[EM] Friendly Cover, a burial-resistant monotone almost cloneproof method

[Kristofer Munsterhjelm]

Here's a method that generalizes fpA - sum fpC to pass:
	- Landau (with a certain provision)
	- monotonicity
	- independence of twins (a weaker clone independence)
	- output scores (not just rankings)
and probably also passes DMTCBR and a weaker DMTBR (as yet unnamed 
criterion). My simulator indicates as such, but I don't have a proof 
yet. In addition, unlike IRV, it's summable.

Let's call it Friendly Cover for now, for lack of a better name. Any 
name suggestions would be appreciated!

(In addition, Friendly Cover passes all the three-candidate criteria 
that fpA-fpC does, like the chicken dilemma criterion.)

This is quite a step towards getting strategy resistance, clone 
independence, and summability!

I'll describe a simple version, then a more complex one, and then do 
some proofs for the criteria.

First, the simple version. It has two problems, one of which a patch 
handles; I'll give an explicit version later that incorporates that 
patch more directly.

For any candidate X:
	Let X's defeaters be the candidates who beat X pairwise,
	Let X's intermediates be the candidates who beat some defeater and are 
not defeaters themselves,
	and let X's friends be everybody else (including X himself).

	Then X's score is the sum of first preferences of X's friends, minus 
the sum of first preferences of X's defeaters.

In a three candidate A>B>C>A cycle, this reduces to fpA - fpC because C 
is A's defeater and B is an intermediate, so the friend set is only A.

However, there are two problems. First, we only get Landau if every 
candidate gets at least one first preference vote. Otherwise it's 
possible that A is the CW and has no first preferences, and B beats 
everybody but the CW and, despite being beaten by the CW, ties him by 
score. That happens because the only defeater of B is A, and A has zero 
first preferences, so B's score is A's score minus zero.

I don't know how to robustly handle that yet, so I'm going to leave it 
for now. Perhaps funny is that people who make a big deal out of core 
support could see this as a feature and not a bug :-)

Second, which *can* be fixed: if A ties C pairwise, C's defeat set 
contains B but not A, and A's friend set also contains B, then raising A 
on a B>A ballot could give C an additional point while not changing A's 
score, thus violating monotonicity. To fix that, we need this patch:

	Before calculating X's score, remove from X's friend set everybody 
who's a defeater of someone who X ties pairwise.

But that's fairly inelegant, so instead I'll give an explicit version 
that's equivalent in the absence of pairwise ties. Thanks to Forest 
Simmons for discovering that equivalence:

For any candidate X:
	Let X's defeaters be the candidates who beat X pairwise,
	Let X's friends be everybody X weakly covers,

	and the score is calculated as above.

Ordinary covering is similar to "A defeats B", i.e. you can't be 
covering someone and that someone also be covering you. Weak covering is 
more like "A defeats or ties B": you can be weakly covering someone else 
who is also weakly covering you, and that means you, in the covering 
sense, tie that other candidate.

The weak covering relation is defined like this: "A weakly covers B if A 
beats everybody B does, and B is beaten by everybody A is beaten by, 
pairwise". (Note that A covers himself.)

Hence the "Cover" in "Friendly Cover". It can be shown that if there are 
no pairwise ties, X's friend set is exactly X and everybody X covers in 
the ordinary Landau sense, but I don't want to clutter up the post.

This solves the problem we patched out because A can't cover B if B is a 
defeater of some C that A ties pairwise, because then A doesn't beat 
everybody B does (in particular, A doesn't beat C!)

----

Proofs:

Proving Landau compliance involves a lot of nitty-gritty details, so 
I'll show it for a related strict covering that differs from 
Landau/Fishburn when there are ties. I think it can be shown for actual 
Landau too, but again, I don't want to clutter up the post; just ask me 
if you'd like the full thing.

First assume that everybody has a first preference. That's the caveat I 
mentioned at the start.

Let A strictly cover B if A weakly covers B, A beats B pairwise, and 
either A beats someone B doesn't, or B is beaten by someone A isn't. And 
let the uncovered set be everybody who isn't strictly covered by anyone.

Suppose A strictly covers B. If B is beaten by one more candidate than 
A, then B's defeat set contains more candidates than A's. And since 
covering relations are transitive (if A covers B and B covers C, then A 
covers C), A's friend set is no smaller than B's. Hence B's sum over 
defeaters is larger than A's, and B's sum over friends is at most equal 
to A's. Thus A outscores B, as desired.

If, on the other hand, A beats one more candidate than B (but both A and 
B are beaten by the same set), then since A beats B pairwise, A weakly 
covers B but B doesn't weakly cover A. So A's friend set contains A 
himself as well as everybody weakly covered by B, but B's friend set 
doesn't contain A. Hence B's sum over defeaters is the same as A's while 
A's sum over friends is greater than B's, so again A outscores B.


Monotonicity is pretty easy: raising A can't make anyone appear in A's 
defeater set who wasn't there before, and can't remove someone from 
someone else's defeater set. Since fpA - fpC itself is monotone, that's 
all we need.


Independence of twins: this is a weaker clone independence that minmax 
also passes. It says that if we replace a candidate X by two clones X1 
and X2, then the outcome can't change.

First, let's show that there's no teaming incentive. Suppose A wins and 
we clone A. Since everybody who beats A also beats all the clones, this 
can't remove any defeaters of A from the clones' defeater sets. And 
since the clones all beat candidates who the original A beats, it can't 
introduce new friends to any of the clones. Since the sum over defeaters 
can't decrease and the sum over friends can't increase, the A clones' 
scores can't increase.

Now suppose that the winner is X and we clone Y. If Y is a defeater of 
X, then all the clones will be defeaters of X. If Y is covered by X, 
then every clone will also be covered by X. So cloning Y doesn't affect 
X's score. Since we know from the previous paragraph that it can't 
increase Y's score, Y can't go from loser to winner by being cloned. So 
there is no teaming incentive (and this is fully general, i.e. not just 
for twins).

Now suppose A wins and we replace A with two candidates A1 and A2. 
Suppose also without loss of generality that A1 beats or ties A2 
pairwise. Then if A1 ties A2, both weakly cover each other. Since they 
beat the same non-clone candidates and are beaten by the same non-clone 
candidates as A, all that happens is that their friend sets go from 
containing A to containing A1 and A2. And since the sum of clones' first 
preferences is the same as the original candidate's first preferences, 
the clones' scores don't change. If A won, both clones will still win; 
if A lost, both clones will still lose.

If A1 strictly beats A2, then A1 weakly covers A2 but not vice versa. So 
A1's score is the same as A used to be while A2's score will at most be 
equal to A1 (and may be lower). In any case, if A won, A1 will win after 
the cloning, and if A lost, both clones will still lose afterwards.

The problem is that in the more general case, it's possible that A could 
be cloned into A1, A2, and A3, who are in a cycle (i.e. A1>A2>A3>A1). 
Then each clone gets one of the other clones into his defeat set, which 
lowers all the clones' score and may make them lose. So if you have at 
least five candidates and a Landau set with three clones in it, there 
could be trouble.

-km