[EM] Resistant set: three almost monotone methods, with stats, and Landau surprise

[Kristofer Munsterhjelm]

Here are the three methods I mentioned in my last post. Since they're 
all experimental, I've classed them all in a category called "RMRA1" 
(Resistant mono-raise attempt 1). They are based on the "beats tensor" 
where beats[k][A][B] is true iff A disqualifies B in every subelection 
that contains both A and B, and that has no more than k candidates. Each 
value of k is called a "layer" or "level".

Note that the level k=2 is just pairwise. k<2 doesn't make sense.

Two of the variations use my "making the case for" idea, where we 
determine the score of each candidate in isolation, and then highest 
score wins.

The three variants are:

"Defeated": When making the case for A, create a defeats graph with 
arrows pointing from each candidate to the candidates he beats pairwise. 
Then, starting at k=2:
	- Remove arrows from every candidate X whose disqualification of A has 
vanished, i.e. for which X ~(k)~> A is no longer true.
	- If there are no arrows pointing at A, return A's penalty as k.
	- If k=n and someone is still disqualifying A, return A's penalty as n+1.
	- Otherwise, increase k and try again.

The candidate with the least penalty wins. (This method passes Condorcet.)

"Defeating": A's score is the highest k where A disqualifies someone, 
e.g. the highest k for which there exists a B so that A ~(k)~> B. Break 
ties by counting the number of candidates who disqualify A at this 
level. Highest level and lowest number of candidates disqualifying A wins.

Two-way: A's penallty is the lowest level where A disqualifies someone 
else and is not disqualified by anyone else. If that never happens, then 
the penalty is n+1. Lowest penalty wins.

These probably are not resolvable, so break ties by a monotone method of 
preference. (But see below about Landau.)


Proofs:

To prove that they elect from the resistant set, the following pattern 
is very useful: Suppose that B is not in the disqualified set. Then 
there exists some A who disqualifies B. Then we just need to show that 
if one of them is elected, it's A, not B.

For RMRA1-defeated, it's easy: B always has an arrow pointing at him 
from A. Thus B's penalty is n+1. If A is in the resistant set, then his 
penalty can at most be n (because resistant set members are 
undisqualified by others), as desired.

For RMRA1-defeating: this is trickier and requires a smaller proof that 
if there is a cycle at level k, then either there is a cycle at level 
k+1 or someone ends up disqualifying someone else at that level - you 
can never go from cycle to no disqualifications (every candidate being 
undisqualified) just by going up a single level.[1]

Now going from level 2 up, at some point a cycle involving some or all 
of the candidates will be broken into a linear order. The head of that 
order will be disqualifying someone (the candidate next in the order) 
and not be disqualified by anyone (by virtue of being the head). He will 
thus have the best tiebreak option at level k and any higher level where 
he keeps defeating someone else.

So the winner/s will have some high k and a tiebreak value of zero. Now 
we just need to show that each such cycle head is part of the resistant set.

Suppose for contradiction that the head, B, is not. Then there exists 
A~>B by def of the resistant set. But then we also have A~(k)~>B which 
contradicts that he's not disqualified by anyone at level k. Hence B is 
part of the resistant set. Which was what we wanted.

For RMRA1-two-way: The proof is analogous to RMRA1-defeating. Heads of 
broken cycles defeat someone else but are not defeated by anyone else. 
Since the full disqualification relation is acyclical, cycles will 
always be broken at some point, so there will exist at least one such 
candidate; and by the previous proof, that candidate will be part of the 
resistant set.


Stats!

All three methods have roughly the same strategy resistance, though 
RMRA1-defeated seems to be ever so slightly better. Here are some 
results for 997 voters, 5 candidates, impartial culture:

