[EM] The resistant set

[Kristofer Munsterhjelm]

After a bit of a false positive with method X, I think I may have a 
class of monotone Condorcet burial resistant methods! Now, I have been 
proven wrong before, so please, have at it.

Let the "resistant set" (or "inner burial set", "inner burial-resistant 
set") be the set of candidates who are not excluded by the DMTC 
generalization criterion of my "Unifying DMTC and DMTCBR" post. To recap:

If A is ranked first by more than one over the number of remaining 
candidates, on every sub-election (restricted election) that contain 
both A and B and someone else, and in addition A beats B pairwise, then 
B is disqualified from the resistant set. Let the resistant set be every 
candidate not thus disqualified. Note that disqualified candidates may 
disqualify others in turn.

-

I'm pretty sure that this set be monotone, and I can *almost* prove that 
its composition with a monotone method is also monotone. (The almost is 
why I'm not going to declare victory yet.) As I still don't have a 
monotonicity checker, I would like some independent tests to provide 
evidence for or against. Yee diagrams don't look too jagged, though.

Here are some results, with 97 voters 5 candidates impartial culture, 
10k elections, 32k tests per. I'll make a few observations after:

The current resistance champion (among the methods I've implemented) is 
Kevin Venzke's "No-elimination IRV". I show it and Smith-IRV for context:

Smith//No-elimination IRV:

Burial, no compromise:  716     0.0716
Compromise, no burial:  2193    0.2193
Burial and compromise:  258     0.0258
Two-sided:              0       0
Other coalition strats: 1244    0.1244
==========================================
Manipulable elections:  4411    0.4411

Smith,No-elimination IRV:

Burial, no compromise:  714     0.0714
Compromise, no burial:  2536    0.2536
Burial and compromise:  3       0.0003
Two-sided:              1       0.0001
Other coalition strats: 1298    0.1298
==========================================
Manipulable elections:  4552    0.4552

Smith//IRV:

Burial, no compromise:  678     0.0678
Compromise, no burial:  2191    0.2191
Burial and compromise:  299     0.0299
Two-sided:              1       0.0001
Other coalition strats: 1543    0.1543
==========================================
Manipulable elections:  4712    0.4712

And some composed methods:

Smith,(Resistant set, Ext-Minmax):

Burial, no compromise:  1471    0.151775
Compromise, no burial:  1469    0.151568
Burial and compromise:  672     0.0693355
Two-sided:              1093    0.112773
Other coalition strats: 0       0
==========================================
Manipulable elections:  4705    0.48545

Smith//(Resistant set, max A>B):

Burial, no compromise:  1422    0.145876
Compromise, no burial:  1612    0.165367
Burial and compromise:  617     0.063295
Two-sided:              1110    0.11387
Other coalition strats: 0       0
==========================================
Manipulable elections:  4761    0.488408

Smith,(Resistant set, Plurality):

Burial, no compromise:  1372    0.140286
Compromise, no burial:  1924    0.196728
Burial and compromise:  425     0.043456
Two-sided:              1054    0.107771
Other coalition strats: 0       0
==========================================
Manipulable elections:  4775    0.488241


The observations: It seems that no matter what you stick in here, the 
strategy susceptibility is around 0.49. That suggests to me that 
completely contrary to my initial suspicions, this resistant set isn't 
too fragile, but it's too strict. It's sufficient for burial resistance, 
but it may not be necessary. It's quite possible that NEIRV fails the 
criterion, for instance, yet it is burial-resistant. Verifying Filip's 
Selective Ranked Pairs would also (most likely) prove such an example.

For monotonicity, I'm thinking as follows:

First, the composition M1,M2 where M1 is a set and M2 is monotone is 
itself monotone if:
	1. M1 is monotone
	2. M2 is monotone,
	3. Raising a current member of the M1 set can never introduce someone 
into that set who wasn't there before.

The first two points are obvious. The third point is necessary because 
otherwise, raising A may admit some B into the set who's higher ranked 
than A by the base method. But if the third point holds, then raising A 
can only kick other members out of set M1, which, by the assumption that 
A won before raising, can never harm A. (Less competition never hurts.)

To show that the resistant set is monotone, we should show that raising 
A can't make some other candidate B now bar A. This is pretty obvious: 
raising A can never raise B above the threshold in any restricted 
election, if B weren't already above it. Nor can it turn A>B into B>A.

So point three, the "no-expansion property": a candidate B could be 
admitted if some C who was previously barring B stops either having 
 >1/|S| support in every restricted election involving both of them, or 
stops beating B pairwise. The latter is obviously impossible. But the 
former... that's what has to be shown, and why I'm not certain.

You would think that set growing would be possible by a variant of 
Kevin's counterexample to method X. Let A bar C from the set, then let 
the base method outcome be C>B>A so that B wins. Then raising B on an 
ABC ballot could reduce A below the threshold, after which C wins. But 
somehow I can't get that to work...

It gives an idea of where you could start if you have a monotonicity 
checker, though.

-km