(non)Monotonicity and Instant Runoff Voting

By Warren D. Smith; heavily revised March 2009 after learning about paper by Anthony Quas.    (Skip to summary)   (Romanian translation)

Monotonicity is the property of a voting system that both

1. If somebody increases their vote for candidate C (leaving the rest of their vote unchanged) that should not worsen C's chances of winning the election.
2. If somebody decreases their vote for candidate B (leaving the rest of their vote unchanged) that should not improve B's chances of winning the election.

One can also consider sets of voters increasing their vote for C in (I), causing (if monotonicity fails) C to stop winning, etc. We can also, even more generally, still, ask for

1. If some set of voters increase their votes for candidate C and either leave the rest of their vote unchanged, or decrease their votes for C-rivals, then: that should not worsen C's chances of winning the election.
2. If some set of voters decrease their vote for candidate B (and either leave the rest of their vote unchanged, or increase their votes for B-rivals), then: that should not improve B's chances of winning the election.

Unfortunately, Instant Runoff Voting (IRV) is not monotonic; indeed, it fails both criteria. Two real-world IRV elections (both held in 2009) illustrating this were Burlington VT (USA) and Frome Australia.

Examples demonstrating nonmonotonicity of IRV

Criterion I fails: when two voters change their vote to C, that stops C from winning.

Details: C wins this 17-voter IRV election (B is eliminated and 1 more of his 5 votes transfer to C than to A, causing C to win 9:8 over A). But after the two A>C>B voters instead give their vote to C, then B wins. (In the new election, A is eliminated and his 4 votes transfer to B, causing B to win 9:8 over C.)

This occurred in the Louisiana 1991 governor election, which was a (non-instant) runoff election with 12 candidates but only the top 3 got over 410,000 votes each; the remaining 9 candidates each got under 83,000 individually and under 125,000 in the aggregate. It also occurred in Burlington Vermont 2009 (a genuine IRV election for which we have full set of ballots) and Peru 2006 (a top-2 runoff election in which the top 3 candidates got 79% of the votes).

#voters their vote
6C>A>B
2B>A>C
3B>C>A
4A>B>C
2A>C>B

Criterion II fails: when two voters change their vote away from B, that causes B to win.

Details: C wins this 17-voter IRV election (A is eliminated and his 4 votes transfer to C so that C wins 9:8 over B). But after 2 of the B>A>C voters instead give their vote to A, then B wins. (In the new election, C is eliminated and his votes transfer to B so that B wins 11:6 over A.)

This occurred in Frome Australia 2009 and also (in an altered form, with extra Currie voters added, of) the Irish 1990 presidential election, which was an IRV election with 3 candidates.

#voters their vote
5C>B>A
4A>C>B
8B>A>C

The two particular election examples above both feature "Condorcet cycles" C>A>B>C and C>B>A>C respectively. However, both these kinds of nonmonotonicity can also occur without a cycle:

Criterion I fails: when two voters change their vote to C, that stops C from winning.

Details: C wins this 17-voter IRV election. But after the two A>C>B voters instead give their vote to C, then B wins.

#voters their vote
4C>B>A
2C>A>B
2B>A>C
3B>C>A
4A>B>C
2A>C>B

Criterion II fails: when two voters change their vote away from B, that causes B to win.

Details: C wins this 17-voter IRV election. But after 2 of the B>A>C voters instead give their vote to A, then B wins.

#voters their vote
5C>B>A
4B>C>A
4B>A>C
4A>C>B

In all the examples above, C was the IRV winner while the plain-plurality winner was somebody else (or it was a tie). Type-II (but not type-I) failure can also occur in situations (both with or without a Condorcet cycle) where C simultaneously is both the IRV and plurality winner:

Criterion II fails: when two voters change their vote away from B, that causes B to win. There is a Condorcet cycle in this example: C>A>B>C.

Details: C wins this 21-voter IRV election. (Also the plain-plurality winner.) But after 2 of the B>A>C voters instead give their vote to A, then B wins.

#voters their vote
8C>A>B
3B>A>C
3B>C>A
5A>B>C
2A>C>B

Criterion II fails: when two voters change their vote away from B, that causes B to win. This example has no cycle.

