[EM] Pairwise Margins

[Blake Cretney]

Forest Simmons wrote:

>A matrix of pairwise margins is antisymmetric: its transpose has reversed
>signs on all entries.
>
>Suppose we are given an antisymmetric matrix with integer entries. Can we
>always be sure that it is the pairwise margin matrix for some possible set
>of ballots?
>
Yes, and usually this fact eliminates the need to construct such a set 
of ballots

>If so, what is the simplest way to construct such a set of ballots?
>
Here's the simplest way, although it doesn't produce particularly 
elegant examples.

Let's say you have seven candidates, conveniently named after the first 
seven letters of the alphabet.  Now, let's say you want C to beat D. 
 I'm going to create a ballot by listing C and D first, and then the 
remainder of the candidates in arbitrary order.

C D A B E F G
Now, I reverse the above sequence.
G F E B A D C

Put them together, and they have no effect on the pairwise matrix.

Now, leave off C and D on the second ballot.

C D A B E F G
G F E B A

The net effect is to increase C's victory over D by one.  It is obvious 
how to generalize this in order to increase any margin by one, and 
therefore, create any matrix.

If you want only complete rankings, you could reverse C and D instead of 
leaving them off.  This increases the margin by two, and so can create 
any table containing only even margins.  With only complete rankings, 
some marginal tables with odd margins are possible, and some are not.

Another interesting question is what marginal matrices are possible for 
a given number of ballots.

>
>How complicated does the set of ballots have to be? For example, when the
>matrix is a five by five array, how many factions are needed (worst case)
>in a set of ballots for which this would be the pairwise margin matrix? 
>
I don't know how many are needed by the optimal procedure, but I do know 
how many are needed by my procedure, 2*(n^2-n)

So, for 5X5, that is 40

>
>To be more concrete, here's a "randomly" chosen five by five antisymmetric
>matrix: 
>
>[[0,-6,2,1,-9],[6,0,5,-3,4],[-2,-5,0,8,7],[-1,3,-8,0,-2],[9,-4,-7,2,0]]
>
>Is there a set of ballots (making use of fewer than the 120 distinct
>permutations of the candidates A, B, C, D, and E) which gives rise to this
>matrix as its matrix of pairwise margins? 
>
Yes.

---
Blake Cretney