RAPID: Sequential Sampling in Stages for Statistical Election Audits

自2016年以来，开展了相当多的活动，以开展一种被称为风险限制审计的严格的选举后统计制表审计。科罗拉多州、内华达州、罗德岛州和弗吉尼亚州要求选举后实施RLA，俄亥俄州、宾夕法尼亚州、密歇根州和其他州在2020年前开展了RLA试点。这个项目开发了RLA的算法，其中选票是分阶段抽取的，而不是一次一个。目前的解决方案是基于比率检验，例如Wald在1945年提出的序贯概率比检验(SPRT)，如果在每次抽签后对样本进行测试，这是一种最有效的检验(最小预期样本量)。在真正的选举中，选票是分阶段抽取的，一次n张选票，然后进行测试。N可能是地方选举的数十张选票，也可能是州一级选举的数百张选票。直接应用SPRT导致选票投票审计的程序效率非常低。这个项目开发了专门用于分阶段抽签的算法，初步结果表明，效率有了显著的提高。这个项目从两名候选人选举和使用抽样和替换的投票审计的算法开始，开发了多候选人选举和比较审计的算法。它既提供了严格的证据，证明了由此产生的审计是风险有限的，也提供了实现算法的软件。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.