License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FORC.2023.2
URN: urn:nbn:de:0030-drops-179232
URL: https://drops.dagstuhl.de/opus/volltexte/2023/17923/
Go to the corresponding LIPIcs Volume Portal


Karov, Bar ; Naor, Moni

New Algorithms and Applications for Risk-Limiting Audits

pdf-format:
LIPIcs-FORC-2023-2.pdf (1 MB)


Abstract

Risk-limiting audits (RLAs) are a significant tool in increasing confidence in the accuracy of elections. They consist of randomized algorithms which check that an election’s vote tally, as reported by a vote tabulation system, corresponds to the correct candidates winning. If an initial vote count leads to the wrong election winner, an RLA guarantees to identify the error with high probability over its own randomness. These audits operate by sequentially sampling and examining ballots until they can either confirm the reported winner or identify the true winner.
The first part of this work suggests a new generic method, called "Batchcomp", for converting classical (ballot-level) RLAs into ones that operate on batches. As a concrete application of the suggested method, we develop the first RLA for the Israeli Knesset elections, and convert it to one which operates on batches using "Batchcomp". We ran this suggested method on the real results of recent Knesset elections.
The second part of this work suggests a new use-case for RLAs: verifying that a population census leads to the correct allocation of parliament seats to a nation’s federal-states. We present an adaptation of ALPHA [Stark, 2023], an existing RLA method, to a method which applies to censuses. This suggested census RLA relies on data from both the census and from an additional procedure which is already conducted in many countries today, called a post-enumeration survey.

BibTeX - Entry

@InProceedings{karov_et_al:LIPIcs.FORC.2023.2,
  author =	{Karov, Bar and Naor, Moni},
  title =	{{New Algorithms and Applications for Risk-Limiting Audits}},
  booktitle =	{4th Symposium on Foundations of Responsible Computing (FORC 2023)},
  pages =	{2:1--2:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-272-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{256},
  editor =	{Talwar, Kunal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17923},
  URN =		{urn:nbn:de:0030-drops-179232},
  doi =		{10.4230/LIPIcs.FORC.2023.2},
  annote =	{Keywords: Risk-Limiting Audit, RLA, Batch-Level RLA, Census}
}

Keywords: Risk-Limiting Audit, RLA, Batch-Level RLA, Census
Collection: 4th Symposium on Foundations of Responsible Computing (FORC 2023)
Issue Date: 2023
Date of publication: 04.06.2023
Supplementary Material: Software (Source Code and Additional Plots): https://github.com/TGKar/Batch-and-Census-RLA archived at: https://archive.softwareheritage.org/swh:1:dir:9bd16e71658b0883e3ac966d48f81f48310fc9f3


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI