More Like this

1. Adaptive Risk-Limiting Comparison Audits

   Harrison, Abigail; Fuller, Benjamin; Russell, Alexander (May 2023, IEEE Security and Privacy)

   Risk-limiting audits (RLAs) are rigorous statistical procedures meant to detect invalid election results. RLAs examine paper ballots cast during the election to statistically assess the possibility of a disagreement between the winner determined by the ballots and the winner reported by tabulation. The design of an RLA must balance risk against efficiency: "risk" refers to a bound on the chance that the audit fails to detect such a disagreement when one occurs; "efficiency" refers to the total effort to conduct the audit. The most efficient approaches—when measured in terms of the number of ballots that must be inspected—proceed by "ballot comparison." However, ballot comparison requires an (untrusted) declaration of the contents of each cast ballot, rather than a simple tabulation of vote totals. This "cast-vote record table" (CVR) is then spot-checked against ballots for consistency. In many practical settings, the cost of generating a suitable CVR dominates the cost of conducting the audit which has prevented widespread adoption of these sample-efficient techniques. We introduce a new RLA procedure: an "adaptive ballot comparison" audit. In this audit, a global CVR is never produced; instead, a three-stage procedure is iterated: 1) a batch is selected, 2) a CVR is produced for that batch, and 3) a ballot within the batch is sampled, inspected by auditors, and compared with the CVR. We prove that such an audit can achieve risk commensurate with standard comparison audits while generating a fraction of the CVR. We present three main contributions: (1) a formal adversarial model for RLAs; (2) definition and analysis of an adaptive audit procedure with rigorous risk limits and an associated correctness analysis accounting for the incidental errors arising in typical audits; and (3) an analysis of efficiency. 

   more » « less
2. Doing More with Less: Mismatch-Based Risk-Limiting Audits

   https://doi.org/10.1007/978-3-032-00495-6_13  

   Ek, Alexander; Blom, Michelle; Stark, Philip B; Stuckey, Peter J; Teague, Vanessa J; Vukcevic, Damjan (November 2025, Springer Nature Switzerland)

   One approach to risk-limiting audits (RLAs) compares ran- domly selected cast vote records (CVRs) to votes read by human auditors from the corresponding ballot cards. Historically, such methods reduce audit sample sizes by considering how each sampled CVR di!ers from the corresponding true vote, not merely whether they di!er. Here we investigate the latter approach, auditing by testing whether the total number of mismatches in the full set of CVRs exceeds the minimum number of CVR errors required for the reported outcome to be wrong (the “CVR margin”). This strategy makes it possible to audit more social choice functions and simplifies RLAs conceptually, which makes it easier to explain than some other RLA approaches. The cost is larger sample sizes. “Mismatch-based RLAs” only require a lower bound on the CVR margin, which for some social choice functions is easier to calculate than the e!ect of particular errors. When the population rate of mismatches is low and the lower bound on the CVR margin is close to the true CVR margin, the increase in sample size is small. However, the increase may be very large when errors include errors that, if corrected, would widen the CVR margin rather than narrow it; errors a!ect the margin between candidates other than the reported winner with the fewest votes and the reported loser with the most votes; or errors that a!ect di!erent margins. 

   more » « less
