Puzzle #??: Independence from covered alternatives & monotonicity

Prove it is impossible for a single-winner voting method based on rank-order ballots (either deterministic or randomized) to exist simultaneously satisfying i, ii, iii, iv:

1. "Independence from covered alternatives": the winner is always a member of the uncovered set – and who it is, depends only on the voter-preferences among the uncovered candidates.
2. "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.
3. "Perfect-symmetry tiebreak responsiveness": In a C-candidate election featuring a perfect symmetrical C-way tie, if identical additional votes are added, then the candidate those extra votes top-rank, should then have the greatest winning chances.
4. Immune to candidate-renamings: if X wins with probability P, then upon renaming the candidates renamed-X should still win with probability P.

Score voting, which is not a rank-order 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 score-based 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