[EM] Condorcet Matrix Decomposition
Dan Bishop
daniel-j-bishop at neo.tamu.edu
Thu Nov 24 23:32:48 PST 2005
For any set of ranked ballots, there is a unique Condorcet matrix. If
there are 3 or more candidates, the converse is not true (e.g., consider
A>B>C+C>B>A and B>A>C+C>A>B).
But even though we can't find the exact set of ballots that created a
Condorcet matrix, we can find *a* set of ballots (which I shall call a
"Condorcet Matrix Decomposition", or CMD) that might have been used to
create the matrix. My intended purpose of the CMD is to estimate who
might win an election if a non-Condorcet-matrix method were used.
Below is a method that (I think) computes a CMD.
*** PROPOSED METHOD ***
while the Condorcet matrix is nonzero:
Rank the Candidates in descending order of minimum pairwise votes.
If there is a tie, break it by using Borda scores.
If there is still a tie, break it randomly.
Construct a ballot with this ranking.
Subtract that ballot from the Condorcet matrix.
*** EXAMPLE ***
(This was created from the ballots 3:A>B>C, 5:B>A>C, 4:C>A>B.)
Start with the Condorcet matrix:
A B C
A 0 7 8 min = 7, borda = 15
B 5 0 8 min = 5, borda = 13
C 4 4 0 min = 4, borda = 8
Create a ballot A>B>C.
A B C
A 0 6 7 min = 6, borda = 13
B 5 0 7 min = 5, borda = 12
C 4 4 0 min = 4, borda = 8
Create a ballot A>B>C.
A B C
A 0 5 6 min = 5, borda = 11
B 5 0 6 min = 5, borda = 11
C 4 4 0 min = 4, borda = 8
The ranking is A=B>C. Suppose the A=B tie is resolved in favor of A.
Create a ballot A>B>C.
A B C
A 0 4 5 min = 4, borda = 9
B 5 0 5 min = 5, borda = 10
C 4 4 0 min = 4, borda = 8
Create a ballot B>A>C.
A B C
A 0 4 4 min = 4, borda = 8
B 4 0 4 min = 4, borda = 8
C 4 4 0 min = 4, borda = 8
There is a 3-way tie. Break it at random.
Suppose B>A>C is chosen.
A B C
A 0 4 3 min = 3, borda = 7
B 3 0 3 min = 3, borda = 6
C 4 4 0 min = 4, borda = 8
Create a ballot C>A>B
A B C
A 0 3 3 min = 3, borda = 6
B 3 0 3 min = 3, borda = 6
C 3 3 0 min = 3, borda = 6
There is a 3-way tie. Break it at random.
Suppose B>C>A is chosen.
A B C
A 0 3 3 min = 3, borda = 6
B 2 0 2 min = 2, borda = 4
C 2 3 0 min = 2, borda = 5
Create a ballot A>C>B.
A B C
A 0 2 2 min = 2, borda = 4
B 2 0 2 min = 2, borda = 4
C 2 2 0 min = 2, borda = 4
There is a 3-way tie. Break it at random.
Suppose A>B>C is chosen.
A B C
A 0 1 1 min = 1, borda = 2
B 2 0 1 min = 1, borda = 3
C 2 2 0 min = 2, borda = 4
Create a ballot C>B>A.
A B C
A 0 1 1 min = 1, borda = 2
B 1 0 1 min = 1, borda = 2
C 1 1 0 min = 1, borda = 2
There is a 3-way tie. Break it at random.
Suppose B>A>C is chosen.
A B C
A 0 1 0 min = 1, borda = 1
B 0 0 0 min = 0, borda = 0
C 1 1 0 min = 2, borda = 2
Create a ballot C>A>B. The Condorcet matrix is now zero, so we are done.
In summary, the set of ballots created was:
4: A>B>C
1: A>C>B
3: B>A>C
1: B>C>A
2: C>A>B
1: C>B>A
*** EXAMPLE BASED ON THE EXAMPLE ***
Suppose that IRV is applied to the CMD ballots from the example: A (the
CW) is the winner.
But if the original ballots were used, B would be the winner. This
proves that an IRV winner cannot be determined from a Condorcet matrix.
It also raises the question of whether IRV on a CMD is more likely to
elect the CW than IRV on the actual ballots.
More information about the Election-Methods
mailing list