[EM] Resistant set results

[Kristofer Munsterhjelm]

So I've been trying to figure out why electing from my "resistant set" 
(or "inner burial set") provides general strategy resistance in 
simulations, more or less regardless of just what method is being used 
for electing from the resistant set itself. And I've made some discoveries.

Most notable is this: Suppose that the resistant set consists of a 
single member. Then any method that elects from the resistant set (let's 
call that property the Resistant criterion) is burial immune in that 
particular election.

My simulations seem to indicate that electing from the resistant set 
confers more general strategy resistance as well. I've made a stab at 
figuring out compromise resistance, but this isn't complete, and the 
simulations show that unlike burial resistance, compromise resistance 
isn't absolute.

But before I show unburiability, here are some formal bits.

The resistant set is defined based on the "disqualification relation", A 
~> B, and the concept of sub-elections.

A sub-election of some election is that election, but modified by 
eliminating some candidates as well as any exhausted ballots. These are 
denoted by sets representing the remaining candidates. For instance, the 
sub-election {A, B, C} or (ABC) of some election e is what you would get 
after eliminating every candidate but A, B, and C, and then removing 
exhausted ballots.

Define A ~(ABC)~> B as the disqualification relation on the sub-election 
{A, B, C}. This relation is defined on every sub-election containing 
both A and B and holds if A has more than 1/k of the first preferences 
among the voters who distinguish between A and B, where k is the number 
of candidates in the sub-election, in this case 1/3.

Define A ~(k)~> B if A ~X~> B for every sub-election X of k candidates 
containing both A and B.

Define A ~> B if A~X~> B for every sub-election X containing both A and 
B. In this case, say that "A disqualifies B".

The resistant set contains every candidate who is not disqualified by 
someone else.

Some short results for the disqualification relation are:

A ~> B is acyclical. Proof: Suppose otherwise that there's a k-cycle A 
~> B ~> C ~> ... ~> A. Then consider the sub-election containing the k 
candidates who are part of the cycle. It's impossible for all k 
candidates to have more than 1/k of the first preferences. Suppose 
candidate C has less. Then C can't be disqualifying any of the others, 
so there is no cycle after all.

A ~> B is not transitive. A could have more than 1/k first preferences 
in every sub-election containing A and B, as could B in every 
sub-election containing B and C (so A ~> B and B ~> C), but there could 
exist some sub-election containing A and C but not B, where A does not 
have more than 1/k of the first preferences, so we don't automatically 
have A ~> C.

(The transitive closure is not monotone. We can have A ~> B and B ~> C, 
but raising A can break B ~> C. So it's going to take more clever tricks 
than that for monotonicity.)

Now for unburiability:

Suppose W is the sole member of the resistant set. We want to show that 
any voter who prefers some A to W can't introduce A into the resistant 
set by burying W.

What can a burier do? Suppose the burier's honest vote is A>B>W>C>D and 
W is the current winner. Then by changing his vote to A>B>C>D>W, the 
burier can move some sub-election first preferences from W to someone he 
ranked lower (here C or D) in some sub-elections not containing A or B. 
This could potentially break a disqualification of a candidate he ranks 
below W, by W.

But note: the burier can't affect any relation between W and someone 
ranked higher than W on his honest ballot, because in every such 
sub-election, he's already contributing maximally to the higher ranked 
candidate. Nor can he affect any relation between A and someone ranked 
lower than A, for the same reason.

Since W is the sole member of the resistant set, A is being disqualified 
by someone else. But the burier can't affect any disqualifications of A 
and thus can't introduce A into the resistant set to win.
The worst he can do is break W ~> L where L is someone he ranked lower 
than W. But he can't gain anything by doing this, since he prefers W to 
every L.

Thus no voter who prefers some A to W can introduce A to the resistant 
set by burial. Hence W is unburiable. More generally, nobody preferring 
a candidate outside the resistant set to the winner can insert that 
candidate into the resistant set by burying.

As for compromising:

Suppose honest is A>B>W>C>D. Let W be the winner and sole resistant set 
member. Compromising for B (B>A>W>C>D) could establish B ~> X for any X 
ranked below B on the compromise ballot. This happens if B was kept from 
disqualifying X due to not clearing the bar in a sub-election containing 
at least all of A, B, and X. Similarly, it could break A ~> B for any A 
originally ranked higher than B.

Now since W is the sole member of the resistant set, there's a 
disqualification path from W to every other candidate. So a compromiser 
who wants B elected can't just establish B ~> W. That's impossible 
because it would produce a cycle (W ~> ... ~> B ~> W), and we've 
established that the relation is acyclical.

So it would seem (???) that the path from W to B has to have A 
immediately prior, i.e. W ~> ... ~> A ~> B. Then we can get a shot at 
getting B elected by breaking A ~> B to introduce B to the resistant 
set; or force B's election by both breaking A ~> B and establishing B ~> W.

But the simulations seem to suggest that doing this is very hard. I 
don't know why, though.

Here's a typical manipulability sim result for 97 voters 5 candidates 
impartial culture under the constraint that the honest election has only 
a single member of the resistant set, and using two methods that pass 
Resistant:

Resistant,Schulze:

Ties: 0 (0)
Of the non-ties:

Burial, no compromise:  0       0
Compromise, no burial:  2802    0.05604
Burial and compromise:  0       0
Two-sided:              341     0.00682
Other coalition strats: 0       0
==========================================
Manipulable elections:  3143    0.06286

IRV:

Burial, no compromise:  0       0
Compromise, no burial:  2804    0.05608
Burial and compromise:  0       0
Two-sided:              0       0
Other coalition strats: 160     0.0032
==========================================
Manipulable elections:  2964    0.05928

The picture when we force each honest election to have multiple 
candidates in the resistant set is much more lively, showing 
distinctions between strategy resistant methods:

Benham:

Burial, no compromise:  7599    0.15198
Compromise, no burial:  21939   0.43878
Burial and compromise:  1407    0.02814
Two-sided:              6       0.00012
Other coalition strats: 7194    0.14388
==========================================
Manipulable elections:  38145   0.7629

IRV:

Burial, no compromise:  0       0
Compromise, no burial:  31767   0.63534
Burial and compromise:  0       0
Two-sided:              0       0
Other coalition strats: 9679    0.19358
==========================================
Manipulable elections:  41446   0.82892

Since a little over half the 97 voter 5 candidate IC elections have 
singular resistant sets, it seems that this "singular resistant set" 
effect explains a lot of the simulation strategy resistance: controlling 
for it (by removing it) pushes the strategy resistant methods up to much 
higher manipulability levels, as shown. But more about such things 
later; this is long enough!

-km