[EM] Chain Climbing methods

[Jobst Heitzig]

Dear folks!

Forest's idea to combine approval scores and defeats, which he used in the Needle method, made me think again of how to improve ROACC. Here's the result: Four new methods which all use ROACC's idea of "chain climbing" but have better properties.

Let me first recall ROACC's definition:

ROACC (Random Order Acrobatic Chain Climbing): 
--------------------------------------------------------------
1. Sort the candidates into a random order. 
2. Starting with an empty "chain of candidates", consider each candidate in the above order. When the candidate defeats all candidates already in the chain, add her at the top of the chain. The last added candidate wins. 

The good thing about ROACC is that it is both 
- monotonic and 
- the winner is in the Banks Set, 
in particular, the winner is uncovered and thus the method is Smith-, Pareto-, and Condorcet-efficient. 

Until yesterday ROACC was the only way I knew of to choose an uncovered candidate in a monotonic way. But Forest's idea of needles tells us that it can be done also in another way. The only difference is that in step 1 we use approval scores instead of a random process:

TACC (Total Approval Chain Climbing):
------------------------------------------------
1. Sort the candidates by increasing total approval.
2. Exactly as above.

The main differences in properties are: TACC is deterministic where ROACC was randomized, and TACC respects approval information where ROACC only uses the defeat information. And, most important: TACC is clone-proof where ROACC was not! That was something Forest and I tried to fix without violating monotonicity but failed. More precisely, ROACC was only weakly clone-proof in the sense that cloning cannot change the set of possible winners but can change the actual probabilites of winning. With TACC, this makes no difference since it is deterministic and so the set of possible winners consists of only one candidate anyway.

Let us study shortly why these two methods are monotonic:
Let us assume that the actual winner X is raised on a some individual ballots by moving either the approval cutoff or another candidate from directly above X to directly below X. Then what can happen is twofold: First, the order in step 1 either does not change or does only change in that X gets moved up one position. Second, the defeat do not change or do only change in that X now defeats some candidate Y which she was defeated by before. In either case, X still must win: It was the last candidate added to the chain. The new chain developes exactly as before: As the order did not change left of X, the chain evolves just as before until the original position of X. If X did not change position, it still defeats all candidates in the chain and so gets added. If X did change position with Y, then Y was beaten by X or some other candidate already in the chain since it was not added to the chain originally. If it is added now, it must hence be beaten by X, so that X still gets ad!
 ded after Y was added. In either case, when X was considered, the resulting chain is the old one except that perhaps Y is added. As no later candidate beat was added originally and X beats everything it beat before, also now no further candidate can be added, so that X is again the winner. QED.

What do we learn from that? The crucial point in this proof is that by raising X, the only change to the order in step 1 can be that X is raised there, too, but the relative position of the other candidates in the order cannot change! 

Having learnt this, we can design other clone-proof variations of ROACC, both deterministic and randomized:


The first uses Borda counts for the initial sorting:

TBCC (Total Borda Chain Climbing):
--------------------------------------------
1. Sort the candidates by increasing total Borda score.
2. Exactly as above.


The second uses a Tie Breaking Rank Order based on rankings:

RBRCC (Random Ballot Ranking Chain Climbing):
-------------------------------------------------------------
1. Sort the candidates as follows: Pick a random sequence of ballots. Sort X before Y if on the first ballot which decides between X and Y, X is below Y.
2. Exactly as above.


The third uses approval cutoffs instead of rankings:

RBACC (Random Ballot Approval Chain Climbing):
-------------------------------------------------------------
1. Sort the candidates as follows: Pick a random sequence of ballots. Sort X before Y if on the first ballot which has the approval cutoff between X and Y, X is below Y.
2. Exactly as above.


All these are clone-proof since the process of finding the initial order is clone-proof (where the random order of ROACC is not!), but I omit the proof here.

Except TBCC, all these methods do also fulfill Steve's "Immunity from 2nd place complaints": 
When the winner X is removed from all ballots, the defeat and approval structure of the rest remains the same, hence the order in step 1 remains the same except that X is removed, hence the chain developes as before until the original position of X. All further added candidates beat all candidates in the original chain except X, hence they are beaten by X. When no further candidate is added, the last added is beaten by X since X was added after it before its removal. Hence the new winner is defeated by X. QED.
As a drawback, all the methods seem to violate IPDA.


The last variation (RBACC) is my current favourite. It is
- simple
- monotonic
- Banks-, Pareto-, Smith-, and Condorcet-efficient
- uncovered
- clone-proof
- aware of preference strength
- immune from 2nd place complaints
- sufficiently randomized to make the strategic production of fake CWs risky,

For those who want determinism, I recommend TACC which has all those properties except the last one.

So, what do you think?

Jobst



PS: Forest, I can't send you e-mail but get a delivery error! 
__________________________________________________________
Mit WEB.DE FreePhone mit hoechster Qualitaet ab 0 Ct./Min.
weltweit telefonieren! http://freephone.web.de/?mc=021201