RAPID: Sequential Sampling in Stages for Statistical Election Audits

George Washington University, Washington DC

Investigators

Abstract

Since 2016 there has been considerable activity towards a rigorous type of post-election statistical tabulation audit known as a risk-limiting audit (RLA). The states of Colorado, Nevada, Rhode Island and Virginia require post-election RLAs, and Ohio, Pennsylvania, Michigan and others carried out pilot RLAs before 2020. This project develops algorithms for RLAs where ballots are drawn in stages, as opposed to one at a time. Current solutions are based on ratio tests such as the sequential probability ratio test (SPRT) proposed by Wald in 1945, which is a most efficient test (smallest expected sample size) if the sample is tested after each ballot draw. In real elections, ballots are drawn in stages, n ballots at a time, and then tested. n may be tens of ballots for a local contest, or hundreds of ballots for a state-level contest. Direct application of the SPRT results in a very inefficient procedure for ballot polling audits. This project develops algorithms specifically for ballots drawn in stages, and preliminary results demonstrate a significant improvement in efficiency. Beginning with an algorithm for two-candidate elections and polling audits using sampling with replacement, this project develops algorithms for multiple-candidate elections and comparison audits. It provides both: rigorous proofs that the resulting audits are risk-limited as well as software implementing the algorithms. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.