[EM] Are LIIA, majority, determinism, and neutrality incompatible?

[Kristofer Munsterhjelm]

Someone check my reasoning here, because I might have found out why LIIA 
methods like ranked pairs are so intertwined with their tiebreakers.

Suppose we have a method that passes majority and also LIIA. (It thus 
has to pass Smith and ISDA.) Consider the following election:

4: A > B > C
5: A > C > B
1: B > A > C
4: B > C > A
1: C > A > B
5: C > B > A

A ties both B and C pairwise, and C beats B: A=B, A=C, C>B.

An output order that's consistent with LIIA needs to have C>B if these 
two candidates are adjacent in the order (if not, you could eliminate a 
winner or loser and B>=C is contradicted by the pairwise victory C>B).

So let's consider the possible output rankings with this constraint 
imposed, and with C and B adjacent:

1. A=C>B
2. C>B=A
3. A>C>B
4. C>B>A

as well as the ones where C is not adjacent to B:

5. B>A>C
6. C>A>B

I'll then go through each and say "We can't have [X] because if (someone 
at the end or beginning) is removed, then the order would be [Y] but 
that is contradicted by [Z]". That means that pairwise, we have Z, but 
deleting a loser or winner from the supposed output ranking X would give 
the ranking Y, which is not the same as Z.

1: We can't have A=C>B because removing C gives A>B which is 
contradicted by A=B.
2: We can't have C>B=A because removing B gives C>A which is 
contradicted by A=C.
3: We can't have A>C>B because removing B gives A>C which is 
contradicted by A=C.
4: We can't have C>B>A because removing C gives B>A which is 
contradicted by A=B.
5: We can't have B>A>C because removing C gives B>A which is 
contradicted by A=B.
6: We can't have C>A>B because removing C gives A>B which is 
contradicted by A=B.

The problem can be solved by either breaking ties in favor of some 
candidates or at random in a way that doesn't depend on what candidates 
are running. But I think the tiebreaker has to be assumed to stay the 
same way as we remove candidates for LIIA to hold.

E.g. suppose that the random tiebreak happened to be set to A>B when A 
is pairwise tied with B, and C>A when A is pairwise tied with C. Then we get

A>B, C>A, C>B

So C>A>B. Then removing C returns A>B which is consistent with the 
chosen tiebreaker (A=B becomes A>B); and removing B returns C>A which is 
also consistent with the chosen tiebreaker (A=C becomes C>A).

-km