[EM] Resistant set: exploring it, and why three candidate monotonicity is easy

[Kristofer Munsterhjelm]

So I've been trying to find a monotone resistant set method, but it's 
very hard. Mostly I have found methods that elect from the resistant 
set, but none of them are monotone.

Bizarrely, it seems that actual *pushover* immunity is much easier than 
monotonicity! At least it is if my simulations are correct; I have found 
three methods in particular that all are pushover immune yet not monotone.

My next idea (that I haven't done yet) is to find the shape of a four 
candidate method that only uses the binary variables of whether any 
given candidate is above the threshold for every subelection. This 
binary data is sufficient to reproduce IFPP or fpA-fpC. For instance if 
we have an ABCA Condorcet cycle with two candidates above the 1/3 
fraction threshold, that looks like:

              {ABC}  {AB} {AC} {BC}
A > thresh   T       T    F    N/A
B > thresh   T       F    N/A  T
C > thresh   F      N/A   T    F

and in that election IFPP eliminates C, then A beats B pairwise and 
wins. (Ditto fpA-fpC.)

If the optimizer says "no solution", then that would indicate that there 
may be a more fundamental problem with trying to make four-candidate 
monotone resistant methods.


But some theory:

The ultimate problem is that a resistant set member is defined as one 
who is undisqualified by anyone else; and that raising a candidate A may 
break X~>Y by obscuring X's first preferences on a subelection 
containing all three of A, X, and Y.

To be more precise, raising A can have one or more of these effects:
	- Establishing A~>B (i.e. making A disqualify B) for some B not 
previously disqualified
	- Breaking B~>A (undoing the disqualification of A by B)
	- Breaking X~>Y (on subelections with three candidates or more).

So the primary monotonicity failure type happens when A is raised, then 
that breaks X~>B so that B is undisqualified. Then B joins the set and 
wins by the tiebreaker that the method implements.

Why is that not a problem for three candidates?

If A disqualifies both B and C directly, then there's no problem since 
raising A can't weaken any of these disqualifications. Similarly, if all 
three are in the resistant set, there's no problem either, because the 
resistant set can't possibly grow.

So suppose that A disqualifies B and B disqualifies C. In the full 
election, both A and B exceed the threshold; necessarily C must be below 
it, and so can't disqualify anyone no matter what.

Thus with a tiebreaker that excludes everybody that disqualify nobody 
(unless that would exclude every candidate), we have the following:

	- C can't win because he's disqualifying nobody, and
	- B can't win because he's disqualified by A

so A must win. Raising A can't make C disqualify anyone (establish 
C~>X), nor can it break A~>Y for any X or Y, so neither of these 
conditions is affected by raising A.

But while we may be able to nail down two candidates in a four-candidate 
election this way, that still leaves one free to cause nonmonotonicity. 
So that could explain why three-candidate IFPP is monotone but it loses 
its monotonicity when you go higher; and explicitly monotone 
constructions like fpA-fpC lose their resistant set compliance as you go 
higher. Retaining monotonicity while going higher is going to need more 
sophistication than this.

-km