[EM] Three forms of reversal symmetry, and an LIIA implication

[Kristofer Munsterhjelm]

I'm going through some draft posts of mine, and here's one. I was
discussing reversal symmetry with Forest Simmons a while ago, where he
said that reversal symmetry means that when you reverse an election, the
winner doesn't stay the same. I had been working on an assumption that
when you reverse the election, the loser becomes the winner and vice versa.

(But looking back at my proof of incompatibility of DMTBR, Condorcet,
and reversal symmetry, that proof *does* use the correct definition -
Forest's. So I must've only thought of the stronger definition recently.)

Thinking a bit more, I came up with three types of reversal symmetry,
from weakest to strongest:

	1. If A is the unique winner and the election is reversed, then A must
not be the unique winner.[1]
	2. If A is the unique winner and B is the unique loser, then reversing
the election should produce an election where B is the unique winner and
A is the unique loser.
	3. If there are no ties anywhere in the social ordering, then reversing
the election should reverse the social ordering as well. If X is ranked
ahead of Y in the forwards election's outcome, then Y should be ranked
ahead of X in the reversed election's outcome.

Then I spent a lot of time trying to prove that passing 1+ passing LIIA
implies passing 3.

I don't think I can do that, but I can salvage my efforts *somewhat* by
showing that Majority+2+LIIA implies 3, at least whenever there are no ties.

The proof is inductive. Suppose first that we have two candidates: A and
B. If there are no ties, one beats the other and is implied to win by
majority. Reversing the election makes the other candidate win, which
satisfies #3.

Now suppose that property 3 holds for every k-candidate (tie-less)
election, and we want to prove it for (k+1) candidates. For some given
election eA, let the social order be A>B>..>Z.

Eliminate A and let the resulting election be called eB. By the
induction property, 3 holds here, and by LIIA, the outcome for eB must
be B>...>Z. Call the reversed election eBR; its outcome must be Z>###>B,
where ### indicates the candidates ... in reverse order.

Now reverse eA to get eC. By property 2, Z must be the winner and A the
loser. Eliminate A. By LIIA, this must not change the order of outcome
of the remaining candidates. But the resulting election (after
eliminating A) is just eBR, and we've established that its outcome must
be Z>###>B. Thus eC's order must be Z>###>B>A and eA must also satisfy
property 3.

====

The really tough part is using 1+LIIA+Majority to go to 2. It might not
even be possible. The proof above stops working because it's possible
that reversing eA can lead to some other B and C becoming the winner and
loser, and then the rest of the proof falls apart. Trying to use the
induction case to pin down the position of A doesn't work either, e.g. I
can easily do:

Suppose induction + property 1. Then A>B>...>Z, eliminating A gives us
B>...>Z and reversing this gives Z>###>B.

But then re-adding A to the reversed election, there's no guarantee that
A will be listed last, because we don't have pinned down A to be the
loser in eC.

Of course, if there *is* a way, I'd be interested in knowing it :-)

-km

[1] It's possible to generalize this for ties: if all candidates of some
set S win with positive probability, then after reversing the election,
every candidate not in S must be ranked ahead of every candidate in S.
But I don't think that's canonical -- perhaps you could prove it with
the help of resolvability, though.