We shall prove the following theorem.
Our proof is an improvement & simplification of
an earlier proof by Markus Schulze which in turn simplified one by Herve Moulin.
Theorem: It is impossible for any (possibly nondeterministic) single-winner election method (with preference orderings as votes) with ≥4 candidates to satisfy both
Note: further, the extension to our proof will produce "maximally dramatic" no-show paradoxes requiring only a single no-show voter.
Proof: Suppose such a method existed. Then starting with the 14-voter scenario below we shall in six further steps derive a contradiction.
#voters | their vote |
---|---|
6 | A>D>B>C |
5 | D>B>C>A |
3 | B>C>A>D |
Situation 2: Suppose B was elected with positive probability in situation 1. When we add 7 B>D>A>C voters, B must be elected with positive probability (by participation) while D must be elected with certainty according to Condorcet. Contradiction.
Situation 3: Suppose C was elected with positive probability in situation 1. When we add 9 C>B>A>D voters, C must be elected with positive probability (by participation) while B must be elected with certainty according to Condorcet. Contradiction.
Situation 4: Suppose D was elected with positive probability in situation 1. When we add 3 D>A>B>C voters, D must be elected with positive probability (by participation) while A must be elected with certainty according to Condorcet. Contradiction.
Situation 5: We conclude from situations 2-4 that A must be elected with certainty in situation 1. When we add 7 C>A>B>D voters, B and D must be elected each with zero probability (by participation).
Situation 6: Suppose A was elected with positive probability in situation 5. When we add 8 A>C>B>D voters, A must be elected with positive probability (by participation) while C must be elected with certainty according to Condorcet. Therefore, A couldn't be elected with positive probability in situation 5.
Situation 7:
Suppose C was elected with positive probability
in situation 5. When we add 6 C>B>A>D voters, C
must be elected with positive probability (by participation) while
B must be elected with certainty according to Condorcet.
Therefore, C couldn't be elected with positive probability in situation 5.
Q.E.D.
Extension:
In the scenarios in our proof with k identical no-show voters, we
can – by adding those voters one at a time until the first
one that changes the winner –
produce a "no-show paradox" scenario with only a single no-show voter.
Q.E.D.