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