[EM] A cloneproof fpA-fpC method?

[Chris Benham]

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