Counting Votes By Humans

A new way to agree on calculations

Cropped from ABC News source

Troy Price is the Iowa Democratic Party Chair. He was in charge of Iowa’s primary vote. The vote totals were due Monday night but have not been finished, now three nights later, and may need to be re-tallied. At a press conference to explain the cause for the delay—mainly a failed phone app—Price was asked, “How can anyone trust you now?”

Today, Ken and I discuss a way to make counting votes quickly checkable by humans.

Indeed the issue with vote counting is one of trust. Our idea is to use computers to assist humans in tallying the votes. But the computers will not be trusted. The goal is to make the number of operations that humans perform of order where there are votes. Even for a national election this is a modest requirement. The surprise, perhaps, is this can be done.

The Vote-Counting Game

Our key insight is to assume that the election is being monitored by two parties—call them Donna and Rachel—who are adversaries. Let us suppose the votes can only be or . Donna wants the count of to be high, while Rachel wants to be high, which here is the same as being low. This is a kind of two-prover model. In complexity theory we know that two provers are more powerful than one prover.

We insist that D and R play a game. We will explain how the game is played in a moment. The key is that the game—the voting game—has several properties.

1. At the end of the game, D and R both have made at most order human operations.

2. At the end of the game, D and R may agree on the vote count.

3. At the end of the game, if D and R do not agree on the vote count, then one of them will be found to be “cheating” and will be fined a monetary amount.

The voting game “solves” the problem of having a humanly checkable election process. The incentive is for D and R to be honest and correct. This precludes either passive error, such as by having incorrect software, or active cheating. If they cheat they may get the fine. If the fine is high enough, that should make D and R strive to be correct.

Item 2 is critical. We do not claim that if D and R agree that their tally is correct. We only claim that if they agree they should be content with the outcome. This is a key insight and perhaps the most controversial point. If we insisted that D and R only agree when they have the objectively correct count, then it is easy to see they must violate 1: they must take order steps.

Structure of the Game and Preparation By the Parties

One structural requirement that is a practical necessity anyway is that the vote count is ordered and that the R and D counts follow the same order. We may suppose, say, that the votes are totaled alphabetically by county, then in order of precints within each county, and finally by name in each precinct. Both D and R are required to provide running tallies that respect this order and their computer systems must allow random access to any running subtotal. Producing the tallies of course is a lot of work while the votes are being counted, but this is divided among many people where each side has onsite observers. The act of checking the tallies—and either finding an error or agreeing on the totals—is what we will optimize.

Let’s consider the tallying of votes. Let

be the ordered sequence of votes. Let

be the running tally of the votes—say the count of . We are not saying D and R can compute this whole sequence infallibly. Of course a computer can compute it, but we cannot trust its answers. What we do is ask D and R to compile their own versions of the tally vector. Let D’s vector be

and R’s vector be

These vectors are computed by computers owned and run by D and R respectively, using the agreed ordering. Each is responsible for the correctness of their vectors. A critical point is that D and R are responsible for their vectors—we do not assume that they are correct.

Running The Protocol

First, D and R check whether . If they are equal, it follows that the tally of the election is done. Since D and R are adversaries, if they agree that is equal to they agree on the outcome of the election. This is success. Note it is important that in this case:

The value they agree on is not necessarily the true .

This is a critical point. We cannot calculate with limited human computations. But if D and R agree that is good enough.

If , then at least one of D and R has made a mistake—or mistakes. That is, some vector is not correct. Note the “mistake” may be a computer error, a human error, or a deliberate error. We do not care which is the case. Nor do we care about finding all mistakes. The goal of the protocol is to give a strong incentive not to make any mistakes and have a process that can check the totals rapidly.

So take , rounded down when needed. D and R then report their running totals and . This uses random access to their tally vectors and so takes constant time.

• If , then D and R know there is an error in the first half. They recurse on that.

• If , then even though these counts may not be correct by themselves, their agreement implies there must be a discrepancy in the second half. D and R recurse on that.

This becomes a binary search in which the invariant is that the counts at the low boundary agree and the counts at the high boundary disagree. In about steps it gets down to where a discrepancy is found in the tallying of a single vote: one of D and R got it right and the other did not. Whoever did not pays the fine.

This completes the description of the protocol. In a more abstract setting this is the same as the discrepancy-finding protocol of Mauricio Karchmer and Avi Wigderson; see their 1990 paper and this 2017 paper by Or Meir.

Analysis

The time analysis is simple. The running time obeys the recursion

with solution is , just as for binary search.

One fine point is that neither D nor R has any incentive to “lie” by making their tallies deliberately wrong. Suppose is a lie. In the case where differs, the recursion will go there and be one step closer to finding a lie. If Rachel’s vector is correct up to , the discrepancy would never be found with her. If agrees with an incorrect , then that doesn’t matter: there still must be a discrepancy in the upper half, and the search will go there. Thus an honest and correct player cannot be tripped up by dishonesty of the other, while in case and both have made mistakes, neither player has a way to know to pin the discovered error on the other party by misreporting or .

Both the penalty and the swiftness of determining itare incentives to D and R to have good programs. They must rely on a program that each has to determine their values and . Both are liable for the correctness of their program. Several aspects make us wonder whether this is a new idea in “checking” of computations:

1. Humans are able to do the checking. They never do more than order work.

2. The result is not a guaranteed correct sum. It is guaranteed that D and R will be forced to agree.

3. The players D and R are assumed to work against each other.

If there are more than two non-negligible candidates then the details are more complicated—such as needing one “prover” per candidate—but the principles are much the same. More problematic are cases where there might be up to errors (where the probability of errors may tail off with higher ) and the goal is to find them all. That could be a subject for another post.

Open Problems

In what situations might this protocol be useful? Has anything like it been proposed?

Update (12:45am ET 2/7): Iowa did finish the count by midnight Thursday in Central Time, but it is open to challenge by any candidate until 1pm ET. Update: The 1pm challenge deadline has been extended to Monday, so the results will not be final until at least a week later than the vote. See also this CNN story about errors in the count. And this Sunday NYT story on counting errors etc.

[added updates; added reference to Karchmer-Wigderson protocol.]