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

Forest Simmons forest.simmons21 at gmail.com
Mon Nov 22 20:58:54 PST 2021

If I am not mistaken, here's a way to modify any type one method to confer
type three reverse symmetry:

For any ballot set S Let F1 be the finish order for the base method applied
to S. Let F2 be the finish order for the base method applied to the set of
reversed ballots S'.

Now pairwise sort F1, F2, and their reverse orders with the same bubble
sort algorithm. Of these four beatpaths, let F be the strongest, i.e. the
one whose weakest pairwise margin is the greatest in absolute value.

Then F and its reversal F' have the same strength.  Whichever of these two
orders makes the most sense as a finish order for S is the new finish order
... the other one will then turn out to be the new finish order for S'.

Whether for ballot set S or S' the same four beatpaths will result .... so
the set {F, F'} will also be the same. It's a simple matter to check which
is a beatpath for the "forward" ballots and which for the reverse.

Make sense?

El lun., 22 de nov. de 2021 8:03 a. m., Kristofer Munsterhjelm <
km_elmet at t-online.de> escribió:

> 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.
> ----
> Election-Methods mailing list - see https://electorama.com/em for list
> info
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20211122/00255859/attachment.html>

More information about the Election-Methods mailing list