[EM] Re: Election-methods Digest, Vol 4, Issue 13

[Gervase Lam]

This weekend, I thought I would use Kemeny's Method on the following 
example that Steve Eppley used in order to demonstrate MAM to me:

4: A>B>C
3: B>C>A
2: C>A>B

Result Matrix:

   A B C
A [- 6 4]
B [3 - 7]
C [5 2 -]

> Date: Sun, 10 Oct 2004 20:51:43 EDT
> From: RLSuter at aol.com
> Subject: [EM] Reply to Paul Kislanko

> But in the example you cite, 7 of 9 voters voted B>C, so
> how could anyone justify C's win? And 6 out of 9 voters
> voted A>B, so how could anyone justify B's win?

Kemeny can be basically described as follows:

(1) Divide each number in the Result Matrix by the number of ballots cast.
(2) Find a ranking (e.g. C>B>A) that creates a pairwise matrix that 
matches the Result Matrix the closest.  This ranking is the Kemeny Ranking.

So that whole numbers are used, instead of dividing each number in the 
Result Matrix by the number of ballots (in this case 9), I multiplied each 
number in the pairwise matrix created from the ranking in (2) by 9.

To find out how close each possible ranking was (which is shown below), I 
subtracted each pairwise result in the Result Matrix (which is shown below 
the 2nd column of 'matrices') from each corresponding pairwise result in 
the pairwise matrix created from the ranking (the 1st column).  If the 
resultant number is negative, the minus sign of the number is dropped.  
This created the matrix in the 3rd column.

All the numbers in the matrix in the 3rd column were added up.  The 
resultant number is shown to the right of the 3rd column.  The lower this 
number is, the closer the ranking is to matching the Result Matrix.

           A B C       A B C     A B C
        A [- 9 9]     [- 6 4]   [- 3 5]
A>B>C : B [0 - 9] (-) [3 - 7] = [3 - 2] => 20
        C [0 0 -]     [5 2 -]   [5 2 -]

           A B C       A B C     A B C
        A [- 0 0]     [- 6 4]   [- 6 4]
B>C>A : B [9 - 9] (-) [3 - 7] = [6 - 2] => 24
        C [9 0 -]     [5 2 -]   [4 2 -]

           A B C       A B C     A B C
        A [- 0 9]     [- 6 4]   [- 6 5]
B>A>C : B [9 - 9] (-) [3 - 7] = [6 - 2] => 26
        C [0 0 -]     [5 2 -]   [5 2 -]

           A B C       A B C     A B C
        A [- 9 0]     [- 6 4]   [- 3 4]
C>A>B : B [0 - 0] (-) [3 - 7] = [3 - 7] => 28
        C [9 9 -]     [5 2 -]   [4 7 -]

           A B C       A B C     A B C
        A [- 9 9]     [- 6 4]   [- 3 5]
A>C>B : B [0 - 0] (-) [3 - 7] = [3 - 7] => 30
        C [0 9 -]     [5 2 -]   [5 7 -]

           A B C       A B C     A B C
        A [- 0 0]     [- 6 4]   [- 6 4]
C>B>A : B [9 - 0] (-) [3 - 7] = [6 - 7] => 34
        C [9 9 -]     [5 2 -]   [4 7 -]

Here are a few things I noticed:

(1) The Kemeny Ranking is the same as the MAM Ranking.
(2) The lower each number is in the matrix in the 3rd column, the better.  
Though the numbers in this matrix for A v. B and B v. C can get quite low, 
A v. C is stuck with 4s and 5s, which is about 50% of the voters.  Kemeny 
can't get the numbers any lower.
(3) Interesting to note that Kemeny found B>C>A (i.e. A is not the winner) 
the second best ranking.  This also matches exactly the B>C>A group of 
voters, the voters who are causing the "problem".
(4) 3 of the top 4 Kemeny Rankings match that of the three groups of 
rankings the voters submitted.  I suppose this really isn't surprising.

> One question this list doesn't address very much is how
> often the kinds of cycles that bother you (and everyone else)
> would occur in actual voting situations. It's an empirical question
> for which there is now very little data, because Condorcet
> voting has rarely if ever been used in any elections of public
> officials, and it has been used only slightly less rarely in other
> kinds of elections (e.g., in elections held by nongovernmental
> organizations).

I think the result of a simulation on such a thing was posted on to this 
mailing list a few months ago.  I think I am wrong here, but I think that 
the simulation showed that there was about a 75% chance of there being a 
Condorcet Winner in a 5 candidate case.

There is an easy to work out what the chances are of one candidate being a 
Condorcet Winner.  For a candidate to be a Condorcet Winner, the candidate 
has to win all of its pairwise contests.  In the zero-info case, this is 
50% (i.e. 1/2).

For an N candidate election, each candidate has to go through (N - 1) 
pairwise contests.  For a candidate to be a Condorcet Winner, the 
candidate has to win (N - 1) pairwise contests.  Therefore, the chances of 
the candidate being a Condorcet Winner in the zero-info case is
1 / 2^(N-1).

I initially thought that the probability of an election have a Condorcet 
Winner would be N / 2^(N-1).  However, the result of the simulation seemed 
to show otherwise.

I think I know where I went wrong in this calculation.  I think it is more 
like 1 / 2^(N-1) + 1 / 2^(N-2) + ... + 1 / 2.

Thanks,
Gervase.