A cloneproof fpA-fpC method?
(Sending this to the list as the people I sent it to didn't reply to me
with any obvious defects to the method :-)
I read Tideman's original paper about ranked pairs a few days ago, and
one thing stuck in my head: he said that minmax, which is not
cloneproof, calculates its objective value over one candidate at a time,
whereas ranked pairs does it for each pairwise preference. And that got
me thinking. So I came up with what might be a cloneproof version of fpA
- max fpC. I thought I'd ask you about it before I post it on EM, to see
if there's anything I missed.
Three-way ranked pairs: (Or perhaps "ranked triples"?)
The general idea is to first break three-cycles according to fpA-fpC,
and then, once these are broken, continue with ordinary RP. So the
method has two stages, call them the triple stage and the pairwise
stage. The triple stage is run first, then the (ordinary RP) pairwise stage.
Triple stage:
I'll explain this in a way that's slower but easier to understand.
There's an obvious performance improvement but I don't want to clutter
up my explanation too much :-) Say there are v voters and c candidates.
Take all permutations of three candidates out of c, (X, Y, Z), so that
there's an X>Y>Z>X cycle. Assign each such permutation a magnitude,
fpX{X, Y, Z} - fpZ{X, Y, Z}, and insert them into a list. Sort the
list by descending magnitude.
The notation here means that we're eliminating all candidates except X,
Y, and Z, before calculating the first preference votes. I.e. we're
using the subelection {X, Y, Z}. (This costs us ranked pairs' O(n^2)
summability, unfortunately; we're now O(n^3).)
Next, go down this list from greatest magnitude to least. Do the
following steps for each permutation (X, Y, Z) in this order:
- If, when considering previous pairwise defeats that have been locked,
(X, Y, Z) is no longer an X>Y>Z>X cycle, skip.
- Otherwise lock X>Z, overriding the Z>X leg of the cycle.
Once all permutations have been processed, proceed as ordinary ranked
pairs, retaining the locked pairwise defeats from the triple stage.
For instance, in a three-candidate ABCA cycle where A is the fpA-fpC
winner, we get:
Triple stage:
(A, B, C): lock A>C
(B, C, A) and (C, A, B): skipped because they're no longer a cycle
Pairwise stage:
A>B: lock
B>C: lock
everything else, skipped
outcome is A>B>C.
Why may this be cloneproof? The RP part is already cloneproof, so let's
consider the triple stage. Note that the definition of clones implies
that if Ak is a clone of A, then Ak > X iff A > X.
Suppose we have the triple (A, B, C).
Cloning A, we should consider which triples may exist out of
(A1, A2, A3), (A1, A2, C), (A1, B, A2),
(Ak, B, C), where the numbered As, as well as Ak,
are members of the A clone set.
(A1, A2, A3) can't affect the outside-of-A preference order
because it can only lock A1>A3. So no problem there.
(A1, A2, C) is impossible because we can't simultaneously have
C > A1 and A2 > C, due to how clones are defined.
(A1, B, A2) is similarly impossible because we can't have both
A1 > B and B > A2.
(Ak, B, C) will have the exact same result as (A, B, C), so the
relation between clones and non-clones will be the same
as that between the original uncloned candidate and the
non-clones.
The cases where B is cloned or C is cloned are completely
analogous.
I think this also passes ISDA. It might even pass LIIA, but I'm not
quite as sure about that. (Sketch idea for the latter: suppose the loser
is X and the second to loser is Y. Then we locked Y>X, at some point; if
it's the RP stage, we already know we pass LIIA. If it's the triple
stage, that means there's a three-cycle (Y, W, X) for some W, that
affirmed/locked Y>X, with Y>W already set. But if X doesn't exist, then
there's nothing to lock, and thus nothing changes. But I haven't
verified this.)
It probably isn't fully resistant set compliant, but it is with a
three-candidate or smaller Smith set. For ties, I'd probably use random
voter hierarchy and sort (A, B, C) higher than (D, E, F) if A>C in the
RVH but not D>F. Equal-rank I'd just ignore voters who rank A=C top, and
count A=B voters towards A and B=C voters towards C.[1]
You could possibly generalize BPW by replacing fpA{A,B,C}-fpC{A,B,C}
with fpB{A,B,C}. Or make a cardinal strength-of-preference
cycle-breaker by letting the magnitude of (A, B, C) be A's rating when
every ballot is linearly scaled to have its favorite of the three rated
max and its least favorite of the three rated min.
What do you think?
-km
[1] I think this is the same as doing ER-whole. You could also do
ER-fractional, but I don't know what criteria it would secure or break.
What does "fpA-fpC" mean?
On 21/10/2024 9:16 pm, Kristofer Munsterhjelm wrote:
(Sending this to the list as the people I sent it to didn't reply to
me with any obvious defects to the method :-)
I read Tideman's original paper about ranked pairs a few days ago, and
one thing stuck in my head: he said that minmax, which is not
cloneproof, calculates its objective value over one candidate at a
time, whereas ranked pairs does it for each pairwise preference. And
that got me thinking. So I came up with what might be a cloneproof
version of fpA - max fpC. I thought I'd ask you about it before I post
it on EM, to see if there's anything I missed.
Three-way ranked pairs: (Or perhaps "ranked triples"?)
The general idea is to first break three-cycles according to fpA-fpC,
and then, once these are broken, continue with ordinary RP. So the
method has two stages, call them the triple stage and the pairwise
stage. The triple stage is run first, then the (ordinary RP) pairwise
stage.
Triple stage:
I'll explain this in a way that's slower but easier to understand.
There's an obvious performance improvement but I don't want to clutter
up my explanation too much :-) Say there are v voters and c candidates.
Take all permutations of three candidates out of c, (X, Y, Z), so that
there's an X>Y>Z>X cycle. Assign each such permutation a magnitude,
fpX{X, Y, Z} - fpZ{X, Y, Z}, and insert them into a list. Sort the
list by descending magnitude.
The notation here means that we're eliminating all candidates
except X, Y, and Z, before calculating the first preference votes.
I.e. we're using the subelection {X, Y, Z}. (This costs us ranked
pairs' O(n^2) summability, unfortunately; we're now O(n^3).)
Next, go down this list from greatest magnitude to least. Do the
following steps for each permutation (X, Y, Z) in this order:
- If, when considering previous pairwise defeats that have been
locked, (X, Y, Z) is no longer an X>Y>Z>X cycle, skip.
- Otherwise lock X>Z, overriding the Z>X leg of the cycle.
Once all permutations have been processed, proceed as ordinary ranked
pairs, retaining the locked pairwise defeats from the triple stage.
For instance, in a three-candidate ABCA cycle where A is the fpA-fpC
winner, we get:
Triple stage:
(A, B, C): lock A>C
(B, C, A) and (C, A, B): skipped because they're no longer a
cycle
Pairwise stage:
A>B: lock
B>C: lock
everything else, skipped
outcome is A>B>C.
Why may this be cloneproof? The RP part is already cloneproof, so
let's consider the triple stage. Note that the definition of clones
implies that if Ak is a clone of A, then Ak > X iff A > X.
Suppose we have the triple (A, B, C).
Cloning A, we should consider which triples may exist out of
(A1, A2, A3), (A1, A2, C), (A1, B, A2),
(Ak, B, C), where the numbered As, as well as Ak,
are members of the A clone set.
(A1, A2, A3) can't affect the outside-of-A preference order
because it can only lock A1>A3. So no problem there.
(A1, A2, C) is impossible because we can't simultaneously have
C > A1 and A2 > C, due to how clones are defined.
(A1, B, A2) is similarly impossible because we can't have both
A1 > B and B > A2.
(Ak, B, C) will have the exact same result as (A, B, C), so the
relation between clones and non-clones will be the same
as that between the original uncloned candidate and the
non-clones.
The cases where B is cloned or C is cloned are completely
analogous.
I think this also passes ISDA. It might even pass LIIA, but I'm not
quite as sure about that. (Sketch idea for the latter: suppose the
loser is X and the second to loser is Y. Then we locked Y>X, at some
point; if it's the RP stage, we already know we pass LIIA. If it's the
triple stage, that means there's a three-cycle (Y, W, X) for some W,
that affirmed/locked Y>X, with Y>W already set. But if X doesn't
exist, then there's nothing to lock, and thus nothing changes. But I
haven't verified this.)
It probably isn't fully resistant set compliant, but it is with a
three-candidate or smaller Smith set. For ties, I'd probably use
random voter hierarchy and sort (A, B, C) higher than (D, E, F) if A>C
in the RVH but not D>F. Equal-rank I'd just ignore voters who rank A=C
top, and count A=B voters towards A and B=C voters towards C.[1]
You could possibly generalize BPW by replacing fpA{A,B,C}-fpC{A,B,C}
with fpB{A,B,C}. Or make a cardinal strength-of-preference
cycle-breaker by letting the magnitude of (A, B, C) be A's rating when
every ballot is linearly scaled to have its favorite of the three
rated max and its least favorite of the three rated min.
What do you think?
-km
[1] I think this is the same as doing ER-whole. You could also do
ER-fractional, but I don't know what criteria it would secure or break.
Election-Methods mailing list - see https://electorama.com/em for list
info
On 2024-10-25 10:12, Chris Benham wrote:
What does "fpA-fpC" mean?
First preference for A minus first preference for C.
i.e. in a three-candidate election that's an ABCA cycle, elect the
candidate A whose first preferences minus the preferences of the one
beating him is maximized. (If there is a CW, just elect that CW.)
This has similarly low manipulability as the Condorcet-IRV hybrids while
being monotone. Later I found a connection between low manipulability
and electing from the resistant set. And sure enough, both
three-candidate IRV and fpA-fpC elect from this set.
The problem is that it's only defined for three candidates. So I've on
and off been playing with extensions that would generalize to more
candidates while retaining monotonicity and some of the strategy resistance.
But none of the generalizations have been cloneproof; even my best
attempt so far (Friendly Cover) is only independent of twins (the way
minmax is). This extension, however, might just be cloneproof and have
some nice Smith-independence properties as well.
Unlike the Condorcet-IRV methods, it (probably) doesn't elect from the
resistant set in general, but it does with a Smith set of three or
fewer. I still haven't found a monotone method that always elects from
the resistant set, but I'm not going to discard partial results like
this method for that reason.
-km