3. When Audits and Recounts Distract from Election Integrity

   https://doi.org/10.18420/e-vote-id2024_13  

   Stark, PB (October 2024, GIEdition Proceedings)

   The U.S. state of Georgia was central to e!orts to overturn the results of the 2020 Presidential election, including a phone call from then-president Donald Trump to Georgia Secretary of State Brad Ra!ensperger asking Ra!ensperger to ‘find’ 11,780 votes. Ra!ensperger has maintained that a ‘100% full-count risk-limiting audit’ and a machine recount agreed with the initial machine-count results, which proved that the reported election results were accurate and that ‘no votes were flipped.’ While there is no evidence that the reported outcome is wrong, neither is there evidence that it is correct: the two machine counts and the manual ‘audit’ tallies disagree substantially, even about the number of ballots cast. Some ballots in Fulton County, Georgia, were included in the original count at least twice; some were included in the machine recount at least thrice. Audit handcount results for some tally batches were omitted from the reported audit totals: reported audit results do not include all the votes the auditors counted. In short, the two machine counts and the audit were not probative of who won because of poor processes and controls: a lack of secure physical chain of custody, ballot accounting, pollbook reconciliation, and accounting for other election materials such as memory cards. Moreover, most voters used demonstrably untrustworthy ballot-marking devices; as a result, even a perfect handcount or audit would not necessarily reveal who really won. True risk-limiting audits (RLAs) and rigorous recounts can limit the risk that an incorrect electoral outcome will be certified rather than being corrected. But no procedure can limit that risk without a trustworthy record of the vote. And even a properly conducted RLA of some contests in an election does not show that any other contests in that election were decided correctly. The 2020 U.S. Presidential election in Georgia illustrates unrecoverable errors that can render recounts and audits ‘security theater’ that distract from the more serious problems rather than justifying trust. 

   more » « less
4. The Decisive Power of Indecision: Low-Variance Risk-Limiting Audits and Election Contestation via Marginal Mark Recording

   Fuller, Benjamin; Pai, Rashmi; Russell, Alexander (August 2024, USENIX Security)

   Risk-limiting audits (RLAs) are the established techniques for verifying large elections. While they provide rigorous guarantees of correctness, widespread adoption has been impeded by both efficiency concerns and the fact they offer statistical, rather than absolute, conclusions. We define new families of audits that help to address these issues. Our new audits are enabled by revisiting the standard notion of a cast-vote record so that it can declare multiple possible mark interpretations rather than a single decision; this can reflect the presence of ambiguous marks, which appear regularly on hand-marked ballots. We show that this simple expedient can offer significant efficiency improvements with only minor changes to existing auditing infrastructure. We establish that these "Bayesian" comparison audits are indeed risk-limiting in the formal sense of (Fuller, Harrison, and Russell, 2022). We then define a new type of post-election audit we call a contested audit. These call for each candidate to provide a cast-vote record table advancing their own claim to victory. We prove that these audits offer remarkable sample efficiency: they guarantee negligible risk with only a constant number of ballot inspections. This is a first for an audit with provable soundness. These results are formulated in a game-based security model that specify quantitative soundness and completeness guarantees. Finally, we observe that these audits provide a direct means to handle contestation of election results affirmed by conventional RLAs. 

   more » « less
5. Ballot Length in Instant Runoff Voting

   https://doi.org/10.1609/aaai.v37i5.25724  

   Tomlinson, Kiran; Ugander, Johan; Kleinberg, Jon (June 2023, Proceedings of the AAAI Conference on Artificial Intelligence)

   Instant runoff voting (IRV) is an increasingly-popular alternative to traditional plurality voting in which voters submit rankings over the candidates rather than single votes. In practice, elections using IRV often restrict the ballot length, the number of candidates a voter is allowed to rank on their ballot. We theoretically and empirically analyze how ballot length can influence the outcome of an election, given fixed voter preferences. We show that there exist preference profiles over k candidates such that up to k-1 different candidates win at different ballot lengths. We derive exact lower bounds on the number of voters required for such profiles and provide a construction matching the lower bound for unrestricted voter preferences. Additionally, we characterize which sequences of winners are possible over ballot lengths and provide explicit profile constructions achieving any feasible winner sequence. We also examine how classic preference restrictions influence our results—for instance, single-peakedness makes k-1 different winners impossible but still allows at least Ω(√k). Finally, we analyze a collection of 168 real-world elections, where we truncate rankings to simulate shorter ballots. We find that shorter ballots could have changed the outcome in one quarter of these elections. Our results highlight ballot length as a consequential degree of freedom in the design of IRV elections. 

   more » « less