[EM] Clone Free Copeland

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view

[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😓😀


Election-Methods mailing list - see https://electorama.com/em for list info