[EM] Pairwise Margins
Blake Cretney
bcretney at postmark.net
Sat Jan 5 19:46:23 PST 2002
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
More information about the Election-Methods
mailing list