[EM] Problem solved (for pure rank ballots): ICC & AFB incompatible (essentially)

Warren Smith wds at math.temple.edu
Wed Jan 24 15:22:21 PST 2007


Hre is a way in which range voting is superior to every pure-rank-order method

Theorem:
These criteria, for a single-winner voting system based on
pure-rank-order-ballots, are incompatible:
1. AFB = avoids favorite betrayal
2. ICC = immune to candidate cloning
3. reduces to simple majority vote in 2-candidate case
4. symmetry under candidate renaming
5. tiebreaks (if any) are random equally likely [this axiom probably may be weakened a lot]
6. adding a new candidate to the election whom all voters unanimously rank unique-bottom, 
does not change the winner.

Proof:
Consider these 3 votes:
A>B>C
C>A>B
B>C>A
by symmetry axiom 4 this is a perfect 3-way tie.
However we shall argue under axioms 1-3 that A must win, which is a 
contradiction that establishes the proof.
If A does not win, then B or C does.

If B wins, then the C-voter would betray C to vote A>C>B getting
A>B>C
A>C>B
B>C>A
and then {B,C} is a clone set and hence by axioms 2 and 3 then A must win
and hence the betrayal worked and hence we get a contradiction with axiom 1.
[The alternate dishonest vote, which is not a C-betrayal, C>B>A,
would not work since B still would win:
A>B>C
C>B>A
B>C>A
now {B,C} is a clone set, so by axioms 2 & 3 B or C must win;
but winner here must be B and not C (and not BC tie) because if it were C 
or BC tie then the A-voter could betray: B>C>A causing 
B>C>A
C>B>A
B>C>A
in which case B must win by axiom 6.]

If C wins, or if BC tie, then the A-voter can betray A to vote B>A>C getting
B>A>C
C>A>B
B>C>A
whereupon {A,C} is a clone set and hence by axioms 2 and 3 then B must win
and hence the betrayal worked and hence we get a contradiction with axiom 1.
[The alternate dishonest vote which is not an A-betrayal, A>C>B would not work since
C still would win when
A>C>B
C>A>B
B>C>A
because {A,C} is a winning clone set
and if A wins (or AC tie) then B>C>A voter betrays: C>A>B to 
make C win
A>C>B
C>A>B
C>A>B
by axiom 6.]
Q.E.D.

Remark 1.
I do not presently know if this theorem can be extended to permit equalities in vote-rankings.

Remark 2.
Antiplurality voting obeys all 6 axioms except for #2 (and #6).
You can make a version of antiplurality voting that obeys #6 by
making a last-place-vote count -1, a second-last-vote count -epsilon,
a third-last-vote count -epsilon^2, etc in the limit epsilon-->0+,
highest score wins.

Remark 3.
Schulze beatpaths voting obeys all 6 axioms except for #1.

Remark 4. 
Range voting obeys all 6 axioms if all range votes are
"normalized" so voters (obeying the recommendations for voting on the
http://rangevoting.org front page) always give the best candidate the top
score and the worst the bottom score in a 2-candidate election
[i.e. in practice with voters who are not idiots].
But with possible-idiot voters, range fails axiom #3 (which does not bother me).

So we have proven a sense in which range is superior to EVERY pure-rank-ballot voting
method, and using two of the most important voting criteria AFB and ICC.

Remaining Open question: what happens if we permit rank order votes to have EQUALITIES in them?
Are ICC and AFB still incompatible or do they become compatible?

(I thank Forest W. Simmons for inspiring me to work on this some more.)
Warren D Smith
http://rangevoting.org



More information about the Election-Methods mailing list