Risk-limiting Audits and the Margin of Victory in Nonplurality Elections

By Anand Sarwate, Stephen Checkoway, and Hovav Shacham.

Statistics, Politics and Policy 4(1):29–64, January 2013.

Abstract

Post-election audits are an important method for verifying the outcome of an election. Recent work on risk-limiting, post-election audits has focused almost exclusively on plurality elections. Several organization and municipalities use nonplurality methods such as range voting, the Borda count, and instant-runoff voting (IRV). We believe that it is crucial to develop effective methods of performing risk-limiting, post-election audits for these methods. We define a general notion of the margin of victory and develop risk-limiting auditing procedures for these nonplurality methods. For positional or scored systems, we show how to adapt methods from plurality auditing. For IRV, the situation is markedly different. We provide a risk-limiting method for auditing the candidate elimination order. We provide a more efficient audit for the elections in which the margin of the IRV election can be efficiently calculated or bounded. We provide efficiently computable upper and lower bounds on the margin and, where possible, compare them to the exact margins for a large number of real elections.

Material

• Journal version.
• Full version, local copy, in PDF and PS.
• Most of the data and code used in the paper is on github.
• Based on an earlier technical report.

Reference

@Article{sarwate-checkoway-shacham:nonplurality:spp13,
  author =  {Anand Sarwate and Stephen Checkoway and Hovav Shacham},
  title =   {Risk-Limiting Audits and the Margin of
            Victory in Nonplurality Elections},
  journal = {Statistics, Politics and Policy},
  year =    2013,
  month =   jan,
  volume =  4,
  number =  1,
  pages =   {29-64},
  url =     {https://checkoway.net/papers/nonplurality2013},
}