Why IRV is more complicated to tally

| Comments (4) | Software Voting
Most elections in the US use what's called first past the post voting. This just means that whoever gets the most votes wins, regardless of if they get a majority of the votes. Some other countries use what's called Instant Runoff Voting (IRV). The idea behind IRV is that voters rank order their choices. Then, if no candidate has a majority of first place votes, the lowest ranked candidate is removed and you then take the highest ranked candidates from each voter who voted for that candidate. Gigabytes of material have been written about the virtues of IRV versus first past the post versus approval voting, and I don't propose to rehash that here. Instead, I want to talk about the impact of IRV on a voting system.

The issue is this: in a FPTP system, the machines can simply record the number of votes for any candidate, since this is sufficient to resolve the contest.1 In an IRV system you need to record the rankings. Here's an example of why:

Let's say we have an election with three candidates, which we'll call Alice, Bob, and Charlie, and denote A, B, C. We have five voters, numbered 1-5. Now, consider the following table of preferences:

A A B B C    --  A:2, B:2, C:1
C C C A B    --  A:1, B:1, C:3
B B A C A    --  A:2, B:2, C:1

In the first round, then A and B are tied, so we cross out C. This has no impact on voters 1-4, but voter 5 now votes for B, so now it's 3-2 for B and B wins.

Now consider the following table of preferences:

A A B B C     -- A:2, B:2, C:1
C B C C A     -- A:1, B:1, C:3
B C A A B     -- A:2, B:2, C:1

This has the same totals as before, but this time, when we cross off C, voter 5 votes for A and now it's 3-2 A and A wins. I.e., totals aren't enough to determine the winner of an IRV contest. (At this point I can hear the approval voting enthusiasts screaming that approval doesn't have this problem. That's true but irrelevant. Take it outside.)

In order to make IRV work, you need to report each voter's preferences. The difficulty here is that this represents a potential threat to voter privacy because it means that election central needs to have access to the voter's ballot information (this is true with central count optical scan, but not with precinct count or DREs). If there is some way to tie the ballot to a voter, you could know how a voter voted, which could be used for vote buying or coercion.

One standard technique for this sort of tying is what's called "pattern voting". The voter is instructed to vote for a specific set of candidates with one race being the one the vote buyer cares about and the other ones being used to encode the voter's identity. Then the attacker looks for that ballot in the reported ballot lists. One natural defense is to disaggregate the contests, so that while you keep the preferences for a given race, they are disconnected from other races. However, when IRV is used, you can encode your information in the ordering of the individual contests, typically without too much impact on the election. This works especially well in races with a large number of candidates, where it doesn't matter too much how big your effect is on the 29th and 30th candidate.

There has been some work on cryptographic techniques for IRV (e.g., [*]), but the uptake of cryptographic voting in general has been minimal.

1.Though it turns out that many DREs actually record the invididual vote results. See, for instance Issue 5.2.19 of the Premier Elections TTBR report.

4 Comments

I believe the (draft) VVSG requires that cast vote records (CVRs) be retained separately for each vote. For example, 7.5.5-A: “DREs SHALL record and retain at least two machine-countable copies of each CVR.”

I'm a little confused as to why you have to tie any more information with IRV or any preference-based voting (I personally prefer Condorcet systems, since IRV has serious issues with fairness as a third party comes closer to being competitive with two main parties).

A trivial implementation that doesn't tie to ballot creates a hash for every possible preference selection, and then increments the value for the hash key every time that preference shows up.

With three options, there are only 8 possibilities:

Axx
Bxx
Cxx
ABC
ACB
BAC
BCA
CAB
CBA

You could even compute the results for this by hand if you really had to. With four, it's slightly more complex, but not unmanageably so, and you could still hand-compute it if you had a lot of time on your hands. Even with more, it's not computationally intensive. Hash space is cheap, and no ballot identifier needs to be tied, as long as you are handling your authentication before the ballot is provided.

And in the California Governer recall, where there were 100 candidates?

Vote buying with pattern voting is a non-issue. A simple cost benefit analysis would quickly dissuade any campaign from attempting it, even if it were possible. vote buying is a form of "retail" fraud that needs to be perpetrated one voter at a time. To be effective (gain enough votes to have a likely chance of changing an election outcome), the campaign must reach out to a substantial number of voters who are not already known to be solid loyalists (and who therefore cannot be relied upon to keep the secret). Even if the cost per vote were small, the risk of many years in prison by the perpetrator if even one of the voters squeals, makes vote buying a non-existant problem.

Yes IRV requires keeping track of rankings on each ballot, rather than just summing precinct totals, but this is easily and regularly done in elections through out the world (Australia, Ireland, and in several U.S. cities) in elections with millions of voters.

Leave a comment