# [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.)

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.

```