[EM] pairwise matrices and ballots

[Blake Cretney]

Often people want to create examples involving pairwise methods,
usually to show that the method behaves badly in some situation. 
Since not all pairwise matrices are possible, it is customary to
provide a set of ballots instead of just providing a pairwise matrix. 
Typically, this requires first finding a pairwise matrix, and then
working backwards to create ballots that provide this, or a similar,
matrix.  That tends to be time consuming and tedious.  I'm going to
describe a mechanical process for creating a set of ballots necessary
to create a given class of pairwise matrices.

Typically, it is not necessary to compose a specific pairwise matrix.
 Instead, a matrix where every cell is added to an unknown value is
enough.  For example

   A    B    C    D 
A  X    b+9  b+7  b+3
B  b+2  X    b+12 b+14
C  b+6  b+10 X    b+4
D  b+11 b+3  b+2  X

My point is, that even if you do not know "b", you still can
determine the winner in such methods as Schulze, Tideman, Minmax,
Borda, and Nanson.

To prove a violation of some criteria, like monotonicity, it is
necessary to show an effect caused by specific ballots being modified.
 So, the process I will describe starts with a set of known ballots,
and provides additional ballots to create a pairwise matrix as shown
above, involving an unknown "b" term.  In fact, the "b" term can be
calculated, it is just probably not worth the bother.  Similarly, I do
not intend that people will actually use my process to compose the
necessary ballots, the important point is that some such set of
ballots is guaranteed to exist.

The process is slightly different, and the matrix is of a slightly
different form, depending on whether or not some form of equal
rankings are allowed.  I am going to first assume that they are not.

Here is the process:  

Consider first a set of ballots with one ballot showing each possible
permutation of the candidates.  Since these ballots are clearly
neutral with respect to the candidates, the resulting pairwise matrix
must have all cells equal.  For example
A>B>C
A>C>B
B>C>A
B>A>C
C>A>B
C>B>A

Each starting ballot must be one of the possible permutations as
described above.  So, by adding all the other possible permutations to
each starting ballot, the result is a matrix with all cells equal.  In
other words, for every i,j i<>j, M[i,j]=b for some b

Now, for each pairwise contest in the matrix, determine who is the
winner.  By adding one of each possible permutations of ballot, there
is no effect, that is, it is still true that
for every i,j i<>j, M[i,j]=b for some b
although, we are talking about a different b.

Since all permutations are represented, there must be at least one
ballot where the pairwise loser is ranked immediately above the
pairwise winner.  Just reverse these candidates to get a new matrix
where all cells are equal to b (for some b), but the cells involved in
the pairwise winner and loser are b+1 and b-1.

This process can be repeated for the chosen chosen contest until the
contest has b+x vs b-x for any x desired.  Then the process can be
repeated for each other contest to create a matrix like the following:
   A   B   C
A  X   b+2 b-4
B  b-2 X   b+3
C  b+4 b-3 X

That is each cell is of the form b+-x, where b is unknown, x is
chosen, and each b+x must correspond to a symmetrically placed b-x.

Now, I will consider the case that some form of equal ranking is
allowed.  Here, start with the set of all possible permutations, but
where some candidates are ranked equal on the starting ballot, rank
the candidates of the same place equal on each of the other
permutations.  By "the same level", I mean that if, for example, the
2nd place through 5th are equivalent on the starting ballot, modify
each of the permutations so that the 2nd through 5th are ranked the
same.  For example,

A=B > C=D
would correspond to
A=B > D=C
A=C > D=B
A=C > B=D
and so on for every possible permutation of A, B, C, and D.  The
starting ballot must be one (or more) of these resulting ballots, so
just add the rest to make the complete set.  This is done for each
starting ballot.  Since the resulting ballots are neutral with respect
to the candidates, we must have
for every i,j i<>j, M[i,j]=b for some b

Now, to increase an arbitrary cell (i,j) by 1, first add the complete
set of permutations, except with the second to last and last place
candidate ranked equal on every ballot.  By neutrality, we must still
have
for every i,j i<>j, M[i,j]=b for some b
Now, just find one of those ballots where i and j are in last place,
and modify the ballot to rank i over j.  You have increased the M[i,j]
cell without any other effect, except requiring a different "b".  This
process can be repeated to set the cells to b+x, where x is arbitrary
and b is unknown.

---

To use this, I recommend you do the following, present the example like this

12 A>B>C>D
... Additional ballots [don't actually find the ballots, it is enough that
you know they exist]

Resulting matrix,
   A    B    C    D 
A  X    b+9  b+7  b+3
B  b+2  X    b+12 b+14
C  b+6  b+10 X    b+4
D  b+11 b+3  b+2  X

Then go on to show your proof.  Often it will make sense to prove that a
violation of a criteria can be found when using the full ranking form, since
the violation will still be possible when partial rankings are allowed.  So,
matrices like this,

   A   B   C
A  X   b+2 b-4
B  b-2 X   b+3
C  b+4 b-3 X

may be more useful.

Note that my method for dealing with partial orders does not assume that
partial orders are allowed except at the end of ballots, unless the starting
ballots provided do not follow this.  This means that the method is still
valid if partial orders are restricted to the end of the ballot.

---

If you only want to use the marginal matrix, "b" can be subtracted out.  For
example, from above the A vs. B gives (b+9) - (b+2) = 7.  This means that you
can set margins to arbitrary values without regard to the unknown "b".

Remember, however, that if there are no equal rankings, that each pair of
cells will have the form
b+x and b-x, so (b+x) - (b-x) = 2x.  So, all margins must be even.

---
Blake Cretney