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 6^{17}=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
#voters | Their Vote | #voters |
---|---|---|
f | C>A>B | g |
g | C>B>A | f |
x | B>A>C | 0 |
y | B>C>A | 4 |
0 | A>B>C | y |
4 | A>C>B | x |
A real life example of this was the Ireland 1990 Presidential election with A=Currie, B=Lenihan, C=Robinson:
#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 6^{239} possible elections. When I examined a random sample of 500,000 of them with a computer, I found that
Indeed, letting P_{V} denote the strict-non-monotonicity probability in a V-voter election, Monte Carlo experiments find
V | P_{V} |
---|---|
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 lim_{V → ∞} P_{V} ≈ 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:
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
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
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
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 Vol_{n-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.
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.)
#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 |
#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.
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.