Smith,No-elimination IRV:     0.4409 (c.i. 0.4365-0.4454)
RMRA1-defeated,Ext-Minmin:    0.4517 (c.i. 0.4472-0.4562)
Smith,IRV:                    0.4549 (c.i. 0.4505-0.4594)
Smith,R1-two-way,Ext-Minmin:  0.4555 (c.i. 0.4510-0.4599)
RMRA1-defeated,Ext-Minmax:    0.4560 (c.i. 0.4517-0.4606)
No-elimination IRV:           0.4578 (c.i. 0.4533-0.4622)
Benham:                       0.4594 (c.i. 0.4550-0.4639)
RMRA1-two-way,Ext-Minmax:     0.4603 (c.i. 0.4559-0.4648)
IRV:                          0.4606 (c.i. 0.4562-0.4651)
RMRA1-two-way,Ext-Minmin:     0.4631 (c.i. 0.4587-0.4676)
Smith,R1-two-way,Ext-Minmax:  0.4635 (c.i. 0.4590-0.4680)
Resistant,Schulze:            0.4909 (c.i. 0.4864-0.4904)
RMRA1-defeating,Ext-Minmin:   0.4926 (c.i. 0.4926-0.5016)
IFPP Method X:                0.4957 (c.i. 0.4912-0.5002)
RMRA1-defeating,Ext-Minmax:   0.4963 (c.i. 0.4919-0.5009)
Resistant,Ext-Minmin:         0.4976 (c.i. 0.4931-0.5021)
Beat-chain(Borda):            1      (c.i. 0.9996-0.9999)
Schulze:                      1      (c.i. 0.9995-0.9999)
Smith,Ext-Minmin:             1      (c.i. 0.9994-0.9998)

Ext-minmax is the leximax version of minmax (break ties by second worst 
defeat, etc). Ext-minmin is the "max A>B" method that has no burial 
incentive but is weak to clones, also made lexicographical.

Generally the results show that RMRA1-defeating is not very good 
(relatively speaking), and the other two can be as strategy resistant as 
IRV in this setting. Note: this is only resistance to strategic voting, 
not nomination! The RMRA1 methods are not cloneproof.

The beat chain and Schulze entries are just there to show how utterly 
unforgiving impartial culture with lots of voters is, and how the "bus 
methods" also converge to 100% manipulability in this an unforgiving 
setting. (Their burial incentive just turns into general coalitional 
strategy.)

And Smith,Ext-Minmin is there to show that max A>B by itself is not 
strategy resistant.

Now the Landau surprise:

Landau is incompatible with the resistant set, as there exist elections 
where no candidate is in both sets. However, these elections are 
infrequent (in impartial culture), so that gives some hope that people 
who like Landau (hi, Forest!) can have their cake and eat it too without 
*too* much strategy degradation. The surprise is, well, let's just see:

L,RMRA1-defeated,Ext-Minmin:  0.4932 (c.i. 0.4887-0.4977)
L,RMRA1-two-way,Ext-Minmin:   0.5105 (c.i. 0.5060-0.5150)
L,RMRA1-defeated,Ext-Minmax:  0.6113 (c.i. 0.6069-0.6156)
L,RMRA1-two-way,Ext-Minmax:   1      (c.i. 0.9994-0.9998)
L,RMRA1-defeating,Ext-Minmax: 1      (c.i. 0.9994-0.9998)
L,RMRA1-defeating,Ext-Minmin: 1      (c.i. 0.9994-0.9998)
Landau,IFPP Method X:         1      (c.i. 0.9994-0.9998)

Now doesn't that seem strange? The choice of the "wrong" tiebreaker 
docks Landau,RMRA1-defeated 10 percentage points and makes two-way 
collapse completely. The reason is this: the methods, as defined above, 
don't produce much beyond winner sets. For instance, every candidate 
disqualified by someone else in RMRA1-defeated has penalty n+1.

When there's no uncovered resistant set member, the method degrades into 
"pick the winner according to the tiebreaker". So the real surprises 
here are:
	- for RMRA1-defeated: max A>B is not too bad a substitute for
		a resistant set member when no uncovered such exists,
	- for RMRA1-two-way: something about it leads to strategy
		vulnerability no matter what.

Not what I would've expected! Perhaps there is some use for max A>B, or 
perhaps it could give some clues as to what a more resolvable 
RMRA1-defeated should be like.

Note that the Landau methods do have pushover incentive. There may be 
better ways to incorporate Landau compliance while getting most of the 
strategy resistance, but it shows that it's not completely out of the 
question. You just have to pay for the Landau compliance, and the method 
is much less forgiving of the details.

Meanwhile, the quest for actual monotonicity continues.

-km

[1] Suppose that there's a cycle between k candidates on the (k-1)th 
level. Then for every candidate A there exists a B so that A~(k-1)~>B. 
Then as we advance one level, barring a perfect tie, at least one of 
these candidates must have more than 1/k first preferences. This 
candidate will still eliminate whoever he eliminated on the (k-1)th 
level. In addition, another of these candidates must have fewer than 
1/k; this candidate can't eliminate anyone. Thus the cycle is broken but 
not everybody is part of the resistant set.