[EM] Clone Free Copeland

[Forest Simmons]

A while back we tried something similar to this but couldn't quite get a
monotonic version of clone free Copeland..

Copeland elects the candidate with the greatest number of pairwise
victories. Copeland is monotonic.  To make it clone free we weighed each
victory with the probability that the defeated candidate would have been
elected in a random ballot election, i.e. the percentage of first place
votes (counted fractionally in case of equal top).  We got so close, but no
matter how we wrestled with it, monotonicity remained just out of reach.

To make a long story short, the key is to count a mere victory with half
the weight of a full covering victory.

We intend to define a way of assigning a score to each candidate, and then
the candidate with the highest score is elected.

For a typical candidate X the score is calculated as follows.  Let S1 be
the set of candidates that are covered by X, including X itself, and let S2
be the set of other candidates that are pairwise beaten by X, but not
covered by X.

For each candidate Y, let p(Y) be the probability that Y would be elected
by random ballot.

Let p1 be the sum of probabilities p(Y) for Y in S1, and let p2 be the sum
of  p(Y) for Y in S2. Then the score for X is defined as p1 + (1/2)p2 .  In
other words the non-covering defeats count only half of the (stronger)
covering defeats.

Note that the winner (the candidate with the highest score) will be
uncovered, just like the Copeland winner, because the score of a covered
candidate will be only part of the sum of a candidate that covers it.

The hard part is monotonicity.  Here we go:

Suppose that W is the winner, i.e. the one with the greatest value of s1 +
.5s2, and suppose that W, by moving up the ranks on a ballot either
achieves an additional pairwise victory, or (2) increases its probability
p(W).  We claim that W will still have the highest score.

First consider case(1) where W now defeats some candidate Y which it didn't
defeat before the move. This will increase the score for W, so W will
continue to be the winner unless some other candidate Z suddenly upgrades
from mere victor over some candidate V to covering V.  This can only happen
if V = Y and W defeats Z, otherwise Z would have already covered V before
the change.

So the new victory adds at least p(V)/2 to the score of W, and at most
p(V)/2 to the score of Z  So W stlll wins.

In case (2) let deltaP be the increase in p(W).  This increase will be
offset by a decrease of the same amount in p(T) where T is the candidate at
the top that was displaced by W.

Since W is covered by itself, the score of W increases by deltaP.  However,
if W pairwise beats T,then W's score will be lowered either by deltaP or by
half of that depending on whether or not W covers T.

So far so good, but remember that any candidate that pairwise beats W will
get its score increased by either deltaP or half deltaP depending on
whether or not Z's defeat of W is by covering. But it cannot be by covering
because any winner W is uncovered, as already remarked fom the beginning.

So we are down to the end game:  Candidate Z gets its score augmented by
half deltaP, which is OK only if W doesn't cover T, which would have a net
effect of zero on W's score and a positive increase in Z's score,
potentially allowing Z to be the new winner.

There are two subcases to consider: (i) T pairwise defeats Z, and (ii) Z
defeats T.

In the first case we have W covers T and T beats Z, so W beats Z, and Z's
score is not increased by W's move up the ranks.

In the second case Z's score is lowered by half deltaP due to the decrease
in p(T).


In sum, replacing T by W, does not decrease W's score, and does not
increase  the score of any other candidate Z more than it increases the
score of W.

I hope that Kristofer and others with lots of patience will check this
monotonicity argument (or find a simpler one) carefully before we announce
the result to a broader audience!

If you find an unfixable flaw, break it to me as gently as possible😓😀

Thanks!
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20200201/24d7e8ea/attachment.html>