[EM] Some ideas about cloneproof resistant set extensions

[Kristofer Munsterhjelm]

I have been thinking a bit about what Joshua said about the resistant 
set not being cloneproof, and trying to find some extensions that might 
get us at least part of the way there.

Here's a very simple one that *should* work, using solid coalitions:

Say that a set S of candidates of cardinality |S| collectively beats 
another candidate X if, in every sub-election of k candidates, where all 
of the candidates in S, as well as X appear, S is a solid coalition of 
support 1/(k-|S|+1).

This is a relatively brute-force approach, but the idea is that if a 
candidate A is cloned into multiple candidates, then in every 
sub-election where A used to disqualify B, now the clone set does so 
collectively. Since we don't need to know which of the clone set 
disqualifies B, all we need to know is that someone in that set 
disqualifies B to bar B from the resistant set.

The support equation is chosen so that it reduced to 1/k when S is a 
single candidate, hence generalizing from the ordinary disqualification 
relation. To be absolutely sure that it works, I would have to prove 
that the extended relation is acyclical in the sense that the resistant 
set can never be empty. In addition, it's a complete pain to actually 
calculate, at least in the straightforward manner, since one would have 
to check 2^n-2 subsets to  properly map the disqualification relation.

Another possibility that is a little more elegant and may end up 
equivalent is this:

Let *S* = {A_1, ..., A_k} be a some set of candidates (using asterisks 
to distinguish from a candidate).

Let *S* ~> B, with B not a member of S, if, in every sub-election 
containing exactly one member of S, as well as B, that member has more 
than 1/k first preference support.

This works because if A is cloned, then these clones are all adjacent 
pairwise, so the "exactly one member of S" construction undoes the 
cloning. I say it's at least a little more elegant because if this is 
not just a duplication of the solid coalition idea, then it should be 
more accommodating of near-clone sets, while if it is, it doesn't need 
to mention solid coalitions, as it just uses the already-existing machinery.

Some other ideas that I didn't get as far using:

The obvious fpA - sum fpC inspired solution would be to use first 
preferences, e.g. {A, B, C} ~> D whenever, in any sub-election 
containing all four candidates, the sum of first preferences of 
candidates in this set exceeds 1/(k-|S|+1).

But intuitively it feels like this is too loose, that it should be 
possible to create collective disqualifications against every candidate. 
Granted, I don't have any proof of this except for a hunch based on my 
2009 post on my semiproportional Bucklin method. So maybe it could be 
investigated after all? The relation should be as simple as is possible 
without producing cycles, and this definitely is simpler than the solid 
coalition stuff.

Something I did reject was the idea of solving cloning by a chain of 
disuqalifications that partition the subelections, e.g. something like

A ~(!C)~> B ~(!A)~> C

if A disqualifies B in sub-elections not containing C, and then B 
disqualifies C in sub-elections not containing A, which could then be 
made to be a sort of "A ~> C indirectly". The idea here is if A and B 
are clones, then the B ~(!A)> C preserves the pre-cloning relation, 
while the A ~(!B)~> part decides which clone is going to win.

But that doesn't work because it's possible to create elections where no 
disqualifications happen. E.g. my usual go-to, the LCR, tweaked a bit:

34: L>C>R
30: R>C>L
7: C>R>L
3: C>L>R

Neither L nor R can disqualify C since C is the CW. And C can't 
disqualify any of them because he doesn't have >1/3 first prefs in the 
full election. And L can't disqualify R nor R L because the pairwise 
contest between L and R is a tie.

If the candidate to be cloned were to be cloned in such a way, then 
there would be no way to make any path through the clone set to 
indirectly beat someone else. Thus this indirect idea fails: resistant 
beatpaths don't work.

-km