Kristofer Munsterhjelm
2017-12-03 20:50:28 UTC
Suppose X is a monotone method. Then Smith,X and Smith//X are monotone
methods.
This happens because no candidate can get into the Smith set by raising
a candidate (say A) on some ballots, except for A himself. The reason
this is the case is that going from
... > B > A > ... to
... > A > B > ...
leaves all pairwise contests the same except for weakening B>A and
strenghtening A>B, and the only thing that can lead to is that A gets
admitted into the Smith set.
Thus, when we raise A, one of two things can happen:
1. The Smith set doesn't change. Since X is monotone, A can't have been
harmed by A being raised, so A is not harmed in Smith,X either.
2. A enters the Smith set. Since Smith,X places all in-Smith candidates
above all out-of-Smith candidates, this benefits A.
Somewhat less intuitively, the same holds for Smith//X. In situation 1
either A was already in the Smith set, in which case X's monotonicity
ensures that A is not harmed; or A wasn't in the Smith set, in which
case A still loses. In situation 2, in the worst case, A goes from being
ranked last of all candidates to being ranked last among the Smith set
members. That can't hurt A - worst case, nothing changes (e.g. Smith set
used to be BCD and X ranks them B>C>D>A, then A is admitted and X's
social ranking is still B>C>D>A).
In general, if:
a. X and Y are methods
b. There's a property mono-alter: "A should not be harmed when we
'alter' the ballots in favor of A"
c. Y passes mono-alter (altering ballots in favor of A doesn't reduce
A's chances of winning)
d. Y passes mono-alter.
then X,Y and X//Y pass mono-alter.
(Interesting question: Let MM be the method that returns candidates in
the smallest mutual majority set ranked first and everybody else ranked
last. Then by the above, MM,Plurality is monotone (passes mono-raise).
But Woodall showed that you can't have all of mutual majority, LNHelp,
LNHarm, and monotonicity. How does MM,Plurality fail LNHelp and/or LNHarm?)
Now to mono-add-top and Smith in particular.
Smith itself fails mono-add-top. There are two kinds of failure.
I say that X>Y is "strong" if its margin is greater than some x (the
number of ballots to be added), and X>Y is "weak" if its margin is less
than x.
First, suppose we have an ABCA cycle in a three-candidate situation, and
B>C is weak, C>A strong. Then adding x ACB ballots can reverse B>C to
C>B before it reverses C>A to A>C. This makes C the CW since C beat A
beforehand and now C beats B as well.
Second, suppose we have an ABCA cycle in a four-candidate situation, and
D is beaten by everybody. Let B>D be weak and C>A strong. Then a
collection of ADBC and ADCB ballots can flip B>D to D>B and admit D into
the Smith set, which decreases A's chances of winning after the
tiebreak. (Or do the same with C>D instead of B>D)
The first failure type (exclusion) makes Copeland fail outright. The
second failure type could be used to create counterexamples for Smith,X
methods by a strategy similar to this:
- Set up an election where
- X ranks D ahead of A, but D is not in the Smith set
- there's an ABCA cycle with weak B>D
- mono-add-top compliance of X can't push A ahead of D
with the number of ballots required to flip B>D.
For Smith,Plurality, the constraints would be something like:
C1: ABCA cycle:
(A>B) > (B>A)
(B>C) > (C>B)
(C>A) > (A>C)
C2: everybody beats D, but B>D is close to be flipped:
(A>D) > (D>A)
(B>D) = (D>B) + x
(C>D) > (D>C)
C3: B>D weak and C>A strong:
(B>D) < (D>B) + x
(C>A) > (A>C) + x
C4: D is first and A is second
fpD > fpA + x
fpA > fpB
fpA > fpC
where x is the number of ballots to add.
Running that through a linear programming solver gives a failure proof
like this:
3: A>B>C>D
1: B>C>A>D
2: C>B>A>D
1: D>A>B>C
2: D>B>C>A
2: D>C>A>B
with a Plurality ranking of D > A > C > B and Smith set {A, B, C},
Smith,Plurality thus giving A > C > B > D. Then add one ADBC and:
3: A>B>C>D
1: A>D>B>C
1: B>C>A>D
2: C>B>A>D
1: D>A>B>C
2: D>B>C>A
2: D>C>A>B
the Smith set then contains every candidate, so Smith,Plurality gives
D>A>C>B.
Smith,Minmax requires more finessing (in particular, moving from a
linear solver to an integer solver) but gives:
6: B>C>A>D
4: C>A>B>D
7: D>A>B>C
2: D>C>A>B
The Smith set is {A, B, C} and the Minmax ranking is D>A>B=C.
Then adding one A>D>C>B ballot gives
1: A>D>C>B
6: B>C>A>D
4: C>A>B>D
7: D>A>B>C
2: D>C>A>B
and the Smith set contains every candidate. The Minmax ranking is
D>A>C>B, and so A is pushed to second place.
With such general solvers, it's relatively easy to make failure examples
that exercise say, both Smith,Plurality and Smith,Minmax. E.g.
3: A>B>C>D
1: A>B>D>C
1: A>D>B>C
2: B>C>A>D
1: B>C>D>A
3: C>A>B>D
1: C>D>A>B
2: D>A>B>C
3: D>B>C>A
2: D>C>A>B
then add one A>D>B>C.
==
But the point is, any method that passes mono-add-top and Smith must
have no pair where, before the x votes are added, A is elected, and
after it, D is elected. I suspect this generally will exclude all
Smith,X methods where X itself isn't Smith.
Although I don't have any proof, my suspicion is that a method X that
has no such pairs must be sufficiently "Smith-like" that it would
basically already be Smith. At least they would have to consider the
pairwise matrix, not just say, the positional matrix.
It is however pretty hard to use the above class of mono-add-top
failures to guide the design of a method, because it's a whole class,
not just one particular failure scenario. That is, the reasoning above
says that you shouldn't elect A in a scenario where {C1, C2, C3} all
hold and then elect D in the corresponding scenario after an ADBC has
been added.
The first failure type:
"suppose we have an ABCA cycle in a three-candidate situation, and B>C
is weak, C>A strong. Then adding x ACB ballots can reverse B>C to C>B
before it reverses C>A to A>C. This makes C the CW since C beat A
beforehand and now C beats B as well"
is easier to guard against. It simply says that if we have an ABCA cycle
with B>C weak, C>A strong, then A mustn't win. Note that minmax
satisfies this, because if there's an ABCA cycle and
A's penalty: max(B>A, C>A)
B's penalty: max(A>B, C>B)
C's penalty: max(A>C, B>C)
then ABCA implies that A's penalty is C>A because C>A is in the
direction of the cycle and B>A isn't, so C>A must be stronger.
Similarly, B's penalty is A>B, and C's penalty is B>C.
If B>C is weak and C>A is strong, then A's penalty is greater than C's
penalty, and so A can't win.
(Very sketchy proof idea for greater numbers of candidates: any greater
cycle can be decomposed to a collection of 3-cycles, and a
candidate's penalty is max of the penalties only considering the
participants of that 3-cycle, since max(a, b, c) = max(a, max(b, c)).
For a prospective C to become a CW, it has to beat A strongly and be
beaten weakly in every 3-cycle. But then the argument above holds for
every 3-cycle and minmax won't elect A. Possibly.)
If the proof idea can be developed into an actual proof (i.e. it is
correct), then we know Smith,Minmax handles the first failure method.
And I think Copeland handles the second for four candidates, at least.
So the hard bit is to come up with something that handles both. Even up
to four candidates inclusive would be something.
----
Election-Methods mailing list - see http://electorama.com/em for list info
methods.
This happens because no candidate can get into the Smith set by raising
a candidate (say A) on some ballots, except for A himself. The reason
this is the case is that going from
... > B > A > ... to
... > A > B > ...
leaves all pairwise contests the same except for weakening B>A and
strenghtening A>B, and the only thing that can lead to is that A gets
admitted into the Smith set.
Thus, when we raise A, one of two things can happen:
1. The Smith set doesn't change. Since X is monotone, A can't have been
harmed by A being raised, so A is not harmed in Smith,X either.
2. A enters the Smith set. Since Smith,X places all in-Smith candidates
above all out-of-Smith candidates, this benefits A.
Somewhat less intuitively, the same holds for Smith//X. In situation 1
either A was already in the Smith set, in which case X's monotonicity
ensures that A is not harmed; or A wasn't in the Smith set, in which
case A still loses. In situation 2, in the worst case, A goes from being
ranked last of all candidates to being ranked last among the Smith set
members. That can't hurt A - worst case, nothing changes (e.g. Smith set
used to be BCD and X ranks them B>C>D>A, then A is admitted and X's
social ranking is still B>C>D>A).
In general, if:
a. X and Y are methods
b. There's a property mono-alter: "A should not be harmed when we
'alter' the ballots in favor of A"
c. Y passes mono-alter (altering ballots in favor of A doesn't reduce
A's chances of winning)
d. Y passes mono-alter.
then X,Y and X//Y pass mono-alter.
(Interesting question: Let MM be the method that returns candidates in
the smallest mutual majority set ranked first and everybody else ranked
last. Then by the above, MM,Plurality is monotone (passes mono-raise).
But Woodall showed that you can't have all of mutual majority, LNHelp,
LNHarm, and monotonicity. How does MM,Plurality fail LNHelp and/or LNHarm?)
Now to mono-add-top and Smith in particular.
Smith itself fails mono-add-top. There are two kinds of failure.
I say that X>Y is "strong" if its margin is greater than some x (the
number of ballots to be added), and X>Y is "weak" if its margin is less
than x.
First, suppose we have an ABCA cycle in a three-candidate situation, and
B>C is weak, C>A strong. Then adding x ACB ballots can reverse B>C to
C>B before it reverses C>A to A>C. This makes C the CW since C beat A
beforehand and now C beats B as well.
Second, suppose we have an ABCA cycle in a four-candidate situation, and
D is beaten by everybody. Let B>D be weak and C>A strong. Then a
collection of ADBC and ADCB ballots can flip B>D to D>B and admit D into
the Smith set, which decreases A's chances of winning after the
tiebreak. (Or do the same with C>D instead of B>D)
The first failure type (exclusion) makes Copeland fail outright. The
second failure type could be used to create counterexamples for Smith,X
methods by a strategy similar to this:
- Set up an election where
- X ranks D ahead of A, but D is not in the Smith set
- there's an ABCA cycle with weak B>D
- mono-add-top compliance of X can't push A ahead of D
with the number of ballots required to flip B>D.
For Smith,Plurality, the constraints would be something like:
C1: ABCA cycle:
(A>B) > (B>A)
(B>C) > (C>B)
(C>A) > (A>C)
C2: everybody beats D, but B>D is close to be flipped:
(A>D) > (D>A)
(B>D) = (D>B) + x
(C>D) > (D>C)
C3: B>D weak and C>A strong:
(B>D) < (D>B) + x
(C>A) > (A>C) + x
C4: D is first and A is second
fpD > fpA + x
fpA > fpB
fpA > fpC
where x is the number of ballots to add.
Running that through a linear programming solver gives a failure proof
like this:
3: A>B>C>D
1: B>C>A>D
2: C>B>A>D
1: D>A>B>C
2: D>B>C>A
2: D>C>A>B
with a Plurality ranking of D > A > C > B and Smith set {A, B, C},
Smith,Plurality thus giving A > C > B > D. Then add one ADBC and:
3: A>B>C>D
1: A>D>B>C
1: B>C>A>D
2: C>B>A>D
1: D>A>B>C
2: D>B>C>A
2: D>C>A>B
the Smith set then contains every candidate, so Smith,Plurality gives
D>A>C>B.
Smith,Minmax requires more finessing (in particular, moving from a
linear solver to an integer solver) but gives:
6: B>C>A>D
4: C>A>B>D
7: D>A>B>C
2: D>C>A>B
The Smith set is {A, B, C} and the Minmax ranking is D>A>B=C.
Then adding one A>D>C>B ballot gives
1: A>D>C>B
6: B>C>A>D
4: C>A>B>D
7: D>A>B>C
2: D>C>A>B
and the Smith set contains every candidate. The Minmax ranking is
D>A>C>B, and so A is pushed to second place.
With such general solvers, it's relatively easy to make failure examples
that exercise say, both Smith,Plurality and Smith,Minmax. E.g.
3: A>B>C>D
1: A>B>D>C
1: A>D>B>C
2: B>C>A>D
1: B>C>D>A
3: C>A>B>D
1: C>D>A>B
2: D>A>B>C
3: D>B>C>A
2: D>C>A>B
then add one A>D>B>C.
==
But the point is, any method that passes mono-add-top and Smith must
have no pair where, before the x votes are added, A is elected, and
after it, D is elected. I suspect this generally will exclude all
Smith,X methods where X itself isn't Smith.
Although I don't have any proof, my suspicion is that a method X that
has no such pairs must be sufficiently "Smith-like" that it would
basically already be Smith. At least they would have to consider the
pairwise matrix, not just say, the positional matrix.
It is however pretty hard to use the above class of mono-add-top
failures to guide the design of a method, because it's a whole class,
not just one particular failure scenario. That is, the reasoning above
says that you shouldn't elect A in a scenario where {C1, C2, C3} all
hold and then elect D in the corresponding scenario after an ADBC has
been added.
The first failure type:
"suppose we have an ABCA cycle in a three-candidate situation, and B>C
is weak, C>A strong. Then adding x ACB ballots can reverse B>C to C>B
before it reverses C>A to A>C. This makes C the CW since C beat A
beforehand and now C beats B as well"
is easier to guard against. It simply says that if we have an ABCA cycle
with B>C weak, C>A strong, then A mustn't win. Note that minmax
satisfies this, because if there's an ABCA cycle and
A's penalty: max(B>A, C>A)
B's penalty: max(A>B, C>B)
C's penalty: max(A>C, B>C)
then ABCA implies that A's penalty is C>A because C>A is in the
direction of the cycle and B>A isn't, so C>A must be stronger.
Similarly, B's penalty is A>B, and C's penalty is B>C.
If B>C is weak and C>A is strong, then A's penalty is greater than C's
penalty, and so A can't win.
(Very sketchy proof idea for greater numbers of candidates: any greater
cycle can be decomposed to a collection of 3-cycles, and a
candidate's penalty is max of the penalties only considering the
participants of that 3-cycle, since max(a, b, c) = max(a, max(b, c)).
For a prospective C to become a CW, it has to beat A strongly and be
beaten weakly in every 3-cycle. But then the argument above holds for
every 3-cycle and minmax won't elect A. Possibly.)
If the proof idea can be developed into an actual proof (i.e. it is
correct), then we know Smith,Minmax handles the first failure method.
And I think Copeland handles the second for four candidates, at least.
So the hard bit is to come up with something that handles both. Even up
to four candidates inclusive would be something.
----
Election-Methods mailing list - see http://electorama.com/em for list info