Details: C wins this 21-voter IRV election. (Also the plain-plurality winner.) But after 2 of the B>A>C voters instead give their vote to A, then B wins.

#voters their vote
3C>A>B
5C>B>A
3B>C>A
3B>A>C
2A>C>B
5A>B>C

There is one saving grace for IRV, though: it is not possible for both type-I and type-II failure to occur in the same election at the same time in the same way. That is, there is no IRV election in which X, by giving away some votes to the current IRV-winner W, can cause X to win and W to stop winning. This disjointness is easy to see and will implicitly underlie our probability calculations below.

How often do such monotonicity failures happen in instant runoff elections?

For now, let's consider only 3-candidate IRV elections. (We shall consider IRV elections with more than 3 candidates later; in them monotonicity failures presumably are more frequent. If there are two or fewer candidates, failure is impossible. In the limit of a large number of candidates, we shall see failure becomes overwhelmingly likely.) In the "random elections model" [which has also been called the "Impartial Culture" in the literature, see, e.g. Ilia Tsetlin, Michel Regenwetter, Bernard Grofman: The impartial culture maximizes the probability of majority cycles, Social Choice and Welfare 21,3 (Dec 2003) 387-398; William V. Gehrlein: Weighted scoring rules, the impartial culture condition, and homogeneity, Quality and Quantity 20,1 (1986) 85-107; etc.] monotonicity failures of type (I) occur about once per 45 elections and of type (II) occur once per 8.2 elections. In total, monotonicity failure occurs once every 6.9 elections, i.e. 14.5% of the time.

IRV advocates have falsely claimed that non-monotonicity in IRV elections is very rare.

One reason was a published paper by Crispin Allard in which he made an incorrect calculation of these numbers. Allard made at least 3 different errors, all of which pushed his number erroneously too small.

1. Wrongly forgot to multiply by 6; Allard reduced the problem to computing a certain volume, but there really were 6 copies of that volume because of 6 ways to rename the 3 candidates.
2. Then when he computed that (6 times too small) volume, he did it wrong, getting a far-smaller number even than the factor-6 too-small number he should have gotten.
3. Allard only examined type-II nonmonotonicity and apparently was unaware that type-I also existed.

As a result of these errors, Allard got a number about 1000 times smaller than the truth. His incorrect paper was Estimating the Probability of Monotonicity Failure in a UK General Election, Voting Matters 5 (January 1996).

A second reason was the perception by IRV advocates that if phenomena like non-monotonicity occurred in an important real election, then the press would shout all about it; since they were unaware of the press ever doing that, therefore, it must never occur in real life. Since we have mentioned very important real-world elections above in which monotonicity (and other properties too!) failed (and the press, as far as I can tell, never mentioned that even once) we know that perception was erroneous. IRV property failure is quite common in real life – it occurs at rates comparable to those predicted by the random elections and Dirichlet models – despite the lack of mention of that in the press.

How do we know that?

