[EM] Condorcet Matrix Decomposition

[Dan Bishop]

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.