3-Candidate Instant Runoff Voting:
Master list of paradoxes and their probabilities

By Warren D. Smith, August 2010.   (Skip to conclusion)

This page is intended to be the best-available compendium of information about the probabilities of different pathologies in 3-candidate instant runoff voting (IRV) elections. The "total paradox probability" in such elections, i.e. the probability that at least one among the 8 pathologies {Q, R, U, V, W, X, Y, Z} listed below (note that set does not include S and T) occur in a random election, is found to be

in our three different probability models (defined below) respectively. But if we restrict attention to elections in which the IRV process matters, i.e. in which the IRV and plain-plurality winners differ (i.e. exactly the elections IRV-advocates tend to cite as examples of the "success" of the Instant Runoff Voting process), the total paradox probability becomes stunningly large:

For the most part, this was not previously recognized. This goes a long way toward explaining why it has been so incredibly easy for people like me to find pathologies in real-world IRV elections, seemingly most of the time we ever looked at any interesting IRV election for which we could obtain enough data, and seemingly especially in the elections cited by IRV-advocates as "great successes" for IRV.

These numbers appear a rather serious indictment of Instant Runoff Voting as a decision-making process, as well as hurting its enactment/repeal chances. These large probabilities differ from the perception advanced by the IRV-advocacy group "FairVote," formerly named the "Center for Voting and Democracy." E.g. FairVote's "senior analyst" Steven Hill and the head of Fairvote, Rob Richie, are quoted in the 2008 popular science book Gaming the Vote by William Poundstone (page 268), thus:

