[EM] Resistant set incompatibility and passing methods

[Kristofer Munsterhjelm]

Here are some more results about the resistant set.

First I'll mention some things it's compatible and incompatible with, 
and then some methods that pass Resistant (i.e. elects from the set).

First, the good news:

- The Condorcet winner is always in the resistant set. Proof: The 
Condorcet winner W beats every other candidate X pairwise by definition. 
Hence X ~(2)~> W is false; and hence X ~> W is false, so W is not 
disqualified by anyone. Thus W is in the resistant set.

- At least one member of the Smith set is in the resistant set. Proof: 
No member outside the Smith set can disqualify a member inside, by 
argument directly analogous to that of the CW. Now suppose for 
contradiction every Smith set member disqualifies someone else. Then 
there is a cycle. But the resistant set is acyclical, so that's 
impossible. Hence someone in the Smith set is undisqualified and thus in 
the resistant set.

Then the bad news:

- No method using the pairwise matrix alone can pass Resistant. The 
elections

1: A > B > C
1: A > C > B
1: B > A > C
2: C > B > A

and

1: A > C > B
2: B > A > C
1: C > A > B
1: C > B > A

give identical pairwise matrices, but the former's resistant set is {A} 
and the latter's is {C}.

- Nor do first preference counts alone suffice:

2: A > B > C
1: B > A > C
2: C > A > B

has resistant set {A}, and

2: A > B > C
1: B > C > A
2: C > B > A

