[EM] Correlated Instant Borda Runoff, without Borda

[Ken Kuhlman]

It was me who proposed CIBR back in early June, and to make a long
story short, your first method is a perfect reflection of my current
thoughts.   But yours is more formally defined & thus better.

I had tried for a while this summer to come up with a "grand
unification theory" by combining the idea of correlation with a
Nanson-Fishburn-like approach, but the math got beyond me.   After an
embarrassing failure, I gave up & started working on an EM test bed
application so I could catch more of my own mistakes.  Unfortunately,
I've been too busy with my real job to make any progress in the last
couple of months, but it's great to see that interest in the impact of
correlated candidates hasn't died off.

In my (obviously biased) opinion, correlation is a solid idea that's
just waiting for a good advocate.  Candidate similarity is important,
and ballots have all the information you need to measure it--you just
have to be willing to gather more information than the pairwise
matrix.

thanks,
-Ken

PS:  I had a conjecture that the pairwise matrix & independence matrix
combined contained enough information to re-construct the original
ballots (assuming fully ranked ballots).    Would anyone be interested
in evaluating it?  I could easily be embarrassingly wrong again, but
if not, it would be pretty exciting...





On 12/23/05, Dan Bishop <daniel-j-bishop at neo.tamu.edu> wrote:
> Months ago, someone proposed a method called "Correlated Instant Borda
> Runoff (CIBR)" in order to fix Borda's clone problem. But only now has
> it occurred to be that CIBR's clone-purging idea might be good for
> things other than improving on Borda.
>
> I've got a couple of examples below, but first I'd like to propose an
> improved defintion of "correlation".
>
> *** DEFINITIONS ***
>
> A candidate C is "voted between" A and B on a ballot if C is voted
> either both strictly higher than A and strictly lower than B, or vice-versa.
>
> The "correlation between X and Y with respect to Z" (where X, Y, and Z
> are candidates), denoted "corr(X, Y) wrt Z" is the proportion of the
> ballots on which Z is NOT voted between X and Y.
>
> The "correlation between D and E", denoted corr(D, E), is defined the
> minimum of corr(D, E) wrt F over all candidates F in the complement of
> {D, E}.
>
> *** SUMMATION ***
>
> Consider a summation array labelled by all possible combinations of X,
> Y, and Z in "corr(X, Y) wrt Z".  To represent a ballot in this summation
> array, put a 0 in each positions in which Z is not voted between X and
> Y, and a 1 elsewhere.  To calculate corr(X, Y) wrt Z, simply add the
> appropriate elements of the ballot arrays and divide by the number of
> ballots.
>
> Let N be the number of candidates, and assume N>2.  By symmetry in the
> definition, corr(X, Y) wrt Z == corr(Y, X) wrt Z, so we only need to
> consider the unordered combinations of X and Y: There are N×(N-1)/2 of
> them.  For each (X, Y) pair, there are N-2 of them.  Therefore, the size
> of the summation array is N×(N-1)/2×(N-2) = (1/2)N³-(3/2)N²+N <= (1/2)N³.
>
> Therefore, the computation of the correlations is third-order summable.
>
> *** EXAMPLE: COMPUTATION OF CORRELATIONS ***
>
> Consider the hypothetical Tennessee capital election between Chattanooga
> (C), Knoxville (K), Memphis (M), and Nashville (N).
>
> 42%: M>N>C>K
> 26%: N>C>K>M
> 15%: C>K>N>M
> 17%: K>C>N>M
>
> If I calculated correctly, the correlations of each possible trio of
> candidates are:
>
> corr(C, K) wrt M = 100%
> corr(C, K) wrt N = 100%
> corr(C, M) wrt K =  59%
> corr(C, M) wrt N =  26%
> corr(C, N) wrt K =  85%
> corr(C, N) wrt M = 100%
> corr(K, M) wrt C =  41%
> corr(K, M) wrt N =  26%
> corr(K, N) wrt C =  15%
> corr(K, N) wrt M = 100%
> corr(M, N) wrt C =  74%
> corr(M, N) wrt K =  74%
>
> Thus, the correlations between each possible pair of candidates are:
>
> corr(C, K) = min(100%, 100%) = 100%
> corr(C, M) = min( 59%,  26%) =  26%
> corr(C, N) = min( 85%, 100%) =  85%
> corr(K, M) = min( 41%,  26%) =  26%
> corr(K, N) = min( 15%, 100%) =  15%
> corr(M, N) = min( 74%,  74%) =  74%
>
> Note that the clone pair has 100% correlation.
>
> *** EXAMPLE: CLONE-PURGING WITH PAIRWISE COMPARISONS ***
> (Just like CIBR, but without the Borda points.)
>
> Consider the election method:
>
> while there are at least 2 candidates:
>     compute the correlations
>     find the most-correlated pair of candidates
>     eliminate the loser of a contest between that pair
> elect the remaining candidate
>
> With the ballots from the previous example, the most-correlated pair is
> Chattanooga and Knoxville.  Chattanooga pairwise defeats Knoxville, 83%
> to 17%, so eliminate Knoxville.
>
> The correlation trios without Knoxville are:
>
> corr(C, M) wrt N =  26%
> corr(C, N) wrt M = 100%
> corr(M, N) wrt C =  74%
>
> The new most-correlated pair is Chattanooga and Memphis.  Chattanooga
> beats Memphis, 58% to 42%, so eliminate Memphis.
>
> This leaves only two candidates: Chattanooga and Nashville.  Chattanooga
> pairwise loses to Nashville, 32% to 68%, so is eliminated.  Nashville wins.
>
> Note that the example elected the Condorcet winner.  This will always be
> the case, because if a CW exists, then by definition it cannot pairwise
> lose to another candidate and thus will never be eliminated.
>
> *** EXAMPLE: CLONE-TRANSFER APPROXIMATION OF IRV ***
>
> Consider the election method:
>
> count the first-choice votes of each candidate
> while no candidate has a majority of the vote:
>     eliminate the last-place candidate
>     transfer that candidate's votes to their most-correlated candidate
> elect the candidate with a majority of a vote
>
> With the ballots from the original example, the first-choice votes are:
>
> 42%: M
> 26%: N
> 17%: K
> 15%: C
>
> No candidate has a majority, so the last-place one (Chattanooga) is
> eliminated.  The correlations without Chattanooga are:
>
> corr(K, M) wrt N =  26%
> corr(K, N) wrt M = 100%
> corr(M, N) wrt K =  74%
>
> Chattanooga is 26% correlated with Memphis, 85% correlated with
> Nashville, and 100% correlated with Knoxville.  Because Knoxville is
> best-correlated to Chattanooga, it receives its vote, so the count is now:
>
> 42%: M
> 32%: K
> 26%: N
>
> The next candidate for elimination is Nashville.  The best-correlated
> candidate to Nashville is Knoxville, which receives Nashville's vote,
> producing a final tally of:
>
> 58%: K
> 42%: M
>
> Knoxville now has a majority of the vote, and is declared the winner.
> (Note that is the same as the IRV winner.  I'd be interested to know how
> often this is the case.)
>
>
> By changing "majority" to "Droop quota" and extending the "transfer
> votes to the most-correlated candidate" rule to excess votes, this
> method can be used to approximate STV (or STV-CLE or a pairwise
> comparision for CPO-STV).  The advantage over traditional STV is that
> the clone-transfer method is third-order summable.
> ----
> election-methods mailing list - see http://electorama.com/em for list info
>