Providence: a Flexible Round-by-Round Risk-Limiting Audit

Ballot comparison RLAs require the fewest ballots of all known RLA approaches. On the other hand, they require the use of special election technology and are not always feasible. Ballot polling RLAs require a larger number of ballots, but are more feasible because they do not require any additional functionality of the voting system. What is needed is a complete ballot manifest (a list of ballot storage containers and the number of ballots in each) which enables the creation of a well defined list of the ballots and their locations (the fifth ballot in box number 20, for example).

A ballot polling audit begins when a round [22] of multiple randomly-chosen ballots is drawn. A risk measure is then computed to determine whether (a) the audit ends in success (the election outcome is declared correct) or (b) another round should be drawn. Election officials would typically decide to perform a full manual hand count if the audit does not stop in spite of drawing a large number of ballots, typically over multiple rounds. Ballot polling audits have been used in a number of US state pilots (California, Georgia, Indiana, Michigan, Ohio, Pennsylvania, Virginia and elsewhere) and in real statewide audits (Georgia, Virgina) [18] as well as in audits of smaller jurisdictions, such as Montgomery County, Ohio [22].

A round-by-round (R2) audit is one where the decision of whether to draw more ballots or not is taken after drawing a round of ballots; typically hundreds or thousands or tens of thousands of ballots in statewide elections. A ballot-by-ballot (B2) audit is the special case of round size one—when the decision is made after each ballot is drawn. The popular Bravo audit requires the smallest expected number of ballots when the announced tally of the election is correct, and stopping decisions are taken a ballot at a time (that is, when it is used as a B2 audit). Election officials typically draw ballots in large round sizes, and Bravo needs to be modified for use in this manner. For use as an R2 audit, the Bravo stopping condition can be applied once at the end of each round (End-of Round (EoR)), or retroactively after each ballot drawn if ballot order is retained (Selection-Ordered (SO)). SO Bravo is closer to the original B2 Bravo, and requires fewer ballots on average than EoR Bravo. But it requires the additional effort of tracking the order of ballots.

Zagórski et al. propose ballot polling RLA Minerva [22], which does not need ballot order and relies only on sample and round tallies. They prove that it requires fewer ballots than EoR Bravo when both audits have the same pre-determined round schedule and the true tally is as announced. They also present first-round simulations demonstrating that Minerva draws fewer ballots than SO Bravo in the first round for large first round sizes when the true tally is as announced. Broadrick et al. provide further simulations that show Minerva requires fewer ballots over multiple rounds and for lower stopping probability [4], though the improvement from using Minerva over either version of Bravo decreases with round size.

A major limitation of Minerva is that one needs to determine the round schedule before the audit begins because Minerva has not been shown to be risk-limiting if an adversary can choose subsequent round sizes after knowing the sample drawn. Bravo, on the other hand, is not limited in this manner. This allows Bravo audits the flexibility of choosing smaller subsequent round sizes if the sample drawn so far is a “good” sample. An open question is whether a ballot polling RLA exists with the efficiency of Minerva and this flexibility of Bravo.

A major limitation of our understanding of the ballot polling problem as a community is that we use the number of ballots drawn or values proportional to this number [10, 1, 5] as measures of the workload of an audit. If this were a correct measure of the workload of an audit, we would want to use B2 audits (round size is one) and make decisions about stopping the audit after drawing each ballot, because this leads to the smallest expected number of ballots. Election officials, on the other hand, greatly prefer drawing many ballots at once. This preference is likely due to the following.

Firstly, each round has an overhead workload as well, including setting up the round and communicating among the various localities involved in conducting the audit (for example, audits of statewide contests involve the drawing of ballots at county offices where the ballots are stored).

Secondly, there is an overhead to finding a storage box and unsealing it. For large round sizes, multiple ballots may be drawn at once from a box, and the number of boxes retrieved is smaller than the number of ballots (storage boxes commonly contain many hundreds of ballots each). For smaller round sizes, the number of times a box is retrieved would be roughly identical to the number of ballots drawn, as it is unlikely that a single box will hold multiple ballots from the sample.

Finally, in the current environment of misinformation, election officials would want to ensure that the probability of a misleading audit sample (falsely indicating that the loser won) is very small, which implies that round sizes should be large.

Thus the workload of an audit is not simply a linear (or affine) function of the number of ballots drawn. Relatedly, an optimal round schedule is not completely determined by the expected number of ballots drawn. It depends on other variables as well. The consideration of all these variables is necessary while planning an audit.

We present Providence, and provide the following:

1. 1.

   Proof that Providence is an RLA and resistant to an adversary who can choose subsequent round sizes with knowledge of previous samples.

2. 2.

   Simulations of Providence, Minerva, SO Bravo, and EoR Bravo which show that Providence uses number of ballots similar to those of Minerva, both fewer than either version of Bravo.

