Answer to Puzzle #4: Probability of non-monotonic IRV elections

Puzzle: Consider 17 voters electing one winner from 3 candidates using IRV (Instant Runoff) voting. (Each vote is a preference ordering among the three candidates; the candidate with the fewest top-rank votes is eliminated repeatedly until only one – the winner – remains.) Among all the possible elections of this sort: what fraction have the unhappy "non-monotonic" property that the winner would have lost to some loser L, if only some subset of identically-voting voters had changed their top-rankings away from L? (Disallow elections involving ties.)

Extra credit: What happens if the number of voters ("17") instead is allowed to tend to infinity?

Monte Carlo (Approximate) Solution: There are 617=16,926,659,444,736 possible elections. When I examined a random sample of 10,000,000 of them with a computer, I found that

A real life example of this was the Ireland 1990 Presidential election with A=Currie, B=Lenihan, C=Robinson:

Simplest nonmonotonic scenario of Ireland 1990 type. 17 voters.
#voters (before; C wins) Their Vote #voters (after B gives A 2 votes; B wins)
5 C>B>A 5
0 A>B>C 2
4 A>C>B 4
8 B>A>C 6

Exact Solution:

Theorem: the fraction of tie-free 17-voter 3-candidate IRV elections that are non-monotonic (and strictly so, i.e. the revised election still is tie-free, and with no election even having a tie for second-place), is exactly 1,236,235 in 242,159,616, i.e. approximately one election in 195.9.

Some more Monte Carlo data: As a matter of interest, let's redo our Monte Carlo experiment but now with 239 voters instead of 17. Then there are 6239 possible elections. When I examined a random sample of 500,000 of them with a computer, I found that

Indeed, letting PV denote the strict-non-monotonicity probability in a V-voter election, Monte Carlo experiments find

Non-monotonicity probabilities PV with various numbers V of voters.
V PV
17 1/(195.9 ± 1.5)
23 1/(110.5 ± 2.1)
29 1/(82.2 ± 1.4)
35 1/(70.2 ± 1.1)
41 1/(60.0 ± 0.9)
47 1/(53.5 ± 0.7)
53 1/(50.9 ± 0.7)
59 1/(47.9 ± 0.7)
65 1/(46.4 ± 0.6)
119 1/(36.1 ± 1.2)
239 1/(29.3 ± 0.6)
479 1/(26.3 ± 0.5)
959 1/(23.1 ± 0.6)

so apparently limV → ∞ PV ≈ 1/21.

Exact solution in the V→∞ limit: With our last breath of oxygen we tackle the V→∞ limit exactly. We sketch a proof that Theorem: P exists and is positive and is expressed thus in closed form as a ratio of 6-dimensional Gaussian integrals:

P = ∫Ψ exp(-S2-T2-U2-W2-X2-Y2) dSdTdUdWdXdY /Ψ∩Ω exp(-S2-T2-U2-W2-X2-Y2) dSdTdUdWdXdY
where Ψ is the (polytopal) subset of 6-space where X+Y<U+W, X+Y<S+T, and U+W+X<S+T+Y and Ω is the (polytopal) subset of 6-space where S+T<U+W and max{S+T-X-Y, 0}<min{U+W-S-T, (T+U+W-S-X-Y)/2}. Numerically (by Monte Carlo numerical integration) this is
P ≈ 0.04945±0.00002 ≈ 1/(20.22±0.01) .

To see that, let S,T,U,W,X,Y be i.i.d. Gaussian random variables with large mean compared to their standard deviation giving the numbers of each type of votes:

#voters Their Vote
S C>A>B
T C>B>A
U B>A>C
W B>C>A
X A>B>C
Y A>C>B

Then Ψ is the set of elections in which A is eliminated in the first round and then C wins the final round over B. And Ψ∩Ω is the set of elections in which, additionally, B is ahead of C in the first round, but some number Z exists with

