Improving the Computational Efficiency of Adaptive Audits of IRV Elections

Alexander Ek (), Michelle  Blom, Philip Stark, Peter Stuckey and Damjan Vukcevic ()

No 15/24, Monash Econometrics and Business Statistics Working Papers from Monash University, Department of Econometrics and Business Statistics

Abstract: AWAIRE is one of two extant methods for conducting risk limiting audits of instant-runoff voting (IRV) elections. In principle AWAIRE can audit IRV contests with any number of candidates, but the original implementation incurred memory and computation costs that grew super exponentially with the number of candidates. This paper improves the algorithmic implementation of AWAIRE in three ways that make it practical to audit IRV contests with 55 candidates, compared to the previous 6 candidates. First, rather than trying from the start to rule out all candidate elimination orders that produce a different winner, the algorithm starts by considering only the final round, testing statistically whether each candidate could have won that round. For those candidates who cannot be ruled out at that stage, it expands to consider earlier and earlier rounds until either it provides strong evidence that the reported winner really won or a full hand count is conducted, revealing who really won. Second, it tests a richer collection of conditions, some of which can rule out many elimination orders at once. Third, it exploits relationships among those conditions, allowing it to abandon testing those that are unlikely to help. We provide real-world examples with up to 36 candidates and synthetic examples with up to 55 candidates, showing how audit sample size depends on the margins and on the tuning parameters. An open-source Python implementation is publicly available.

Pages: 16
Date: 2024
New Economics Papers: this item is included in nep-cdm
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.monash.edu/business/ebs/research/publications/ebs/2024/wp15-2024.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:msh:ebswps:2024-15

Ordering information: This working paper can be ordered from
http://business.mona ... -business-statistics

Access Statistics for this paper

More papers in Monash Econometrics and Business Statistics Working Papers from Monash University, Department of Econometrics and Business Statistics PO Box 11E, Monash University, Victoria 3800, Australia. Contact information at EDIRC.
Bibliographic data for series maintained by Professor Xibin Zhang ().