When there's a close election, something we often see afterwards is a scene like this, a manual recount of the ballots cast in the election. And recounts like this are both an important security feature and a potential opportunity to employ technology to make the process better. A recount is an important security feature, because in any kind of counting process we're likely to see some fraction of votes be counted in error. This is true no matter what the voting technology. It's just in a complex process involving thousands of locations. Some votes are going to be misplaced. Some are going to be misinterpreted. Some are going to be lost. And a manual recount is an opportunity to check up on the whole process. Some voting systems like DREs provide very limited opportunities for a recount. If there's a recount in a place involving DRE's, what election officials are actually doing is just pressing the print button again. Maybe they're going to check their arithmetic, adding up the totals from the different machines, but there's no opportunity to actually go into the machine and evaluate each ballot individually, since the, the software in the machine, if it was dishonest, will have changed all of the records. The most time-consuming audits, but also, recounts rather, but also the most thorough, are ones that are involving paper ballots. Recounts of paper ballots can be time consuming and costly, and so there are rules in place about when they occur. Most states have a law that invokes a mandatory recount of, of all the ballots in the election. If the margin of victory is smaller than a certain predetermined threshold. Also in most jurisdictions, candidates, or sometime voters can request a recount if they're willing to pay for it. Usually the State will refund the cost of the recount in the event that the election outcome changes. But it's still a big gamble for whoever's making the request. That cost can be very high when it comes to recounting paper ballots. Figures from different sources vary and it depends a bit on what you are taking into account. But the quest to manually recount a paper ballot can be any where from 10's of cents to more than a dollar, and in a large election, that can very quickly add up. So the cost, the cost can be prohibitive to manual recounts in large jurisdictions. Now a related topic to recounting is the idea of post-election auditing, which involves very much the same process of going back and having people review physical records of some of the votes. Now let me explain why post-election audits are an extremely valuable security feature. So in a, a system that provides auditability, like a precinct count optical scan voting system, we end the election with two sets of records. We have a set of paper ballots, which are slow and expensive to recount manually, but are verified by the voter. So in some ways these are the strongest evidence we have of the voter's intent. On the other hand, we also have a computer record, an electronic record in a, in a memory card, say. This is fast and easy to count, because it's a computer record. But it's not verified by the voter. This kind of redundancy between different records, which, as I explained earlier in the course also have very different security properties and failure modes, offers us a chance to get much greater security for the whole system. However this redundancy is only useful if we check both records to make sure they agree, and checking these records for consistency is the role of a manual audit. So, a manual audit is a process that can be conducted after the election, but before the final results are declared, and it involves spot checking the ballots to make sure that the computer records and the paper records agree. Unlike a, a recount which usually takes place, throughout the entire jurisdiction, and involves all the ballots, a post-election audit usually involves selecting a random subset of all of the precincts, and then just counting the pieces of paper in those precincts to check whether they agree or disagree with the computer records in those places. If there's a disagreement, we can elevate to a recount of all the ballots across the entire jurisdiction. One important criteria for this, though, is that the places that we're going to audit have to be picked randomly. We can't announce in advance where the audits are going to be held, or anyone who's going to commit fraud would just make sure the fraud was committed in places that weren't going to be audited. Furthermore, there have been documented cases where election officials, in order to avoid a wider recount, went and checked the ballots in certain jurisdictions beforehand in secret. And then announced that those were the places that were going to be audited, after they knew that they weren't any discrepancies that were going to be revealed. So those kinds of shenanigans can be avoided if we carefully come up with procedures for randomly selecting where the audit locations will be. One way to do this, that's frequently talked about is to, to use stock market closing prices on the day, on the day, the day before the audit is going to be held. That way its going to be very hard to predict or manipulate which set of, of places is going to be a subject to the audit. Another question is how much do we need to audit? How many precincts, for instance? And the standard practice is to use a fixed fraction of the precincts, say, ten percent of them, selected at random. This has some problems, though. A better alternative would be to fix the level of statistical confidence we're shooting for. Say we want to, audit enough that we'll be 99 percent confident that the outcome is correct. If we just audit a fixed fraction of precincts, we're either going to be counting too many votes or not enough votes to reach a given target level of confidence. Because the level of confidence we get from auditing, say, ten percent of precincts, depends on the size of those precincts, the number of votes, the margin of victory, and other factors like that. So, the recommended practice is to fix a level of confidence and then audit until you get to it. This idea of picking a level of confidence leads to the idea of a statistical risk- limiting audit. That is, you audit until you can establish with your given level of confidence that hand counting all of the paper records would yield the same winner as the electronic tally. A couple of states have implemented pilot programs with statistical risk-limiting audits, and I'm hoping that the majority of states follow suit in the near future. So let me give you an example of an audit that we can use to see how statistical risk-limiting audits might work and ways that technology can make them much more efficient. So in our example, we have candidates Alice and Bob. And Alice has gotten 55 percent of the votes, and Bob has gotten 45. What we want to do in this audit is reject the hypothesis that more than five percent of ballots differ between the paper and electronic records. So we're going to pick some precincts. In order to get 95 percent confidence, let's say we're going to have to pick 60 precincts and hand-count the ballots in those places. The problem with this is going to be the cost. If those precincts are large, auditing 60 precincts might cost, say, $100,000. We'll see an example than can reduce these figures in a few minutes. So there's an alternative approach that can make these costs much lower. So rather than picking whole precincts and auditing there, which is the standard practice today, we could try to pick individual ballots and just make sure that those individual ballots agree between the paper and electronic records. Let me give you some intuition for why this is much more efficient. On the left here, you see 100 marbles, let's say those are standing in for precincts. Ten percent of the marbles are blue, which are precincts where error or fraud occurred. On the right you see 6300 beads, again with ten percent of them blue. These represent individual ballots and ballots with error or fraud. So if we sample ten percent from each of these sets of things, in which case are we going to have a greater likelihood of finding a blue unit? In which case is our ten percent audit more likely to turn up fraud? So the question is how large a sample do we need to draw from each of them to reach our given statistical, confidence level? And the sample you're going to have to draw from the marbles is going to be a much higher percentage than the sample you have to draw from the beads. So if we apply this intuition to, to auditing, and come back to our example, we can see that if we move from auditing precincts to auditing ballots, we can drastically reduce the cost. Because using ballot based audit, we might only have to look at 60 ballots from in, across the entire jurisdiction. This would reduce the cost from $100,000 to way less than $1,000. So, what's the problem though with the idea of a ballot based audit of sampling individual ballots to get to a statistical level of confidence? The problem is that we need some way, to match records from the computers from the electronic count to individual ballots. You have to have two things that allegedly agree according to the computers, to check that they actually do. One way to get this would be to have serial numbers printed on all of the ballots and to record those along with the votes that the machine thinks are on each ballot. But this creates a privacy problem. It's difficult to establish this correspondence in a way that doesn't compromise the secret ballot. So now I'm going to show you a new idea that came out of some of my earlier research, that is one way we can perform an audit with a more efficient ballot-based way without compromising the secret ballot. And this is very interesting because it involves a way that we can use machines in the process without having to trust them. So what we begin with is the results from the election. Let's say we have a set of paper ballots and a set of computer totals. So, this is our starting point for the audit. And what we want to do is establish that the paper ballots and the computer totals are in agreement. So the first thing we're going to do is check that the electronic records match the paper records and we'll do this using something I call a recount machine. This could be an off the shelf commercial scanner hooked up to a PC running special software. And its job is to scan in all the ballots and produce two set of records as a result. First it's going to produce a computer file that has the votes from each ballot individually together with a new number, the ballot number. Second, it's going to print on each of the ballots as it's being scanned that same ballot number. So it's going to number the ballots, and produce a computer record that has, for each ballot number, the votes that were recorded there. Now, we're doing this as a separate process after original voting. Because that way the ballots have already been shuffled, the order has been lost. Privacy has been protected. But if we scan them the second time, after the real count, now we have an opportunity to enumerate them, and to produce this kind of record. So we'll take that electronic record from the recount machine and we'll compare it to the records from the initial count. If there's any mismatch, we need to do a manual recount. But if the records agree, we're good, right? Well, actually we have one problem which is that we need a way to know that the recount machine wasn't lying to us, that it was more honest. Why should we blindly trust that machine if we weren't going to trust the optical scanners or whatever machines produced the initial count? But using ballot based auditing measures, we can verify that it's behaving correctly. So the second step is that we're going to audit the recount machine by selecting random ballots from the pile for human inspection. So we actually select records then pull the corresponding ballots out of the pile, and make sure that they agree with the records that the recount machine produced for those same ballots. So looking at this whole process, we can see that there's really two steps. We're going to do a machine recount, coupled with a ballot-based manual audit. So this is really neat to me because this is a way we can use a machine in the election process without having to trust it at all since we can manually verify that it was behaving honestly. This kind of technology can significantly reduce the amount of work we have to do to perform a post election audit. Let's take, as an example, the 2006 Virginia US Senate race. There was a .3 percent margin of victory. So this is a very close election, and if we want to establish with 99 percent confidence that the result is correct with a traditional precinct-based audit, we'd have to have people look at more than 1,000,000 ballots. With a machine-assisted audit, we can reduce that number to just a bit more than 2,000 ballots. So, this is an incredible savings in terms of the amount of time, and, and, and money and human effort that has to go into the process. And it comes without having to trust the technology at all. Other researchers have spent a lot of time trying to think of efficient rules for figuring out how many ballots have to be audited. Using, ballot based audits like this. And have come up with heuristics that are, are really smart. It, it turns out that if you look at the contents of the ballot, for instance, you can reduce the, the number even further. These kinds of reductions are being coupled with very easy to use heuristics for, for determining that, that number of ballots you have to look at. So all of this work is going into trying to make sure that the, the procedures are easy for election officials to follow. And simple to write into, into election system procedures. So I hope that ballot based audits like this, and routine post-election auditing. Will become a much bigger part of election practice in the future. This is especially important because it's, it's part of what's probably the gold standard in election technology today. Precinct count optical scan ballots, paper ballots scanned at the polling place, coupled with a mandatory risk limiting post election audit that occurs before the election results are declared. This is about as good as we know how to do in terms of all of the properties we want from elections based on available technology today.
