ALPHA: AUDIT THAT LEARNS FROM PREVIOUSLY HAND-AUDITED BALLOTS

• 成果类型: Article
• 署名作者: Stark, Philip B.
• 署名单位: University of California System; University of California Berkeley
• 刊物名称: ANNALS OF APPLIED STATISTICS
• ISSN/ISSBN: 1932-6157
• DOI: 10.1214/22-AOAS1646SUPP
• 发表日期: 2023
• 页码: 641-679

摘要

A risk-limiting election audit (RLA) offers a statistical guarantee: if the reported electoral outcome is incorrect, the audit has a known maximum chance (the risk limit) of not correcting it before it becomes final. BRAVO (Lindeman, Stark and Yates (In Proceedings of the 2011 Electronic Voting Technology Workshop/Workshop on Trustworthy Elections (EVT/WOTE'11) (2012) USENIX)), based on Wald's sequential probability ratio test for the Bernoulli parameter, is the simplest and most widely tried method for RLAs, but it has limitations. It cannot accommodate sampling without replacement or stratified sampling which can improve efficiency and are sometimes re-quired by law. It applies only to ballot-polling audits which are less effi-cient than comparison audits. It applies to plurality, majority, supermajor-ity, proportional representation, and instant-runoff voting (IRV, using RAIRE (Blom, Stuckey and Teague (In Electronic Voting (2018) 17-34 Springer))) but not to other social choice functions for which there are RLA methods. And while BRAVO has the smallest expected sample size among sequentially valid ballot-polling-with-replacement methods when the reported vote shares are exactly correct, it can require arbitrarily large samples when the reported reported winner(s) really won but the reported vote shares are incorrect. AL-PHA is a simple generalization of BRAVO that: (i) works for sampling with and without replacement, with and without weights, with and without strati-fication, and for Bernoulli sampling; (ii) works not only for ballot polling but also for ballot-level comparison, batch polling, and batch-level comparison audits; (iii) works for all social choice functions covered by SHANGRLA (Stark (In Financial Cryptography and Data Security (2020) Springer)), in-cluding approval voting, STAR-Voting, proportional representation schemes, such as D'Hondt and Hamilton, IRV, Borda count, and all scoring rules, and (iv) in situations where both ALPHA and BRAVO apply, requires smaller samples than BRAVO when the reported vote shares are wrong but the out-come is correct-five orders of magnitude in some examples. ALPHA in-cludes the family of betting martingale tests in RiLACS (Waudby-Smith, Stark and Ramdas (In Electronic Voting. E-Vote-ID 2021 (2021) Springer)) with a different betting strategy parametrized as an estimator of the popu-lation mean and explicit flexibility to accommodate sampling weights and population bounds that change with each draw. A Python implementation is provided.