(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

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:

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:

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.

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").

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(S₁∩S₂)=O(n^-0.99)" is also true in the Random Elections Model: the S₂ part is because of this puzzle and the S₁ part is trivial since in the V→∞ limit the variance in each vote-total is zero. (Incidentally, Quas's argument for S₁ 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.

Before starting the above argument, we let the IRV process run normally (unperturbed) until it has winnowed down the field to, say, N^4/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 N^1/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 #2⁵⁷ (say) come out the way we want, we then can also add manipulations to make field #2⁵⁸ come out as desired without destroying the preceding gambits that had manipulated the fields after rounds 2⁵⁷, 2⁵⁶, etc.

The total expenditure (i.e. #ballots altered) over the whole IRV process is then upperbounded by about const·∑_k(N/2^k)^P which is a convergent geometric series with sum=const·N^P. 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·N^P 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·N^P, is sublinear and not enough to alter the conclusion that C is majority-preferred over X (with success probability>1-N^P-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 N^0.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

* 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.

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