3. 3.

   Results and analysis from the use of Providence in a pilot audit in Rhode Island.

4. 4.

   A model of workload that includes the overhead effort of each round and the overhead effort of retrieving a storage unit of ballots; simulations that illustrate the use of this model to compare the different types of ballot polling audits and to plan an audit with minimal workload.

5. 5.

   An analysis of round size as a function of the maximum acceptable probability of a misleading audit sample.

6. 6.

   Open source implementation of Providence and audit planning tools.

Our results demonstrate the superiority of Providence over the other audits. Our work may be used by election officials to plan ballot polling audits, including in Georgia and Pennsylvania in 2022.

Section 2 describes related work. Section 3 describes the Providence audit, section 4 the simulations comparing the number of ballots drawn using various ballot polling audits and section 5 the use of Providence in an audit carried out by the Board of Elections of Rhode Island. Section 6 presents our workload model and describes its use for a ballot polling audit using details of the 2020 US Presidential election in the state of Virginia. Our conclusions, the availability of an audit implementation and acknowledgements may be found in sections 7, 8 and 9 respectively.

Notice that Providence requires the computation of $\tau_{j}$ for $j=1$ and no other values of $j$. The value of $\tau_{1}$ is simply the ratio of the the tails of the binomial distributions for the two hypotheses and can be fairly efficiently computed. The computation of $\tau_{j}$ for $j\geq 2$, as required in Minerva, relies on the convolution of two probability distribution functions and is hence computationally considerably more expensive.

Notice also that Providence and Minerva are identical for $j=1$.

We now prove that Providence is risk-limiting using lemmas from basic algebra in Appendix A.

Minerva was proven to be a risk-limiting audit for a predetermined round schedule. As explained earlier, it is not clear that Minerva is risk-limiting if an adversary can adaptively select the round schedule as the audit proceeds. In this section we prove that Providence does not have this problem, and is risk-limiting even when the adversary can choose next round sizes based on knowledge of the current sample.

To illustrate the practical implication of this property, we consider a toy example: an RLA of a two-candidate contest with margin $0.01$ and risk limit $0.1$. Suppose we wish to achieve a conditional stopping probability $0.9$ in each round of the audit. For Providence, we can compute a new round size for each round based on the previous samples. For Minerva, however, we would have a predetermined round schedule. We use the default Minerva round schedule of audit software Arlo [19] (used by many states performing an RLA), which is is $[x,2.5x,6.25x,...]$; that is, the next marginal round size is $1.5$ times the current one. This multiplier of $1.5$ is known to give, over a wide range of margins, a probability of stopping roughly $0.9$ in the second round if the first round size has probability of stopping $0.9$.

Both the audits of our toy example therefore begin with a first round size of $17,272$ with a $0.9$ probability of stopping, and both will stop in the first round if the sample contains at least $8,725$ ballots for the winner. We now consider two cases for which the audit proceeds to a second round.

In one case there are $8,724$ votes for the winner in the sample, just one fewer than the minimum needed to meet the risk limit. In the Minerva audit, we are already committed to a second round size of $43,180$ which, given the nearly-passing sample of the first round is higher than necessary, achieving a stopping probability in the second round of $.954$. The Providence audit samples more than $9,000$ fewer ballots with a round size of $34,078$, achieving the desired $0.9$ probability of stopping.

In a less lucky sample, the winner recieves $8,637$ ballots, few more than the loser recieves. In the Minerva audit, we again have to use a second round size of $43,180$, but now this round size only achieves a $0.727$ probability of stopping, significantly less than the desired $0.9$. Again, the Providence audit can scale up the second round size according to the first sample and achieve the desired $0.9$ probability of stopping with $58,007$ ballots.

Given tight certification deadlines⁴⁴4Virginia recently passed legislation requiring pre-certification RLAs., the total real time to conduct the RLA is also an important factor to consider when planning audits. Because each county can sample ballots for the same round concurrently, the total real time for a round depends only on the slowest county. In Virginia, Fairfax County typically has the most votes cast by a significant difference; in the contest we consider, Fairfax County had  551 thousand votes cast, more than double the  203 thousand of second-highest Virginia Beach City. Consequently, we model the expected total real time $T$ of an audit using just the largest county, and we define analagous variables for the expected values in just the largest county. For the largest county, let the expected total ballots sampled be $\bar{E}_{b}$, the expected number of rounds $\bar{E}_{r}$, and the expected number of distinct precinct samples summed over all rounds be $\bar{E}_{c}$. Similarly, we use real time per-ballot, per-round, and per-precinct workload variables, $t_{b}$, $t_{r}$, and $t_{p}$. So the real time of the audit is estimated by

