[EM] Four-candidate fpA-fpC extension

[Kristofer Munsterhjelm]

Here are some patterns to an idea to extend fpA-fpC to four (and more)
candidates that I've been playing with lately. It may be useful as a
block towards something that more generally passes DMTBR and either
summability or monotonicity, and may give some ideas on how to
cloneproof fpA-fpC.

Start with an eligible set of every candidate. Then do fpA-fpC on every
three-candidate subset of the eligible set. Let the new eligible set be
the union of every non-losing candidate. Repeat until either the
eligible set doesn't change ("cycle") or the set is reduced to three
candidates or fewer. In the latter case, do fpA-fpC or majority rule on
the set (if it's three or two candidates respectively).

I'm not sure how to deal with the cycles, so it's an incomplete method.
But for four candidates up to 7 voters, it passes DMTBR unless there's a
cycle either before or after burial. For up to 5 voters, it passes
monotonicity, but it fails for seven voters, e.g.:

2: A>B>C>D
1: A>B>D>C  <-- ballot X
1: C>B>D>A
1: C>D>A>B
2: D>A>B>C

D wins, then raise D on ballot X:

2: A>B>C>D
1: A>D>B>C
1: C>B>D>A
1: C>D>A>B
2: D>A>B>C

then A wins.

The partial clone independence idea when the winner is a DMT candidate
is that suppose we have a three-candidate election and then clone the
winner and DMT candidate A into A1 and A2, then A1 will win in any (A1,
X, Y), and ditto for A2, because A won initially. And in a contest that
contains both, (A1, A2, X), it doesn't matter if one of the As is
eliminated because then we just reduce to the before-cloning case.

So suppose no A is eliminated. Then (A1, A2, X) must eliminate X, so the
final set (starting with four candidates and eliminating at least one)
is either (A1, A2) or (A1, A2, Y) for some other Y. If the former, then
it doesn't matter which of the As pairwise defeat the other. If it's the
latter, then there can't be a cycle since A was a DMTC. So whichever A
clone beats the other pairwise wins.

The loser cloning example follows from that the method passes DMT.

The loser clone independence could be made stronger if the method takes
the union of the winners of three-elections instead of the non-losers.
This also cuts down on the number of cycles, but it in return makes
monotonicity violations more severe.

E.g. suppose A wins and B is cloned. Then WLOG let B be among the
candidates removed from the eligible set in the first step, before
cloning. Then no (B1, X, Y) or (B2, X, Y) three-election can have a B
candidate as the winner, because these give the same result as (B, X, Y)
did before the cloning, and we were assuming B was eliminated there.
Hence the only way a B can be retained is if X is not the winner in the
(B1, B2, X) election. But as we only have two clones, there can't be a
cycle, so whichever beats the other two pairwise must win. In
particular, this means that the winner, if it's one of the Bs, is always
the same B (the one who beats the other pairwise). Hence one of the Bs
will be eliminated and we have reduced to the (pre-cloning) base case.[1]

I'm not sure how DMTBR is retained. The obvious proof angle is that
because DMTBR is satisfied for fpA-fpC, the burial can't get the
buriers' candidate elected in any of the three-elections. So in the
"everybody but the winners are eliminated" variant, by the assumption
that the buriers' candidate didn't win before the burial, he won't win
after either.

But that doesn't work for the "nonlosers are retained" variant because
even if A can't be turned into a loser in (A, B, C) by B>A voters
burying A under C, it could change the loser from B to C and thus
protect B from elimination.


If I could rigorously prove DMTBR in the absence of cycles, and I had a
way of dealing with the cycles in a way that preserves it, then I would
have a summable DMTBR method, which in itself would be a new combination
of properties. ... even if it weren't monotone.

This isn't anywhere near a complete method, but perhaps there's
something that can be built upon in it.

-km

[1] If there are more than two clones, we could imagine an election
where (B1, B2, X) elects B1, (B2, B3, X) elects B2, and (B3, B1, X)
elects B3, hence preserving the cycle.