(non)Monotonicity and Instant Runoff Voting

Monotonicity is the property of a voting system that

  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.

Unfortunately, Instant Runoff Voting (IRV) is not monotonic; it fails both criteria.

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.

#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 (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. 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. 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?

Let's consider only 3-candidate IRV elections. (In IRV elections with more than 3 candidates, failures presumably are more frequent. If there are two or fewer candidates, failure is impossible.) 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.4% 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 numbers 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.

Here is a simple computer program which does this for type-I nonmonotonicity: 

for NNL from 2 to 5 do
NN := 6*10^NNL;   #NN = no. of experiments to try = 600, 6000, 60000, 600000
FailCt := 0;               #counter initially zero
CAwinsCt := 0;             #this counter also initially zero
for i from 1 to NN do      #perform NN experiments
   #step 1: generate random normal numbers as the 6 kinds of vote count
   ABC := RandomNormal();
   ACB := RandomNormal();
   BAC := RandomNormal();
   BCA := RandomNormal();
   CAB := RandomNormal();
   CBA := RandomNormal();
   if(CAB+CBA > BAC+BCA and       #B elimd in original IRV election
      ABC+ACB > BAC+BCA and       #B elimd in original IRV election
      CAB+CBA+BCA > ABC+ACB+BAC   #C wins original IRV election
   ) then   
      CAwinsCt := CAwinsCt+1;   #to simplify, we only examine elections which "C" won with "A" second
      if(ABC < BAC+BCA and         #after ACB votes moved from A to C then A elimd...
         ABC < CAB+CBA+ACB and         
         ABC+BCA+BAC > CAB+CBA+ACB       #...whereupon B wins the new IRV election
      ) then
         FailCt := FailCt+1:   #increment counter since mono-I failure example seen
      fi;
   fi;
od;
print(FailCt, " out of ", CAwinsCt, " type-I mono failures where C won but stops winning if given ACB votes");
od;

The output of this program (two runs, using a normal distribution with much larger positive mean than its standard deviation) was: 

   13 out of 92 type-I mono failures where C won but stops winning if given ACB votes
  125 out of 1015 type-I mono failures where C won but stops winning if given ACB votes
 1278 out of 9985 type-I mono failures where C won but stops winning if given ACB votes
12134 out of 100008 type-I mono failures where C won but stops winning if given ACB votes

    8 out of 89 type-I mono failures where C won but stops winning if given ACB votes
  123 out of 1021 type-I mono failures where C won but stops winning if given ACB votes
 1240 out of 10003 type-I mono failures where C won but stops winning if given ACB votes
12088 out of 99549 type-I mono failures where C won but stops winning if given ACB votes

Hence we conclude the type-I failure probability for IRV 3-candidate elections is

(13+125+1278+12134 + 8+123+1240+12088)/(92+1015+9985+100008 + 89+1021+10003+99549)
= 27009/221762
= 12.18%
which with a generous error bar is (12.2±0.1)%, or 1 failure per 8.2 elections.

Here is the analogous program for type-II monotonicity failure; it yields (2.47±0.04)% failure rate. 

for NNL from 2 to 5 do
NN := 6*10^NNL;   #NN = no. of experiments to try = 600, 6000, 60000, 600000
FailCt := 0;                #counter initially zero
CBwinsCt := 0;              #this counter also initially zero
for i from 1 to NN do       #perform NN experiments
   #step 1: generate random normal numbers as the 6 kinds of vote count
   ABC := RandomNormal();
   ACB := RandomNormal();
   BAC := RandomNormal();
   BCA := RandomNormal();
   CAB := RandomNormal();
   CBA := RandomNormal();
   if(CAB+CBA > ABC+ACB and       #A elimd in original IRV election
      BAC+BCA > ABC+ACB and       #A elimd in original IRV election
      CAB+CBA+ACB > BCA+BAC+ABC   #C wins original IRV election
   ) then
      CBwinsCt := CBwinsCt+1;   #to simplify, we only examine elections which "C" won with "B" second
      x := min(BCA+BAC-CAB-CBA, 0.5*(CBA+BCA+BAC -ABC-ACB-CAB) );
      if( x>0 and CAB+CBA < ABC+ACB+x and CAB+CBA < BAC+BCA-x  #after x BAC votes moved from B to A then C elimd & B wins
           #in older work years back, I forgot this last condition and hence got "4.9% failure rate";
           #when the older program is corrected, it agrees with this one.
      ) then
         FailCt := FailCt+1:   #increment counter since mono-II failure example seen
      fi;
   fi;
od;
print(FailCt, " out of ", CBwinsCt, " type-II mono failures where C won but B wins if B gives A votes");
od;

A different probabilistic model (Dirichlet)

A different probabilistic model is sometimes proposed in which the 6 vote-numbers (for the 6 vote types ABC, ACB, BAC, BCA, CAB, CBA) are to be chosen uniformly in the 5-dimensional simplex

ABC+ACB+BAC+BCA+CAB+CBA=100,   ABC≥0, ACB≥0, BAC≥0, BCA≥0, CAB≥0, CBA≥0
(using 3-letter variable names). I call this the "Dirichlet model." If you replace "RandomNormal()" in the above computer programs by "RandomExponential()" then you get that effect (as Dirichlet was the first to point out).

In the Dirichlet model, for 3-candidate IRV elections I find in this way that the probability of type-I monotonicity failure is (2.16±0.14)%. This agrees excellently with E. Stensholt's finding [Nonmonotonicity in AV, Voting Matters 15 (June 2002)] that "2.17% of the profiles are nonmonotonic." ( Incidentally, Stensholt perhaps erroneously thinks the Dirichlet model is the same as the Impartial Culture model, and erroneously is unaware of type-II failure. Stensholt did not cite the erroneous Allard paper, which if he had seen it would have let him know about type-II. ) It is surprising how greatly the number changes when we change the underlying probabilistic model in this way: 12.2% in the first model versus only 2.2% in the second.

For type-II monotonicity, while we in our original Impartial Culture model found a 2.47% monotonicity-failure rate, in the Dirichlet model we get (0.98±0.094)%. A computer program I had written independently years before for the purpose of correcting Allard's calculation had found (1.050±0.001)% which agrees fine with, and confirms our present (0.98±0.094)%; Allard's incorrect number was 0.025%. (Actually it ought to be possible in the Dirichlet model to express all these probabilities as exact rational numbers arising from polytope-volume ratios, as opposed to our approximate Monte-Carlo results. )

Summary

Probabilistic model type-I failure prob type-II failure prob monotonicity failure prob
Random-elections = Impartial culture (12.2±0.08)% (2.47±0.04)% (14.7±0.1)%
Dirichlet (uniform in simplex) (2.17±0.04)% (1.050±0.001)% (3.22±0.04)%

The best approximation of reality probably lies somewhere between the Dirichlet and Impartial Culture models.


Return to main page