Puzzle:
It has often been noted that
Instant Runoff Voting (IRV)
ignores a large portion of a large number of the votes.
In this puzzle, we shall prove a theorem showing,
quantitatively, that IRV always ignores asymptotically all
the information in the votes.
Suppose there are V voters and C candidates.
A. Prove
that IRV never examines more than a fraction
(HC-1/2)/C
of the CV "cell entries" inside the votes,
where Hn=1+1/2+1/3+1/4+...+1/n is the nth "harmonic number."
When C=10, this fraction is 6121/25200≈24%,
when C=20, it is 15%, and when C→∞ it goes to 0.
B. Prove
that IRV usually will not elect Condorcet winners (even when Condorcet Winners exist)
in the random election model in the limit C→∞ with V fixed,
nor in any limit V,C→∞ with C≥V0.51.
Solution A: Here is an IRV-winner-determining algorithm. At the beginning we shall suppose our computer has, already in its memory, the V rank-order votes (each an array of C numbers, for example if C=5 and the array contains "4,0,1,3,2" that means that voter top-ranks candidate 4, second-ranks candidate 0, third-ranks candidate 1, fourth-ranks candidate 3, and last-ranks candidate 2). The algorithm maintains C linked lists containing the voters whose current top-preference is candidate K, for each K∈{1,2,...,C}, and maintains knowledge of the cardinalities of each of those lists. It also maintains a list and array indicating the as-yet uneliminated ("still there") candidates. Each voter has a "finger" which initially is pointing at the candidate she top-ranks. During the first IRV round, we construct all these lists in O(V+C) steps while examining the top-rank vote of every voter (V array-cell-examinations). Then during that and each subsequent IRV round, we
But if you also count the cells that are "hopped over," then the algorithm can be forced to examine almost all of the VC cell-entries for C large, e.g. see this example. That is, however, unlikely. If each voter just provides a random ordering of the candidates as her vote, then each voter ultimately hops until she reaches one of the two final-round candidates, then stops; this is in expectation about C/3 hops. So typically with random voters, a fraction ≈1/3 of the vote-cells are examined assuming we also count hopped-over cells as "examined."
Based on an insight by Vincent Conitzer and Tuomas Sandholm.
Solution B (sketch): one needs to show that the "noise" from the unexamined cell-entries probably far exceeds the "signal" from the examined subset. And it's indeed experimentally seen to happen.
Even without any calculation, it ought to be plain that ≥2/3 of the vote-cells IRV leaves unexamined will usually outweigh the ≤1/3 of them – or 0% of them – it examines, as far as determining the Condorcet winner is concerned. For example, if we were doing simple majority vote in a 2-candidate election in which there were a large number of votes each a perfect coin flip, then examining the first third of the votes would yield an incorrect winner arctan(√2)/π≈30.4% of the time. In our case we are examining only at most one-ninth of the pairwise comparisons. So with a large number C of candidates we can expect the IRV-examined cells to yield a large number of incorrect conclusions about pairwise winners.