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

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 municipali-ties 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 proce-dures for these nonplurality methods. For 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 comput-able upper and lower bounds on the margin and, where possible, compare them to the exact margins for a large number of real elections