[FairVote's] position is that such paradoxes are too rare to worry about. "We've had thousands of [IRV] elections and it's not an issue," said Rob Richie. Steven Hill, a senior analyst with [FairVote] dismisses "these mathematical paradoxes that while in theory are interesting for mathematicians to doodle around on their sketch pads, in fact have no basis in reality... it's also possible that a meteorite will strike Earth and wipe out life... but probably not for a few more million years."

FairVote, Richie, and Hill have all cited various specific IRV elections as "great successes," including Burlington Vermont USA 2009, Ireland 1990, and the Australian House elections of 2007, which actually contained pathologies such as nonmonotonicity (a fact they, during these laudings, left unmentioned). Indeed, despite me and others pointing out these and other examples to FairVote repeatedly for many years, they continue to maintain to this very day

In terms of the frequency of non-monotonicity in real-world elections: there is no evidence that this has ever played a role in any IRV election – not the IRV presidential elections in Ireland, nor the literally thousands of hotly contested IRV federal elections that have taken place for generations in Australia, nor in any of the IRV elections in the United States.
   – FairVote webpage titled "Monotonicity and IRV – Why the Monotonicity Criterion is of Little Import" downloaded 24 August 2010; our emphasis added.

1. The three probability models

Random election model ("REM"; also has been called "impartial culture"):

View a V-voter C-candidate election as a big table with V rows. The kth row specifies which of the C! possible rank-order-style ballots was the vote selected by the kth voter. We assume all among the C!^V possible such tables are equally likely, and take the limit V→∞.

Dirichlet model (also has been called "impartial anonymous culture"):

The election is viewed as being defined by its vector of the C! nonnegative integer "vote totals" (one total for each possible ordering of the candidates, i.e. saying how many voters provided that ordering); this vector sums to V, the total number of voters. All such vectors are considered equally likely, and we take the limit V→∞.

Quas's "1D political spectrum" model:

The C candidates are regarded as independent random-uniform points on the real interval (0,1). The voters are the uniform distribution on (0,1) itself (the candidates are samples from it). As their vote, each voter orders the candidates in order of increasing distance. For example,

        0------------J-----*------------K----------L----------1

in this picture, the candidates dropped randomly on the line segment (0,1) are named J, K, and L; and the voter located at * votes "J>K>L."

2. Mathematical techniques

In the Quas and Dirichlet models the probability of any particular event defined by linear inequalities is proportional to a polytope volume in a C-dimensional or (C!-1)-dimensional space, respectively. It is possible to compute all these as exact rational numbers, in principle. For finite instead of infinite V, it comes down to counting lattice points inside polytopes, and that is in principle doable exactly as an "Ehrhart polynomial(V)" formula. In the REM, the probabilities instead arise from polytope volumes in a nonEuclidean spherical geometry. These are also in principle expressible exactly in terms of "Schläfli functions."

However, I'm not doing any of that here. I'm just using Monte Carlo inexact evaluation.

However, it looks to me now that all the Quas 1D probabilities tabulated in the blue table can be written as rational numbers with denominator=360, and all those in the yellow table with denominator=1800. I.e. our inexact Quas evaluations, if these conjectures are true (and they appear to be) can trivially be converted into exact ones. For example, the approximate number "6.9446" from the blue Quas table is 2500.056/360 which presumably means the corresponding exact answer is 2500/360=125/18=6.94444... and in fact this is true.

The Monte Carlo data is presently insufficiently precise to determine the corresponding magic denominators for the Dirichlet model, but it strongly supports the idea that for the blue table, it is some multiple of 41472, while for the yellow table, it is a multiple of 12780.

3. Master List of Configurations and their Probabilities

Consider the following 10 possible paradoxes that could afflict a 3-candidate Instant Runoff Voting (IRV) election with winner A and second-place finisher B.

In cases S and T, a better word than "paradox" or "pathology" might be "phenomenon." That is, S and T cannot be regarded as "flaws" in the IRV election process, they are just phenomena that would have happened with those votes for any election process. That is why our "total paradox probability" includes only the 8 pathologies {Q, R, U, V, W, X, Y, Z} and not either S or T.
    Professor Jack Nagel has argued R also should have been un-included. For that, see §5.

17. "Loser drop-out paradox." An IRV-loser, by dropping out of the race, would change the winner. (The loser, also called a "spoiler," is B, and when B drops out the winner changes from A to C.) The same set of 3-candidate IRV elections also exhibit "Favorite betrayal paradox": a set of co-voting voters are better off "betraying their favorite" than honestly voting that favorite top, i.e. it is unstrategic to vote for a "spoiler."
18. All scoring rules (including Plain Plurality, antiPlurality, Borda, etc) agree the winner is B, disagreeing with IRV's winner A. If you agree that "democracy" should elect the most-loved and least-hated candidate, then since in these situations B is both of those things simultaneously, you must agree IRV got the wrong winner in these situations.
19. There is a Condorcet Cycle.
20. The Plurality and IRV winners differ (i.e. Plurality=B, IRV=A).
21. If some voters raise their ranking of the current winner, that makes him lose. (I.e. can raise A to top in some BAC and/or BCA votes to make C win.)
22. If some voters lower their ranking of a current loser, that makes him win. (I.e. some voters can lower B to cause B to win.) Both this and the preceding are forms of non-monotonicity.
23. Possible to delete voters ranking current winner bottom, such that he then loses. (I.e. can delete some BCA voters causing A to lose and C to win.)
24. Possible to add new voters ranking a current loser bottom, such that he now wins. (I.e. can add CAB voters to make A lose and B win.) Both this and the preceding are forms of "participation failure."
25. Condorcet "beats-all" winner exists but IRV eliminates him. (I.e. the Condorcet winner is C.)
26. The IRV winner is the same if all ballots are reversed, i.e. the "best" candidate A according to IRV, is the same as the "worst" candidate according to IRV.

For discussion of a particular IRV election containing almost all of these pathologies simultaneously, see completely idiotic IRV election.

There are 1024 possible combinations of those phenomena or their negations, which we denote by a 10-bit binary string. For example 0000100010 means "U and Y occur but QRST_VWX_Z all do not." We list every possible 10-bit string along with an IRV election example allegedly yielding precisely that combination of pathologies – and the probability of occurrence of that combination in our three probability models. (Bitstrings omitted if that configuration impossible, which is why there are many fewer than 1024 lines in our table.) Each percentage in the next two tables is based on 25×10¹⁰ Monte-Carlo experiments and therefore has additive standard error ±0.0001 or closer, i.e. please read "33.3333%" as "(33.3333±0.0001)%." The total computer time (2006-era personal computer) was ≈30 hours.

Below is a smaller summary table of some of the most-requested pathology-probability information in our three probability-models (All of the numbers in the below tables are derivable by adding up appropriate sets of numbers from the above master table):

And below is the same table, but restricted to elections in which the IRV process matters, i.e. in which the IRV and plain-plurality winners differ. (Warning: The error bars are approximately twice as wide as in the tables above.) This almost always makes pathologies substantially more likely:

When IRV-pathologies get more likely when IRV & plurality winners differ (and they usually do get more likely!), that suggests that IRV, counter-intuitively, actually is worse than plain-plurality voting – at least as far as that particular paradox is concerned, and in 3-way elections.

4. Bugs(?)

Anthony Quas pointed me in the right direction to find a bug in my Quas-generator. My Dirichlet generator was also buggy due to some imbecile on Wikipedia publishing an incorrect sorting network. Both now repaired.

I now agree with the scientific literature values for every number I'm aware of in these tables which has already been computed in that literature (over a dozen)? To make that clearer, the below table lists some exact values claimed in the scientific literature versus our Monte Carlo estimates from the blue table above. (I may sometimes be listing somebody as "discoverer," who actually was not the first. Quite a few of these values were independently discovered by several authors.)

Please report any errors/corrections to   warren.wds AT gmail.com.

5. Example of use

These based on old run at lower precision??? Redo with new hi-precn numbers to get slight changes

Prof. Jack Nagel asked what the "total paradox probabilities" would be if R were not included as a "paradox." (Note that S and T already were not included.) His question gives us an excellent opportunity to demonstrate the use of the tables. The only possible binary codes representing "R plus some subset of S and T, but no other letters" are

Of these, the only one which actually occurs with nonzero probability (see the pink table) is 0101000000 with probabilities 0.0164%, 0.0096%, 0.0000%. We may therefore obtain Nagel's "no-R total paradox probabilities" by subtracting these figures from the "total paradox probabilities" we gave in the blue table. The results are

in our three different probability models respectively (error bars≤±0.00025% as usual). Restricted to elections in which the IRV process matters, the answers instead are

where note the normalization constants 0.24466 and 0.12326 arise from the total-T line of the blue table. The reason these adjustments are so small is that R is a rare paradox, and the occasions where R arises unaccompanied by any other paradoxes in {Q, U, V, W, X, Y, Z} – which are the only ones we need to subtract – are very rare.

Another example: "spoilers." IRV propagandists have often claimed that IRV "eliminates the spoiler effect." As you can see from the fact that paradox "Q" happens with positive probabilities (ranging from 9.2% to 33.8% in our 3 probability models for both "all elections" and elections where IRV "matters," i.e. 6 scenarios total), that claim was a lie.

However, can we at least make the weaker claim that IRV reduces the chance of a spoiler scenario versus plain plurality voting? The answer in 3-candidate IRV elections is "yes." To see that, notice that every 3-candidate election where the plurality and IRV winners differ (phenomenon T), is a plurality-voting spoiler scenario (with IRV winner A, plurality winner B, and spoiler C). There also could be elections in which the IRV-winner A is the plurality-spoiler; but since those elections are precisely those in which B is a "Condorcet loser" and A is not plurality winner (hence B is), they already were counted in set T. There also could be elections where the the plurality and IRV winner both are A, i.e. the same (i.e. we do not have phenomenon T) and there is a plurality-spoiler, who then must be B (which happens if and only if either C is Condorcet winner, i.e. we have pathology Y, or there is a Condorcet cycle of form A>B>C>A, i.e. phenomenon S). Therefore prob(T)+prob((Y∪S)∩¬T) equals the chance that at least one plurality-spoiler exists. Then looking up the numbers in our tables we see prob(Q)<prob(T)+prob((Y∪S)∩¬T), and indeed prob(Q)<prob(T), in all 6 of our scenarios, indicating yes: IRV does reduce the spoiler chance in 3-candidate elections.

What about in C-candidate elections with C≥4? Does IRV reduce spoiler chances then (and for which C)? Sorry: those answers seem both un-deducible from the tables here, and non-obvious. But see our separate page about "spoiler candidates" in IRV and plain plurality voting, where the chances are explicitly computed when C=3, and among other things, it is argued that in both the IRV and plain-plurality voting systems in all three of our probability models, the chance goes to 100% that your election contains at least one "spoiler" and hence the probability for "paradox Q" should go to 100% in all three models when C→∞.

6. What about C→∞ candidates instead of C=3?

THEOREM: As the number C of candidates is made large, the "total paradox probability" for IRV approaches 100% in all three probability models here.

PROOF (INCOMPLETE IN THE QUAS-1D CASE): In the Dirichlet model, Quas 2004 in his theorem 1 showed that the probability of paradox 'U' ("more is less" nonmonotonicity) approached 100% when C→∞. Smith 2009 was able to show the same result in the Random Election Model by redoing Quas's proof with appropriate changes. In the Quas-1D model, a Condorcet winner generically exists (and always exists aside from the possibility of a 2-way tie) as a consequence of Duncan Black's singlepeakedness theorem and it is the candidate located closest to the midpoint. However, when C→∞ Quas found that IRV elects the candidate located at x with probability proportional to a certain probability density ρ(x) with support on (1/6, 5/6) and pictured below.

Therefore IRV falls victim to paradox 'Y' with probability→100%. Since the "total paradox probability" is at least as great as the probabilities of these particular paradoxes, it must approach 100% in all three models, and the proof is complete. Q.E.D.

WHY THAT PROOF WAS INCOMPLETE IN THE QUAS-1D CASE: Actually, the above proof is inadequate because Quas's paper did not prove the existence of ρ(x), although Quas did provide convincing evidence, e.g. the picture above computed by Monte Carlo, for its existence. It seems "obvious" that IRV can exhibit no special favortism for the candidate nearest the midpoint (who automatically is the Condorcet winner), as opposed to any of the other candidates located between 0.499 and 0.501 (whose number approaches ∞); indeed the picture indicates, if anything, IRV is biased against the centermost within this interval. Therefore it is "obvious" that the probability IRV elects this one centermost candidate approaches 0. But this "obviousness" is not a "proof."

It would suffice to prove that after IRV has winnowed the C candidates down to, say, C/logC, the probability→1 (when C→∞) that the centermost candidate has been eliminated.

CONJECTURE: Paradox 'X' also should occur with probability→100% in the Quas-1D model, indeed in all three models.

7. Sources

The tables here were computed by Warren D. Smith, August 2010, using computer. Also see the same results but computed using different random number generator as a safety measure. [If you average the results from this and that page, you could shrink the error bars by a factor of √2.] Smith incorporated results from the following literature sources into his computer program:

1. Sven Berg & Dominique Lepelley: Note sur le calcul de la probabilite des paradoxes du vote, Mathematiques, Informatique et Sciences Humaines 121 (1993) 33-48.
2. William V. Gehrlein: Condorcet's paradox and the likelihood of its occurrence: different perspectives on balanced preferences, Theory & Decision 52,2 (March 2002) 171-199.
3. William V. Gehrlein & Dominique Lepelley: The probability that all weighted scoring rules elect the same winner, Economics Letters 66,2 (2000) 191-197.
4. Dominique Lepelley, Ahmed Louichi, Hatem Smaoui: On Ehrhart polynomials and probability calculations in voting theory, Social Choice & Welfare 30,3 (2008) 363-383.
5. Dominique Lepelley & Vincent Merlin: Scoring run-off paradoxes for variable electorates, Economic Theory 17,1 (2001) 53-80.
6. Dominique Lepelley, Frederic Chantreuil, Sven Berg: The likelihood of monotonicity paradoxes in run-off elections, Mathematical Social Sciences 31,3 (1996) 133-146.
7. Anthony Quas: Anomalous outcomes in preferential voting, Stochastics & Dynamics 4,1 (2004) 95-105.
8. Mark C. Wilson & Geoffrey Pritchard: Probability calculations under the IAC hypothesis, Mathematical Social Sciences 54,3 (Dec. 2007) 244-256.

Some other sources which I did not consult, but seem plausibly relevant, include:

1. William V. Gehrlein & Peter C. Fishburn: Effects of Abstentions on Voting Procedures in Three Candidate Elections, Behav. Sci. 24,5 (Sept. 1979) 346-354.
2. Dominique Lepelley & Boniface Mbih: The vulnerability of four social choice functions to coalitional manipulation of preferences, Social Choice & Welfare 11,3 (1994) 253-265.

Beware: Incorrect (but published) results were computed by Crispin Allard and by Eivind Stensholt (and probably others too; unfortunately I myself had computed some incorrect values in CRV web pages). It is quite easy to make your computer get approximately the right value for any given paradox probability. Unfortunately, it also is quite easy to mess up the definitions hence not get it exactly right. (Also, only good random number generators passing all 'Supercrush U01' and Marsaglia 'Diehard' tests should be employed; system-supplied generators usually fail numerous tests in those batteries even as of 2010.) It is usually rather difficult to make your computer get an enormously-wrong estimate. The only case I am aware of where that happened was Allard's paper, which underestimated the nonmonotonicity probability by 3 orders of magnitude by making 4 seperate errors, all biased in the same direction, and apparently never doing any simple "sanity checks."

Update (Nov. 2015): I recently was made aware of the 2009 Dartmouth senior thesis (pdf) by Joe Ornstein titled "Instant Runoff Voting's Startling Rate of Failure." He examines 10000 instant runoff voting elections each in 20 different probabilistic models, including "spatial models." Ornstein is especially interested in "close elections" defined as "any election in which three candidates receive more than 25% of the first-place votes." Depending which of his 20 probabilistic models he uses, Ornstein finds that 7% to 33% of his elections are close. As a fraction of all elections (both close and non-close) 0.6% to 13.5% feature "type I nonmonotonicity" (our paradox "U"), depending which of Ornstein's 20 probability models we use. And Ornstein finds that 13% to 45% of the close elections feature paradox U. Furthermore, the higher paradox percentages coincide with the probability models Ornstein considers more realistic.

Ornstein: "The proportion of non-monotonic IRV elections [is] disturbingly large, large enough to severely question IRV's adequacy as a suitable election reform."

A journal article [Joseph T. Ornstein & Robert Z. Norman: Frequency of monotonicity failure under Instant Runoff Voting: estimates based on a spatial model of elections, Public Choice 161,1 (October 2014) 1-9] later appeared based on this work.

Update (Oct. 2016): Nicholas R. Miller gave two presentations at Amer. Political Science Assoc'n meetings in 2012 (he was former president of APSA), about his papers:
Frequency of monotonicity failure under Instant Runoff Voting with three candidates: Closeness matters, 2012 & revised 2016
Monotonicity failure under Instant Runoff Voting with three candidates, 2012

Miller's conclusions seem consistent with mine and with Ornstein's, at least on shallow examination.

8. Conclusion

That's incredible. Before I had the sense that IRV was bad because paradoxes could happen and weren't so rare. Now it's looking like IRV is benign only in those unproblematic elections where all election methods perform well. In cases where you actually need a better way of voting, IRV is a crapshoot.
–   William Poundstone, author of the 2008 popular science book Gaming the Vote, after seeing this page (this was his comment by email).

Return to main page