election-methods@mailman.electorama.com

Technical discussion of election methods

View all threads

Some ideas about cloneproof resistant set extensions

KM
Kristofer Munsterhjelm
Wed, Dec 20, 2023 7:53 PM

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

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