(Executive Summary)

WARNING. This page has some errors and is under construction. Is the right idea but some details are not quite right. Really I should not be speaking of cells and boxes, I should be phrasing it in terms of "communication complexity"and should be citing this paper by Conitzer & Sandholm. Their point is IRV has a lot smaller communication complexity than other voting methods, i.e, the voters and everybody can transmit much less info than the other voting methods and still guarantee finding the official winner. The untransmitted info is then ignored. They did not make this remark, but that demonstrates that always, in IRV, asymptotically all of the info in the votes need never be transmitted. But they show that for most other (non-IRV) voting methods, if less than a constant fraction of the info is transmitted, then in at least some situations the voting method simply will elect the wrong winner or fail to know who the right one should be (hence all of the info genuinely must be used, at least in suitable election situations).

You go to the trouble of registering and voting. Then some voting systems ignore your vote, either entirely or partially. This can happen either because the voter makes an error, or it can happen intentionally as part of the design of the voting system.

We think that is bad, and the more ignoring there is, the worse it is. (For one thing, just consider all the wasted effort by the voters in providing all that information.)

### Rigorous definition of vote-examination fraction F

To turn this into something quantitative, define the vote-examination fraction of a voting system as follows. Suppose, there is some algorithm A which – after the votes can been collected and stored (in some obvious format) in memory cells – examines those memory cells and computes the election winner. Think of those memory cells as boxes; the algorithm A can, at any point, decide to open up a box and use whatever information it finds inside. Furthermore, suppose there exists some A with the properties that

1. It always determines the correct winner.
2. It always does so while examining a fraction F (or less) of the memory-cells, i.e. it opens a fraction ≤F of the boxes and never opens the rest.

Here F is actually a function of the number V of voters and the number C of candidates. We are interested in minimizing F by choice of A, for given V≥C≥2. (In particular, mathematicians would be interested in the limsup of F when V,C→∞.)

### Examples

For plurality voting, F=100%, i.e. it is impossible for any A to ignore even a single memory cell. Proof: We assume each memory cell stores one vote (each vote is the name of a candidate). Start examining the memory cells. Even after A has examined V-1 memory cells, leaving just one un-examined, it still cannot guarantee that it knows the name of the winner, because that last cell might break (or create) a tie between two leading candidates. (And there is no way for A to know in advance which cells contain which votes.)

One can similarly argue, for approval and range voting, that F=100%, because again, there is no way to prevent the possibility that the very last cell examined (each cell now storing a single range or approval score for a single candidate by a single voter; there are VC cells in all) does not break or create a lead-tie.

It is trickier to think about Borda and Condorcet voting. We can show F≈100%. Specifically, we can set up a C-way tie where each candidate is pairwise-tied with each other, except that if a single voter decides to act differently about two candidates X and Y, then one of them becomes the Condorcet winner. Namely, suppose half of the voters (perhaps plus one more voter) rank the candidates in a cyclic shift of alphabetical order, and the other half rank the candidates in a cyclic shift of their reversed alphabetical order (all cyclic shifts equally frequent) all except for one voter who (perhaps) switches two candidates in her ranking. A cannot know for sure which two candidates got switched (if any) until it has examined at least V·(C-1) of the VC cells, and just this single switch makes the difference in deciding the election winner (creates or breaks tie). Actually, although we have imagined the votes stored in VC cells, one can also imagine them as being stored in only (C-1)V cells (the last-place candidate in the ranking is implied) in which case this is, in fact, F=100% exactly. But this argument required V to be an exact multiple of 2C (or one off) and if V is not, then it might be possible to examine somewhat fewer cells.

### Instant Runoff Voting (IRV)

In contrast, Instant Runoff Voting is very bad in this respect. Experimentally, it has particularly high voter-error rates. But even if every voter votes correctly, then, in the limit C→∞ where the election has a large number of candidates, IRV ignores asymptotically 100% of the information in the votes, i.e. F→0. To prove that, we need to construct an algorithm A which, given VC memory cells containing the IRV votes (each voter provides the names of the C candidates in order of preference in her C cells) examines only a fraction F of these cells (where F→0 if C is large) but nevertheless always outputs the correct winner. That is done in puzzle 34, where in fact it is shown that

F ≤ (1+1/2+1/3+1/4+…+1/C) / C.

For example if there are C=10 candidates, then at most 29.3% of the cells are read by the IRV process, with the remaining 70.7% ignored. If we imagine the votes are stored in only (C-1)V cells rather than CV (the last-place candidate in the ranking is implied) then the denominator C on the far right of the formula needs to be replaced by C-1. Either way, F→0 when C→∞.

And due to non-monotonicity and "no show paradoxes," even the parts of your vote that IRV does not ignore, can do things you don't expect:

• Raising your vote for X from bottom to top, can actually cause X to lose the election.
• Casting an honest can actually hurt you by yielding a worse election result from your point of view, than if you had not voted at all.

IRV voters have to ask themselves why they are being asked to fill out a rather large ballot of rank orderings when in fact almost everything they write will always be ignored.

### In contrast to IRV...

Range, approval, and Borda voting also never ignore anything any voter says, in the rather obvious sense that every vote affects every election total for every candidate (and in Condorcet, every vote affects every pairwise total). With range, approval, and Borda, any perturbation you make to your vote always moves the election results in the naively expected directions if it moves them at all, and casting an honest vote can never hurt you. (In every Condorcet system, though, casting an honest vote can hurt you versus not voting at all.)