IDEAS home Printed from https://ideas.repec.org/p/msh/ebswps/2024-15.html
   My bibliography  Save this paper

Improving the Computational Efficiency of Adaptive Audits of IRV Elections

Author

Listed:
  • Alexander Ek
  • Michelle Blom
  • Philip B. Stark
  • Peter J. Stuckey
  • Damjan Vukcevic

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.

Suggested Citation

  • Alexander Ek & Michelle Blom & Philip B. Stark & Peter J. Stuckey & Damjan Vukcevic, 2024. "Improving the Computational Efficiency of Adaptive Audits of IRV Elections," Monash Econometrics and Business Statistics Working Papers 15/24, Monash University, Department of Econometrics and Business Statistics.
  • Handle: RePEc:msh:ebswps:2024-15
    as

    Download full text from publisher

    File URL: https://www.monash.edu/business/ebs/research/publications/ebs/2024/wp15-2024.pdf
    Download Restriction: no
    ---><---

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:msh:ebswps:2024-15. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Professor Xibin Zhang (email available below). General contact details of provider: https://edirc.repec.org/data/dxmonau.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.