[EM] A cloneproof fpA-fpC method?

[Kristofer Munsterhjelm]

(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.