Puzzle #??: Independence from covered alternatives & monotonicity
Prove it is impossible for a singlewinner voting method based on rankorder ballots
(either deterministic or randomized) to exist
simultaneously satisfying i, ii, iii, iv:

"Independence from covered alternatives":
the winner is always a member of the
uncovered set –
and who it is, depends only on
the voterpreferences among the uncovered candidates.

"Monotonic":
if a voter raises candidate
X above Y (and makes no other changes, and no other voter changes their ballot),
that cannot decrease X's winning chances.

"Perfectsymmetry tiebreak responsiveness":
In a Ccandidate election featuring a
perfect symmetrical Cway tie, if identical additional votes are added,
then the candidate those extra votes toprank, should then have the
greatest winning chances.

Immune to candidaterenamings: if X wins with probability P,
then upon renaming the candidates renamedX should still win with probability P.
Score voting,
which is not a rankorder ballot system, satisfies
ii, iii, iv and independence from all alternatives besides the winner.
(It does not necessarily elect a member of the uncovered set, albeit if
we change the definition of "X covers Y" to incorporate preference strengths
instead of ignoring them – which seems more sensible if one has a scorebased ballot
– then it does, indeed then the score voting winner is the only uncovered candidate.)
Answer
(Both Puzzle & Answer by Forest W. Simmons, July 2010)
We shall prove impossibility by deducing a contradiction.
Scenario I:
#voters  their vote 
2  B>C>A 
1  C>A>B 
1  A>B>C 
Scenario II:
#voters  their vote 
2  D>B>C 
1  B>C>D 
1  C>D>B 
Our method must
give greater winning probability to alternative B in scenario I than II.
[Because if we
rename A→C, B→D, C→B in scenario I then
we get scenario II; hence our claim is equivalent to claiming
that in scenario I considered alone, B wins with greater probability than C;
and that in turn follows from perfect tiebreak responsiveness.]
Now consider the scenario III:
#voters  their vote 
2  D>B>C>A 
1  C>A>D>B 
1  A>B>C>D 
The uncovered set is {A,B,C} and so by independence from covered alternatives
the winner is chosen
according to scenario I.
Now switch A and B in the last voter's ballot to get
#voters  their vote 
2  D>B>C>A 
1  C>A>D>B 
1  B>A>C>D 
The uncovered set becomes {D,B,C},
and so by independence from covered alternatives the winner is
chosen according to scenario II.
In summary, solely by raising B relative to A on a ballot,
the winning probability of B decreased.
This contradicts monotonicity.
Q.E.D.
Return to puzzles
Return to main page