As before, we can use our simulations to estimate $\bar{E}_{b}$, $\bar{E}_{r}$, and $\bar{E}_{p}$ using the corresponding averages over the trials. Available data to estimate values for $t_{b}$, $t_{r}$, and $t_{p}$ is limited, and so we take as an example the values $t_{b}=75$ seconds, $t_{r}=3$ hours, and $t_{p}=75$ seconds.⁵⁵5The value $t_{b}=75$ seconds corresponds to a serial retrieval and interpretation of the ballots based on the [5] timing, $t_{p}=75$ seconds corresponds to the approximate doubling in time for new-box ballots as reported in [5] in the ballot-level comparison timing data, and $t_{r}=3$ hours is just a guess at an approximate order for this variable. In practice, election officials could use our software and their own estimates of these values to explore choices for round schedules. Figure 12 shows how the estimated real time for these values differs as a function of $p$. It should be noted that real values of $t_{b}$, $t_{r}$, and $t_{p}$ will vary greatly based on the number of parallel teams retrieving and checking ballots, the distribution of ballots and containers both in number and physical space, and other factors. We provide Figure 12 only as an example of the general shape and behavior of this function. Use of this optimal scheduling tool would depend on parameter estimates tailored to each case.

Unfortunately, efficiency alone is not sufficient for planning audits. In the US today, election officials have a legitimate need to include personal safety as a consideration. In a random sample, a true loser may receive more votes than the true winner. This happens more often when the sample sizes are small, like for a hypothetical first round size of $11$ in the pilot audit, as seen in Figure 5. In the abstract, a misleading sample in an early round is dealt with by drawing more ballots (moving on to another round), but in practice the implications of this approach may be dangerous.

Imagine that Alice beats Bob in an election contest both truly and in the reported results, but Bob’s supporters are insistent he really won. When election officials carry out the RLA, they choose a small first round size in the hopes of achieving an efficient audit by getting to stop sooner (and drawing fewer ballots on average). After the first round, by chance, there are more votes for Bob than for Alice in the sample. Bob’s supporters celebrate their victory that the audit has in fact revealed that Bob really won, but the election officials have to explain that they are moving on to a second round. After the second round, there are more votes in the sample for Alice and sufficiently many that the risk limit is met and the audit now ends confirming the announced result that Alice won. This is an undesirable situation, as it can appear to Alice’s supporters that election officials are simply drawing ballots till a chosen outcome is obtained.

We introduce the notion of a misleading sample, any cumulative sample which, assuming the announced outcome is correct, contains more ballots for a loser than for the winner. We can again use our simulations to gain insight into the frequency of misleading samples. For each stopping probability $p$, Figure 13 gives the proportion of simulated audits that had a misleading sample at any point. Notably, this proportion is as high as 1 in 5 for the smaller stopping probability round schedules. Accordingly, we introduce a new parameter to our audit-planning tool, the maximum acceptable probability that the audit is misleading, the misleading limit.

In Figure 13, horizontal lines are included to show misleading limits of $0.1$, $0.01$, and $0.001$. To achieve a probability of a misleading sample of at most $0.1$, a round schedule with at least roughly $p=.3$ is needed. To achieve a probability of misleading of roughly $0.01$, a round schedule with $p=0.8$ is needed, and to achieve a probability of misleading of roughly $0.001$, a round schedule with $p=0.95$ is needed. It is not unreasonable to think that election officials might choose a misleading limit of $0.01$, or smaller, given the state of public perception of election security in the US and the associated threats of violence. Consequently, the desired misleading limit may be a deciding constraint in the choice of round schedule.

We observe a similar behavior in our simulations of audits on the contest from the pilot audit. Figure 14 shows the proportion of the pilot simulations which contained a misleading sample in any round. Despite the large difference in margin ($\sim 0.05$ in Virginia and $\sim 0.25$ in the pilot) we still observe that a misleading limit of $0.01$ is first achieved at roughly $p=0.8$ and $0.001$ at $p=0.95$.

If election officials wish to enforce a misleading limit for all the rounds, our simulation analysis could help. On the other hand, for a given round, it is straightforward to compute analytically the probability that a loser has more votes than the winner in the sample. Table 2 shows for various margins the minimum first round size $n$ that guarantees a probability of a misleading sample at most $M\in\{0.1,0.01,0.001\}$. For all values of $M$ and all margins, Providence achieves a higher probability of stopping than either EoR Bravo or SO Bravo. As seen in the Table 2, to enforce $M=0.01$ requires minimum round sizes with at least roughly a $0.8$ probability of stopping in the first round. Even if the most efficient audit schedule (by either workload or real time measures) would use a lower stopping probability $p$ to choose the first round size, the election officials may opt to use this constraint on the probability of a misleading sample as the deciding factor in planning their audits.