Answer to Puzzle #55: How often is voting honestly worse than not voting with Instant Runoff Voting?

Puzzle:
In IRV, voting honestly can be worse (for a set of co-feeling voters) than not voting at all.

1. Find a concrete example of that.
2. In the random elections model, with 3-candidate V-voter elections (V→∞) show that the likelihood of that is 16.2%. More precisely, this is the chance that a random IRV election will be a situation in which adding some extra number of voters of some common type (such as "A>B>C") will cause the winner to get worse from their point of view. (Also show it is 7.292% in the Dirichlet model.)
3. In the limit of a large number C of candidates, what happens to this likelihood?
4. In a random 3-candidate IRV election as above but now restricting attention to the subset of such elections in which the IRV and plurality voting winners differ, what is the likelihood? If we (further) restrict to the (contained) subset in which for some constant K with 0<K<1 (for example K=99%, but the precise value is irrelevant) the second-placer gets ≤K times as many top-rank votes as the first-placer, and the third-placer gets ≤K times as many top-rank votes as the second-placer, and the IRV and plurality winners differ, then show the probability of a maximum participation failure tends to 100% in the V→∞ limit.
5. In contrast, with both Approval and Range voting, voting honestly is never worse than not voting at all.

Answer (a,b):

• If A was the winner, then adding A>B>C voters cannot (with IRV) cause A to stop winning.
• If C was the winner, then adding A>B>C voters cannot make things worse – from these voters' point of view, the worst is already happening.
• So the only way this can happen is if B was the winner and adding some number t of A>B>C voters causes C to win. This can happen in only one way: A (which used to be eliminated in the first round) now survives the first round (in which B now is eliminated) only to lose to C in the final round.

For this to happen, we need (using 3-letter variable names) that

The first says A is eliminated (but after the t extra A>B>C votes are added, B is); the second says B wins over C after that; the third says B is eliminated after the t extras are added; the fourth says C then wins.

This simplifies to

Here A is eliminated in first IRV round, then B wins 10:8 over C. But if we add 3 more A>B>C voters, then B is eliminated in the first round, whereupon C wins 11:10 over A. These 3 voters would have been "better off staying home" and not voting.

Six times the probability of all the simplified inequalities being satisfied, if ABC, ACB, BAC, BCA, CAB, and CBA are independent standard normal random deviates, is found, by performing 200 million Monte Carlo experiments, to be

The justification for the multiplication by 3!=6 is that we need to consider all possible ways to permute the names of the 3 candidates, i.e. we want to count the probability we get a paradox if the added-voter-type is A>B>C and the probability if it is B>A>C, and the probability if it is A>C>B, etc, where note that all these events are disjoint (due to the first pair in each of our sets of inequalities) hence it really is exactly justified to multiply by 6. (We also remark that it is also possible to express P in closed form in terms of "Schläfli functions.")

This calculation confirms independently (at least, its three most significant digits...) a claimed high-precision computation of 16.230% by

D.Lepelley & V.Merlin: Scoring run-off paradoxes for variable electorates, Economic Theory 17 (2001) 53-80.

I.e. the likelihood of a "participation failure" in an IRV 3-candidate election – a situation where it is possible by adding co-feeling honest voters to make the election result worsen from their point of view – is 16.2%.

If we instead make ABC, ACB, BAC, BCA, CAB, and CBA be independent standard exponential deviates, then we get the "Dirichlet model" rather than the "random election model" and we find (7.36±0.07)%. Lepelley & Merlin found the exact value 7/96=7.291666%.

More Lepelley-Merlin results: Lepelley & Merlin also examined other runoff systems besides IRV (such as Nanson-Baldwin), other kinds of paradoxes, and allowing finite numbers of voters.

Another kind of paradox is the "reverse form" of the participation failure we just examined (L&M call it the "abstention paradox") in which, if some set of voters in an election abstain from voting, that would improve the election result in their view.x For IRV in the random election model, L&M find the probability of that is 5.583%, while under the Dirichlet model it is 35/648≈5.401%.

Further, they find for the combined probability of an IRV "no-show paradox" (i.e. the probability an IRV election exhibits either the forward or reverse form, or both simultaneously) 21.813% under the random election model, while under the Dirichlet model it is 131/152≈11.3715%.

For the Nanson-Baldwin voting system (repeated elimination of the Borda loser) instead of IRV, they find 5.022% probability of forward and also 5.022% probability of reverse paradox under the random election model, which become about 3.4% and 2.4% respectively under the Dirichlet model.

Answer (c): When C increases, this likelihood P is nondecreasing because the same scenarios as before still work on the final C-1 candidates remaining after the first is eliminated by IRV. This nondecreasingness forces P(C) to tend to a positive constant limit as C→∞.

Open Question: What is that constant?

Here is an argument (which is not a proof, but I find it pretty convincing) that, in the random election model with #voters V→∞ in the limit of a large number C of candidates, the probability approaches 100% that we get a "participation failure" scenario. (Also, that the probability we get one for a random voter type, should tend to a positive constant.)

We have seen already that with C=3 candidates, this probability is approximately 16.2%.

Consider the C candidates in order of elimination by the IRV procedure. Suppose we add a new set of K identical voters all with some random voter-type (from the C! possible types). Initially, with high probability (from central limit theorem...) each voter type has about V/C!±√(V/C!) representatives.

If K exceeds (1/C!)√(V/C!) or so, then it typically will be enough to alter the elimination order both for the candidate the new votes rank top, and for order-V other candidates it ranks somewhat below top, all directly – and then via indirect effects after those candidates fail to be eliminated and others receive transferred votes, more candidates will be affected; these indirect effects ought to swamp the direct ones eventually. The net effect should be a vast randomizing effect totally scrambling the elimination order from then on. Since a "random" candidate then will win, this will be a participation failure scenario if it was "worse" in the new-voter-type's view than the old winner. That ought to happen with some constant probability for a random voter type. So the chance it will happen for some voter-type should approach 1 as C→∞.

(d) An analysis by Depankar Ray – actually valid in a considerably more general probabilistic setting than ours –

Depankar Ray: On the practical possibility of a "no show paradox" under the single transferable vote, Math'l Social Sciences 11,2 (1986) 183-189.

In elections with very large numbers of voters and candidates these two winners differ asymptotically 100% of the time so if Ray's analysis were valid in this limit (which it isn't; it only applies to the 3-candidate case) we'd get 50% probability asymptotically of a participation failure.

Finally, an important remark which Depankar Ray also did not notice, is this:

In 3-candidate elections in which

1. The IRV and plurality winners differ.
2. Each candidate gets at least some constant fraction fewer top-preference votes than the preceding one
3. All votes are i.i.d. random (all 6 types equally likely) subject to the preceding two conditions

the probability of a maximum participation failure is 100% (in the large #voters limit).

[The proof of this theorem is trivial.]

This kind of IRV election is very common in practice, which explains why participation failure seems to be very common in IRV elections in practice, c.f. Ireland and Australia.

Return to puzzles

Return to main page