[EM] Resistant set results

[Joshua Boehme]

Apologies if this is a naive question, but based on that definition is the resistant set affected by clones? Consider...

4 A>B
3 B

A ~(AB)~> B and not vice versa, so A ~> B

Now add A', a clone of A...

2 A'>A>B
2 A>A'>B
3 B

A~(AA'B)~>B isn't true, so A ~> B no longer holds


Allowing tied rankings doesn't solve it, since A and A' could be from different wings of one major party -- so voters have true preferences between them -- while B is from another major party.


On 12/9/23 12:13, Kristofer Munsterhjelm wrote:
> 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
> ----
> Election-Methods mailing list - see https://electorama.com/em for list info