max{S+T-X-Y, 0} < Z < min{U+W-S-T, (T+U+W-S-X-Y)/2}
such that if Z voters change their votes from "B>A>C" to "A>B>C," then B wins. (Due to the central limit theorem our Gaussian approximations are valid in the V→∞ limit, and tied elections are neglectible in this limit.)

It is possible to re-express these integrals and hence P in terms of "Schläfli functions" (volumes of nonEuclidean 5-simplices). That is because we can do the radial integration thus reducing our 6-dimensional integrals to integrals over nonEuclidean polytopes drawn on the 5-dimensional surface of a 6-dimensional sphere, where these integrals merely express nonEuclidean volumes since the integrand is a constant. Then, these polytopes may be subdivided into Schläfli-type "orthoscheme" simplices, i.e. whose volumes are Schläfli functions. By the theory of these functions, they may be re-expressed as merely 2-dimensional integrals instead of 5D; and they also should be re-expressible in terms of certain polylogarithms. That would allow evaluating P to a very large number of decimal places. At first it seems quite remarkable how an innocent-seeming problem from voting gives rise to – of all things – Schläfli functions! But you should now realize that this is actually commonplace and that many similar problems in voting will also be solvable in essentially the same way. Here is another (simpler) example.

Further simplifications: Change variables to F=X+Y, G=Y-X, H=S+T, L=T-S, M=U+W (which all still are Gaussian random variables and all 5 of which are i.i.d.), then

P = ∫Ψ exp(-F2-G2-H2-L2-M2) dFdGdHdLdM /Ψ∩Ω exp(-F2-G2-H2-L2-M2) dFdGdHdLdM
Ψ is the (polytopal) subset of 4-space (5-space if you include L) where F<M, F<H, and M<H+G and Ω is the (polytopal) subset of 5-space (4-space if you do not include G) where H<M and max{H-F, 0}<min{M-H, (L+M-F)/2}. This has reduced it to a ratio of two five-dimensional Gaussian integrals (instead of 6D) allowing us more simply to employ Schläfli functions that are volumes of nonEuclidean 4-dimensional simplices. That by the theory of Schläfli functions means we can express everything merely in terms of first order polylogarithmic functions, i.e. single integrals whose integrands involve only functions found in freshman calculus textbooks. This would allow anybody sufficiently determined to compute P to hundreds of decimals of accuracy. (I, however, am not going to do that at least until somebody writes software to evaluate nonEuclidean 4-polytope volumes.)

Schläfli Function. Let me explain just enough about Schläfli functions so that you can see how to do this. Schläfli's theorem is that in any process during which an n-dimensional nonEuclidean polytope smoothly expands from a point, the volume V of that polytope obeys

±(n-1) dV = ∑F Voln-2(F) dθF
where the ± sign is the same as the curvature of the nonEuclidean space (+ for spherical, - for hyperbolic) and where the sum is over the (n-2)-dimensional faces F of the polytope and &thetaF is the dihedral angle there.

For example, with n=2, suppose we want to know the 2-volume, i.e. area, of a triangle drawn on the surface of the unit-radius sphere. Expand our triangle (at all stages having a triangle drawn on thepshere using geodesoc arcs) from a point. The (n-2)-dimensional faces, i.e. 0-dimensional vertices, are just the corners of that triangle and the θF are its angles. Initially for a tiny triangle, the angles sum to π since the sphere is locally flat. But as we expand the triangle to become, say, the one with all three angles right-angles (i.e. the triangle that the octant x≥0, y≥0, z≥0 cuts out of the unit sphere) the angles sum to more than π. Integrating dV over time to get the total area V, we see the well known theorem that the area of a spherical triangle with angles α, β, γ is just |α+β+γ-π|. In particular, our octant-triangle has angle sum 3π/2 so its area is π/2 which is exactly correct: one-eighth of the total surface area 4π of the unit-sphere.

