"Participation failure" is forced in Condorcet methods with at least 4 candidates

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

Condorcet:

if there is a Condorcet ("beats all") Winner, he must be elected uniquely and with certainty,

(Strong) participation:

adding votes with A ranked top cannot decrease the probability A wins, and adding votes with B ranked below all voters who win with positive probability, cannot increase the probability that B wins.

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.

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.

Return to main page