has resistant set {B, C}. However, I couldn't find any such "disjoint 
collisions" with the same first preference counts *and* pairwise 
matrices, leaving open the possibility that a combination of the two 
could be used to create a summable Resistant method. (At the moment I 
don't see how, though.) I can't even find one with the more discerning 
intersection of resistant set and Smith set.

- Landau is incompatible with Resistant. Consider the election

1: A > B > D > C
1: A > D > C > B
1: B > A > C > D
1: B > C > A > D
1: B > D > C > A
1: C > A > B > D
2: C > B > A > D
1: D > A > B > C
1: D > A > C > B
1: D > C > A > B

The resistant set is B, but B is covered by A, since A pairwise beats 
both B and D whereas B only beats D pairwise.

My simulation puts the occurrence of disjoint Landau and resistant sets 
at around once every 21k elections (impartial culture, 97 voters, 5 
candidates). So it's relatively rare, which means you can make a Landau 
method not be *too* vulnerable to strategy. But you can't get it to pass 
Resistant all the time.

- Copeland is incompatible with Resistant. For the election

1: A > B > D > C
1: A > C > B > D
1: B > C > D > A
1: B > D > C > A
1: C > D > A > B

the Copeland set is {B, C}, but the only resistant set member is A.

My simulation puts the occurrence at 1/40 under the same conditions, 
which fits with my intuition that Copeland can't be made strategy resistant.

- Reversal symmetry is incompatible with Resistant. For the election

1: A > C > B
2: B > A > C
2: C > B > A

C ~> B ~> A, so C is the sole resistant set member.

In reverse:

1: B > C > A
2: C > A > B
2: A > B > C

C ~> A ~> B, so again C is the sole resistant set member.

My simulator hits one of these every 12 elections or so. So reversal 
symmetry discards strategy resistance (of this form). I kinda suspected 
this from my proof that DMTBR is incompatible with rev. sym., but this 
is easier.

Note that the simulator encountering an example once every k times 
doesn't mean that the method is vulnerable one in k times, because there 
may be second order effects; but the order of magnitude matches up 
pretty well with what I've seen - Copeland and rev. sym are no-gos, 
while you can get Landau and only pay a small penalty.

And the neutral (but surprising) news:

- Resistant is not a subset of the DMT set, nor even of the mutual 
majority set. Consider this election:

1/4 + epsilon: A>B>C
1/4 + epsilon: B>A>C
1/2 - 2 epsilon: C>B>A

The mutual majority and DMT sets are {A, B}; but every candidate is in 
the resistant set. So you don't get mutual dominant third burial 
resistance (or UDMT) simply by electing from the resistant set. This 
surprises me because I always thought the high strategy resistance of 
certain methods in simulations were due to DMTBR compliance. But it 
makes sense in retrospect because IFPP elects from the resistant set yet 
fails mutual majority.

If there is a single DMT candidate W, though, then that candidate is the 
sole member of the resistant set: since he's a CW, W ~(2)~> X for all 
other X, and since he has more than 1/3 of the first preferences, W 
~(k)~> X for all k > 2. Hence W disqualifies everybody else directly.

If a candidate has majority first preference support, then he's also the 
sole DMT set member, so a majority candidate also directly disqualifies 
everybody else.


========

Methods passing Resistant:

Elimination methods (like Baldwin, IFPP, IRV, Nanson, etc.) can be seen 
as methods that go from a wider sub-election to a more narrow one, 
repeatedly, until only one candidate remains.

For these, there's a particular useful strategy. If we can show that 
whenever A ~> B, then A is never eliminated before B by the method; then 
the method passes Resistant when we disregard any additional rules (like 
IRV's condition that a candidate with >1/2 first prefs is immediately 
elected).

Suppose otherwise for contradiction that B, who is not a member of the 
resistant set, is elected, and there exists some A who disqualifies B. 
(Otherwise B would be a member of the resistant set.) Then for B to have 
been elected, every other candidate must have been eliminated. In 
particular, A must have been eliminated. But this is impossible if, 
whenever A ~> B, A is never eliminated before B. Call this the "proper 
order property".

Okay.

IRV passes Resistant because unless there is a k-way tie, in every 
round, at least one of the k candidates must have less than 1/k of the 
first preferences. Consider every disqualification A ~> B. If neither A 
nor B has been eliminated yet, then A must have greater than 1/k of the 
first preferences by definition. Thus whoever is eliminated, it's not A 
(but it could be B). Since this holds for every disqualification, A can 
never be eliminated before B. So IRV passes if we disregard the majority 
rule. But the majority rule can't elect anyone who's disqualified by 
someone else, since a candidate with majority first preferences 
disqualifies everybody else in that sub-election. Hence IRV itself passes.

IFPP is analogous. It batch disqualifies every candidate with less than 
1/k first preferences in each round. By the same argument as before, 
that can't eliminate A before B if A ~> B. So IFPP passes.

Note that the strategy doesn't work for BTR-IRV. It's possible that A, 
B, and C remain, and A ~> C but B beats A pairwise. If the losers are A 
and B, then B beats A pairwise, then the A ~> C relation is lost and C 
could be elected.

Benham passes. Suppose that the current round/sub-election's CW is W. 
Then W is not disqualified by any continuing candidate since W pairwise 
beats all of them. And W can't be disqualified by any candidate who was 
eliminated earlier, since IRV follows the proper order property. Hence W 
is not disqualified by anyone, so W is in the resistant set.

My earlier "method X" passes because when it's figuring out A's score, 
it can never eliminate a candidate with more than 1/k of the first 
preferences in any subelection. Hence the proper order property is 
retained. If A is disqualified by someone else, A must be eliminated in 
one of the steps as a consequence, and his score thus is zero.

(Another method my simulations suggest elects from the resistant set is 
"fpA - max fpC elimination", which at each round eliminates the fpA - 
max fpC loser. I haven't proven it, though. A Benham variant could have 
the benefit of being monotone with Smith sets <= 3 candidates, but 
dayum, it would be complex. And not summable.)

Some general templates:

If M elects from the resistant set, so does Smith,M and Smith//M. 
Smith,M is straightforward: since there's a Smith member in the 
resistant set, there will always be a resistant set candidate to elect.

As for Smith//M: Since no non-Smith candidate can disqualify a Smith 
candidate, removing Smith-dominated candidates can't introduce a Smith 
set member into the resistant set who wasn't in it before. It's possible 
that some candidates who weren't disqualified before become so due to 
fewer sub-elections needing to be taken into account, but everybody who 
was disqualified before will remain disqualified (or be eliminated 
outright due to being outside the Smith set).

By referring to these methods we can say that electing from the 
resistant set is compatible with any one of clone independence, 
Condorcet, Smith, ISDA, mono-add-top, and three-candidate mono-raise. It 
might be compatible with both LNHs (since IRV passes them), but I 
haven't proven that the disregarding of equal-ranked candidates doesn't 
invalidate LNH. The combinations of these criteria that different 
methods pass are also compatible. I don't know what other combinations 
or criteria are, but I would very much prefer unrestricted mono-raise to 
be compatible.

-km