We propose an approach to post-election auditing based on Bayesian principles, and give experimental evidence for its efficiency and effectiveness. We call such an audit a "Bayes audit". It aims to control the probability of miscertification (certifying a wrong election outcome). The miscertification probability is computed using a Bayesian model based on information gathered by the audit so far.#R##N##R##N#A Bayes audit is a single-ballot audit method applicable to any voting system (e.g. plurality, approval, IRV, Borda, Schulze, etc.) as long as the number of ballot types is not too large. The method requires only the ability to randomly sample single ballots and the ability to compute the election outcome for a profile of ballots. A Bayes audit does not require the computation of a "margin of victory" in order to get started.#R##N##R##N#Bayes audits are applicable both to ballot-polling audits, which work just from the paper ballots, and to comparison audits, which work by comparing the paper ballots to their electronic representations. The procedure is quite simple and can be described on a single page.#R##N##R##N#The Bayes audit uses an efficient method (which may be based on the use of gamma variates or on Polya's Urn) for simulating a Bayesian posterior distribution on the tally of a profile of ballots.#R##N##R##N#A Bayes audit is very similar to single-ballot risk-limiting audits. However, since Bayes audits are based on different principles, the precise relationship between risk-limiting audits and Bayes audits remains open.#R##N##R##N#We provide some initial experimental results indicating that Bayes audits are quite efficient, requiring few ballots to be examined, and that the miscertification rate is indeed kept small, even for very close elections.
['Ronald L. Rivest', 'Emily Shen']
A Bayesian method for auditing elections