[EM] Some thoughts on Smith and monotonicity

[Kristofer Munsterhjelm]

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.