<div dir="ltr">Here's a copy of Jobst's original post on TACC, "Total Approval Chain Climbing," including his proof of monotonicity. In addition he describes some closely related strategy resistant non-deterministic versions.<br>
<br>>From: Jobst Heitzig <heitzig-j <at> <a href="http://web.de" target="_blank">web.de</a>><br>
Subject: <a rel="nofollow" href="http://news.gmane.org/find-root.php?message_id=896927002%40web.de" target="_blank">Chain Climbing methods</a><br>
Newsgroups: <a href="http://news.gmane.org/gmane.politics.election%2dmethods" target="_blank">gmane.politics.election-methods</a><br>
Date: 2005-03-04 13:15:29 GMT
(9 years, 6 weeks, ago)<br>
<pre>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:
<b style="background-color:rgb(255,255,102)">TACC</b> (Total Approval Chain Climbing):
------------------------------------------------
1. Sort the candidates by increasing total approval.
2. Exactly as above.
The main differences in properties are: <b style="background-color:rgb(255,255,102)">TACC</b> is deterministic where ROACC was randomized, and <b style="background-color:rgb(255,255,102)">TACC</b>
respects approval information where ROACC only uses the defeat information. And, most important: <b style="background-color:rgb(255,255,102)">TACC</b>
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 <b style="background-color:rgb(255,255,102)">TACC</b>,
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 ch
ain 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 <b style="background-color:rgb(255,255,102)">TACC</b> which has all those properties except the last one.
So, what do you think?
Jobst
</pre><br><div><div class="gmail_extra"><br><br><br></div></div></div>