[EM] Re: Election-methods Digest, Vol 4, Issue 13
Gervase Lam
gervase.lam at group.force9.co.uk
Mon Oct 11 18:45:41 PDT 2004
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.
More information about the Election-Methods
mailing list