It actually is possible to derive exact formulas for these probabilities using "Schläfli functions" (see puzzle #4). But a simpler approach is just to perform "Monte Carlo experiments" where you simply try lots of random elections to see how often these phenomena occur.

See this web page: /IrvParadoxProbabilities.html for far more about that.

Still another probabilistic model (1-dimensional "political spectrum")

In this model, the N candidates are random-uniform points on the real interval (0,1). The voters are the uniform distribution on this same interval. Each voter orders the candidates best-to-worst in order of increasing distance away from her.

Quas says that he has evaluated the probability of a type-I monotonicity failure when N=3 in this model and it is exactly 5/72=6.9444...%. My computer (Monte-Carlo calculation) finds (6.945±0.002)%, confirming Quas. Quas [after some clarification of his wording] claims the following characterization of 3-candidate type-I-nonmonotonic IRV elections in the political spectrum model:

There is a non-monotonic [type I] allocation of votes if and only if the central candidate gets more than 25% of the vote and is the first to be eliminated. (In this case, the centrist automatically is a "Condorcet winner.") To see this, note that in this case, the non-winning outer candidate can give the winner enough of her vote to have slightly fewer votes than the centrist. She then is eliminated (now having the fewest votes) and all her votes transfer to the centrist rather than to the more extreme winner, allowing the centrist to become the new winner.

That was, in fact, exactly what happened in Burlington 2009.

Apparently 3-candidate type-II-nonmonotonic IRV elections are impossible in this model. We thank Peter J. Sloan for pointing this out.

At first, confusedly, I had thought the following election was non-monotonic [type II]. [As a picture:
```      0==============P=======M===============E=1
```
With Instant Runoff Voting (IRV with honest voters), E is eliminated, then M wins (versus P). With plurality, P just wins.
But if some P supporters dishonestly & strategically give their P votes to E (i.e change their honest votes P>M>E to E>M>P), then M is eliminated in IRV, whereupon P wins. That's nonmonotonicity: fewer P votes cause P to win.]

My computer finds the frequency of occurrence of that kind of failure is (2.7778±0.0003)%, which suggests to me that the exact answer is 1/36=2.7777...%. However this does not meet the technical definition of nonmonotonicity! This election is an example of strategic ballot reversal which is actually an even crazier pathology than nonmonotonicity – maximally lying about your preferences causes your favorite to win, while honest voting would cause him to lose. But because the strategists are also being dishonest about M vs E, this strictly speaking is not "nonmonotonicity" which would involve dishonesty about P only.

Peter Sloan's impossibility proof (sketch):

Let's call the plurality winner P, the central candidate M, for moderate, and the other candidate E ("extremist"). The only honest ranking for P's voters allowed under the 1D political spectrum is P>M>E. Now to get a nonmonotonicity type-II paradox, we need some IRV voters to demote P in their vote, causing P to win. This will not work if the voters honestly ranked P second or third since it will not alter the IRV elimination order (except perhaps by eliminating P). So we must have some P voters switching from P>M>L to either L>M>P or L>P>M, paradoxically causing P to win. That's disallowed since this does not leave the relative rankings of the rest (i.e. L and M) unchanged. The honest ranking is M>L. Or finally, P>M>L could switch to M>L>P or M>P>L, but this will not help eliminate M, so it won't work. Conclusion: type-I non-monotonicity is the only kind allowed in a three-candidate race under the political spectrum model. Q.E.D.

Limit of a large number of candidates

THEOREM: Consider N-candidate elections in either

1. The "random elections model" (all N! votes equally likely for each of V voters independently, V→infinity voters) or
2. The Dirichlet model (the N! kinds of vote-counts sum to 100% and each are ≥0, and all such N!-tuples equally likely; Quas calls this the "simplex model").
Then: the probability that the resulting IRV election is "non-monotonic" in the type-I sense that switching votes from X to Y (where Y is the IRV winner) will cause Y to stop winning... approaches 100% as N becomes large. Indeed, the probability of monotonicity is <N-0.99 for all sufficiently large N. Indeed, further, this non-monotonicity almost surely happens in a huge number of ways simultaneously, i.e. for a huge number (growing to infinity with N) of possible replacement-winner candidates X.

PROOF SKETCH: The Dirichlet case of this theorem was proved by Quas (in the article we cited) as his "theorem 1." The other case can be proved by a parallel argument pointed out by Warren D. Smith in 2009. In both cases the argument proceeds roughly as follows.

Let X be the IRV winner and let Y be preferred over X by a majority (earlier lemmas by Smith & Quas had shown Y exists with probability→1 since X is a Condorcet winner with probability→0 since indeed with probability→1 no Condorcet Winner exists; see this puzzle for the proofs of those lemmas). Change votes saying "X>Y" to now vote X top (apparent "improvement" for X). Now slightly less than half the ballots say X is top. But Y is now the IRV winner with probability →1 since it is ranked top by about 1/N of the voters (versus about 0.5/N for everybody else besides X) hence with probability →1 Y survives to the final IRV round then beats X. (That, to be solid, really required some estimates, but Quas made them.) So the "improvement" stopped X winning.

More details: In case 1 (the random election model with V→∞), Quas's beta distributions become normal distributions (correlated ones with known correlations). Quas's finding (at top of p.104 in his published article) that "1-Prob(S1∩S2)=O(n-0.99)" is also true in the Random Elections Model: the S2 part is because of this puzzle and the S1 part is trivial since in the V→∞ limit the variance in each vote-total is zero. (Incidentally, Quas's argument for S1 in the Dirichlet model can be simplified greatly if you know that when N→∞ "almost all of the mass of a regular N-simplex with unit edges lies in a ball of radius∝N-1/2.") The rest of Quas's argument proving his theorem 1 then goes through unaltered (as sketched above) to prove our theorem.
Q.E.D.

REMARK: The above theorem and proof (with slight changes) should also work for WBS-IRV instead of IRV. For BTR-IRV it will work provided that once the BTR-IRV process winnows it down to 3 survivors, either the final two besides X both pairwise-defeat X, or the one that doesn't is pairwise-defeated by the other one. Those requirements are not necessarily going to be satisfied by themselves (although they should be satisfied with a decent probability, say 0.4 or so), but can presumably be assured with probability→1 with some slight amount of malice aforethought – the undesired survivors need to be eliminated in earlier rounds because X gets raised ahead of them in ballots a little more often.

CONJECTURE: In the 1D political spectrum model with N candidates, the IRV election is non-monotonic (type-I failure) with probability≥1-N-0.2 for all sufficiently large N.

PROOF SKETCH: We now sketch a proof of Quas's conjecture that the IRV election in the 1D political spectrum model is nonmonotone with probability→1 when N=#candidates→∞. I'm optimistic this proof sketch is, in fact, convertible into a genuine proof, but (as of 20 March 2009) not yet willing to say I'm sure.

By Black's singlepeakedness theorem, a Condorcet winner Y exists and is the candidate located nearest to 1/2. Let X be the IRV winner.

Let us select a candidate C somewhat nearer to 1/2 than X (but on the same side) and (say) having a comparatively large initial Voronoi region (i.e. comparatively large initial number of top-rank votes). [We shall need a lemma here that with probability>1-O(ε), the distance between X and 1/2 exceeds ε and there are numerous candidates located between 1/2 and X.]

Consider a cabal, organized by me, of voters who raise X in their votes and whose strategic goal is to create a "buffer zone of safety" for C. That is, some of the voters who prefer Z>C>X, will raise X above Z. The point is this will cause C's nearby rivals (Z) to be eliminated before C is eliminated (even though C would normally have been eliminated because squeezed between two rivals). In this way it seems to me we can keep C alive. In the same way it seems to me we can enhance the survival of other selected candidates. The goal is to induce a specific configuration to approximately appear at each stage of the IRV process, essentially independently of the initial candidate-locations. We make IRV winnow the candidates down according to a fixed time-evolution of the distribution, and with the survivors artificially uniformly-spaced. (The point of uniform spacing is small changes tip the balance; it gives us more control for fewer "bucks expended.") Eventually C will become the IRV winner, entirely due to voters raising the old IRV-winner X in their votes with no other change.

Suppose at the stage where there are M survivors, all the inter-candidate spacings are uniformly const/M but with additive "noise" of order ±(N/M)P/M for some constant exponent P with 0<P<1. (I think this all will work with P=2/3.) Then we ought to be able to control things to eliminate the even-numbered candidates, thus getting M/2 survivors also highly-uniformly spaced, while expending about const·(N/M)P vote-alterations (i.e. raising X in that fraction of the votes).

Before starting the above argument, we let the IRV process run normally (unperturbed) until it has winnowed down the field to, say, N4/5 survivors, and only after that point try to perturb the process. IRV naturally, since it eliminates candidates with small Voronoi regions, will tend to uniformize inter-candidate spacings. Indeed, believe it can be shown as a lemma that (with probability→1 when N→∞), after IRV has winnowed down the field to O(Nκ) candidates with 0<κ<1, the spacings between the remaining candidates automatically will be uniform to within a constant factor. If we select a clump of all the candidates within, say N-3/5 of the N1/5-spaced lattice points and make sure (via vote manipulation) there is one survivor in each clump then we get a situation with near-uniform spacing.

After that, the ballot alterations ("raising X above Z") can be done to manipulate each of the IRV process without affecting preceding stages. For example, suppose we have a ballot of the form "Q>Q>Q>Q>Z>C>...>X>..." where the Qs stand for candidates eliminated in preceding IRV rounds. We can then raise X above Z to get "Q>Q>Q>Q>X>Z>C>..." and all the preceding elimination decisions are unaffected. (We can pledge never to raise X to top-rank; with probability→1 that will not sacrifice enough control to hurt anything.) This way, if we work out manipulations to make the field after IRV round #257 (say) come out the way we want, we then can also add manipulations to make field #258 come out as desired without destroying the preceding gambits that had manipulated the fields after rounds 257, 256, etc.

The total expenditure (i.e. #ballots altered) over the whole IRV process is then upperbounded by about const·∑k(N/2k)P which is a convergent geometric series with sum=const·NP. This has been a sketch of (basically) an inductive proof that we can control the whole history of the IRV election (with success probability→1) by raising X within const·NP ballots. In that case at the end of the day the IRV process will have winnowed it down to X versus C. Thereupon C will have a larger Voronoi region than X and hence will win because the extra votes X got, namely const·NP, is sublinear and not enough to alter the conclusion that C is majority-preferred over X (with success probability>1-NP-1 or so, anyhow – e.g. if X unluckily were located very near to 1/2 this scheme wouldn't work).

It appears than many (say at least N0.1) choices of "C" would be possible in this argument, proving not only that nonmonotonicity almost-surely happens, but it also almost surely happens in a huge number of simultaneous ways. Q.E.D.

REMARK: The above conjecture and proof sketch will not work for WBS-IRV and For BTR-IRV instead of IRV, becasue they both always elect Condorcet winners, one exists with probability→1 in this model, and raisng a Condrocet winner in votes always still leaves him a Condorcet winner.

Quas had in mind a different proof-argument for this conjecture [he gives it just before the start of section 3 of his paper]. His idea would be for X-raising voters to try to enhance the survival of candidates located near to X who would normally have been eliminated. Then at some point X will find itself surrounded by two surprisingly-still-alive rivals, and hence will be eliminated. Quas notes the lemma that, in this 1D model, any candidate who, at any stage in the IRV process, is a "local minimum," i.e. whose neighbors each have more top-rank votes than it does, cannot win. Thus, raising X in votes stops X winning.

Regardless of whether we can prove it, the conjecture seems to be true since Quas tells me he has "convincing computer evidence" for it.

Another open problem – what about "no-show paradoxes"? It is an open question whether an analogue of this "→100% failure theorem" holds not only for nonmonotonicity, but also for "participation failure." (Conjecturally, it does.) See puzzle#55c.

Summary

3-candidate IRV elections
Probabilistic model type-I failure prob type-II failure prob monotonicity failure prob
Random-elections = Impartial culture (12.157±0.001)% (2.3119±0.0005)% (14.469±0.002)%
Dirichlet [uniform in 5-simplex] 13/288=4.513888...% (0.90935±0.0001)% (5.4232±0.0001)%
1D "Political spectrum" 5/72=6.9444...% (2.7778±0.0003)%* or 0 (9.7222±0.0003)% or 5/72
* UPDATE/APOLOGY: Actually the 2.7778% is for "ballot reversal" strategy and not type-II nonmonotonicity. Strictly speaking the latter is impossible. Furthermore, the whole "type-II" column here contains somewhat-wrong numbers, see /IrvParadoxProbabilities.html for the correct ones.

The best approximation of reality probably lies somewhere between the Dirichlet and Impartial Culture models... and Quas's "1D political spectrum" model evidently does.

N-candidate IRV elections in N→∞ limit
Probabilistic model type-I failure prob monotonicity failure prob
Random-elections = Impartial culture →100% →100%
Dirichlet [uniform in (N!-1)-simplex] →100% →100%
1D "Political spectrum" →100% (conjectured) →100% (conjectured)

Also note that multiwinner STV elections can be approximately regarded as a sequence of IRV single-winner elections, and multiwinner elections tend to have a lot of candidates. Therefore, it would seem practically guaranteed that such STV elections will exhibit non-monotonic embarrassments – with more winners and more candidates making these embarrassments more likely.

Please notify warren.wds AT gmail.com of any improved/corrected values.

Return to main page