Three forms of reversal symmetry, and an LIIA implication
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.
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@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
On 23.11.2021 05:58, Forest Simmons wrote:
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?
I think that would work, but you might be able to weaken the type one
requirement to an "extra weak reversal symmetry":
Type 0: If the forward election does not produce a tie anywhere in the
social ordering, then reversing the election should not lead to the same
ordering.
As long as at least one pair is different, you could (theoretically)
distinguish between the two and assign F to one and F' to the other.
Maybe bubble sort will require something between type 0 and 1 reversal
symmetry to ensure that the beatpath orders are always all different,
though.
And speaking of weakenings, I think I can discard the requirement for
monotonicity in my 2+LIIA->3 proof.
Suppose there are two candidates and they don't tie. Then 2 immediately
requires that a social order of A>B for the forward election implies B>A
for the reverse, which is all we need to provide the base of the
induction chain.
-km
Very Good!
And see an inline comment on my symmetrization suggestion ... a practical
consideration or two.
El mié., 24 de nov. de 2021 6:55 a. m., Kristofer Munsterhjelm <
km_elmet@t-online.de> escribió:
On 23.11.2021 05:58, Forest Simmons wrote:
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.
Or, use both bubble and sink sort on both F1 and F2 .... where bubble and
sink, respectively, prioritize out of order swaps for adjacent pairs
nearest the bottom and top, respectively .... one starts near the bottom
and bubbles up, while the other starts near the top and settles down.
One could use weakest margin of defeat to prioritize the swaps (a sorted
margins variant), and thereby simplify the last step of identifying F and
F'... but that creates a potential problem when two nearby adjacent pairs
have the same margin of defeat.
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?
I think that would work, but you might be able to weaken the type one
requirement to an "extra weak reversal symmetry":
Type 0: If the forward election does not produce a tie anywhere in the
social ordering, then reversing the election should not lead to the same
ordering.
As long as at least one pair is different, you could (theoretically)
distinguish between the two and assign F to one and F' to the other.
Maybe bubble sort will require something between type 0 and 1 reversal
symmetry to ensure that the beatpath orders are always all different,
though.
And speaking of weakenings, I think I can discard the requirement for
monotonicity in my 2+LIIA->3 proof.
Suppose there are two candidates and they don't tie. Then 2 immediately
requires that a social order of A>B for the forward election implies B>A
for the reverse, which is all we need to provide the base of the
induction chain.
-km