A Bayesian Method for Auditing Elections

Authors: 

Ronald L. Rivest and Emily Shen, Massachusetts Institute of Technology

Abstract: 

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.

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.

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. The Bayes audit uses an efficient method (which may be based on the use of gamma variates or on Pólya's Urn) for simulating a Bayesian posterior distribution on the tally of a profile of ballots.

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. 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.

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.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {179538,
title = {A Bayesian Method for Auditing Elections},
booktitle = {2012 Electronic Voting Technology Workshop/Workshop on Trustworthy Elections (EVT/WOTE 12)},
year = {2012},
address = {Bellevue, WA},
url = {https://www.usenix.org/conference/evtwote12/workshop-program/presentation/Rivest},
publisher = {USENIX Association},
month = aug
}

Presentation Video

Presentation Audio