For our next example, take n=3: imagine a tetrahedron (always drawn on the 3-dimensional "surface" of a unit-radius sphere in 4 dimensional space) expanding continuously from a point. The "(n-2)-dimensional faces" are just the six 1-dimensional edges of the tetrahedron and the θF are the dihedral (paper-folding) angles that the 2-dimensional faces touching that edge make at that edge. The Voln-2(F)'s are just the edge lengths. As our tetrahedron expands towards its final size, its dihedral angles change and hence its nonEuclidean volume changes. We just integrate the dV over time to find the final volume. (Note in Euclidean geometry the dihedral angles would not change during the expansion.)

For our voting problem here we instead are concerned with 4-dimensional polytope volumes. The 2-faces are triangles (or anyhow polygons) whose 2-volumes, i.e. areas, may be found by adding up their bend-angles and subtracting the result from 2π. Thus we have an integral of the Schläfli volume-differential dV and the integration dtime is just a 1-dimensional definite integration problem. Hence the 4-volume of any 4-dimensional polytope drawn on the surface of a unit-radius sphere in 5-dimensional space may be written as a 1-dimensional definite integral.

But wait – there's more!

The above reckoning was all only for one kind of nonomonotonic IRV election: in which some candidate C wins, but if some A>B>C voters change their vote to B>A>C, then A wins.

While that was the only kind permitted by the wording of the problem, there is also another kind of nonmonotonicity, which also can happen even in 17-voter elections!

It is also possible for C to win, but then if some A>C>B voters change their vote to C>A>B (and/or to C>B>A) then C stops winning and B wins. (An example, pointed out by William Poundstone, was the Louisiana 1991 Governor election with A=Duke, B=Roemer, C=Edwards.)

Simplest scenario of Louisiana 1991 type. 17 voters.
#voters (before; C wins) Their Vote #voters (after A gives C 2 votes; B wins)
6 C>A>B 8
2 B>A>C 2
3 B>C>A 3
4 A>B>C 4
2 A>C>B 0

Simplest scenario of Louisiana 1991 type where C is originally both the IRV and plurality winner. 21 voters.
#voters (before; C wins) Their Vote #voters (after A gives C 2 votes; B wins)
8 C>A>B 10
3 B>A>C 3
3 B>C>A 3
5 A>B>C 5
2 A>C>B 0

Adding in these new kinds of scenario would, of course, increase the counts. By how much?

Call the (old) kind of non-monotonicity, which we showed occurs 1/(20.22±0.01) of the time in the large #voters limit, "loser now wins" non-monotonicity. The new kind is "winner now loses" non-monotonicity. A quick Monte-Carlo experiment indicates it occurs 1/(8.2±0.07) of the time in the same limit. The total is 1/(5.83±0.07) of the time.

References

Kazuhiko Aomoto: Analytic structure of Schläfli function, Nagoya Math. J. 68 (1977) 1-16.

H.S.M. Coxeter: The functions of Schläfli and Lobatschefsky, Quarterly Journal of of Mathematics (Oxford) 6 (1935) 13-29; reprinted in his Twelve Geometric Essays, Southern Illinois University Press 1968.

H. Kneser: Der Simplexinhalt in der nichteuklidischen Geometrie, Deutsche Math. 1 (1936) 337-340.

L. Lewin: Polylogarithms and Associated Functions, New York: North-Holland, 1981.

John Milnor: The Schläfli differential equality, in John Milnor Collected Papers Volume 1, Geometry, 281-295, Publish or Perish, Inc., Houston and Texas, 1994.

Jun Murakami and Masakazu Yano: On the volume of a hyperbolic and spherical tetrahedron, Commun. Analytic Geometry 13,2 (2005) 379-400. (I found this on Murakami's web page.) See also this, this, and this.

Similar analysis but about "favorite betrayal" rather than "non-monotonicity."

Web page about IRV non-monotonicity.

Open Solved! question: What happens (in the infinite-voter case) if the number C of candidates tends to infinity? What then is the probability of IRV monotonicity failure?

Old answer: I do not know, but suspect it tends to 100%. (My "basis" for that belief is it is probably 0% or 100% and it ought to increase with C, hence is not 0%.)

New answer: proved by the Quas-Smith theorem here.


Return to puzzles

Return to main page