Efficient Lower Bounding of Single Transferable Vote Election Margins

• URL: http://arxiv.org/abs/2501.14847v1
• Date: Fri, 24 Jan 2025 13:39:23 GMT
• Title: Efficient Lower Bounding of Single Transferable Vote Election Margins
• Authors: Michelle Blom, Alexander Ek, Peter J. Stuckey, Vanessa Teague, Damjan Vukcevic,
• Abstract summary: Single transferable vote (STV) is a system of preferential proportional voting employed in multi-seat elections. The margin of victory, or simply margin, is the smallest number of ballots that, if manipulated, can alter the set of winners. Lower bounds on the margin can also be used for this purpose, in cases where exact margins are difficult to compute.
• Score: 56.12949230611067
• License:
• Abstract: The single transferable vote (STV) is a system of preferential proportional voting employed in multi-seat elections. Each ballot cast by a voter is a (potentially partial) ranking over a set of candidates. The margin of victory, or simply margin, is the smallest number of ballots that, if manipulated (e.g., their rankings changed, or ballots being deleted or added), can alter the set of winners. Knowledge of the margin of an election gives greater insight into both how much time and money should be spent on auditing the election, and whether uncovered mistakes (such as ballot box losses) throw the election result into doubt -- requiring a costly repeat election -- or can be safely ignored. Lower bounds on the margin can also be used for this purpose, in cases where exact margins are difficult to compute. There is one existing approach to computing lower bounds on the margin of STV elections, while there are multiple approaches to finding upper bounds. In this paper, we present improvements to this existing lower bound computation method for STV margins. In many cases the improvements compute tighter (higher) lower bounds as well as making the computation of lower bounds more computationally efficient. For small elections, in conjunction with existing upper bounding approaches, the new algorithms are able to compute exact margins of victory.

Related papers

• Optimal bounds for dissatisfaction in perpetual voting [84.02572742131521]
  We consider a perpetual approval voting method that guarantees that no voter is dissatisfied too many times. We identify a sufficient condition on voter behavior under which a sublinear growth of dissatisfaction is possible. We present a voting method with sublinear guarantees on dissatisfaction under bounded conflicts, based on the standard techniques from prediction with expert advice.
  arXiv  Detail & Related papers  (2024-12-20T19:58:55Z)
• Improving the Computational Efficiency of Adaptive Audits of IRV Elections [54.427049258408424]
  AWAIRE can audit IRV contests with any number of candidates, but the original implementation incurred memory and computation costs that grew superexponentially 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.
  arXiv  Detail & Related papers  (2024-07-23T13:28:00Z)
• Ahead of the Count: An Algorithm for Probabilistic Prediction of Instant Runoff (IRV) Elections [0.0]
  We introduce a novel algorithm designed to predict outcomes in Instant Runoff Voting (IRV) elections. The algorithm takes as input a set of discrete probability distributions describing vote totals for each candidate ranking. We calculate all possible sequences of eliminations that might occur in the IRV rounds and assign a probability to each.
  arXiv  Detail & Related papers  (2024-05-15T00:25:51Z)
• Efficient Weighting Schemes for Auditing Instant-Runoff Voting Elections [57.67176250198289]
  AWAIRE involves adaptively weighted averages of test statistics, essentially "learning" an effective set of hypotheses to test. We explore schemes and settings more extensively, to identify and recommend efficient choices for practice. A limitation of the current AWAIRE implementation is its restriction to a small number of candidates.
  arXiv  Detail & Related papers  (2024-02-18T10:13:01Z)
• Adaptively Weighted Audits of Instant-Runoff Voting Elections: AWAIRE [61.872917066847855]
  Methods for auditing instant-runoff voting (IRV) elections are either not risk-limiting or require cast vote records (CVRs), the voting system's electronic record of the votes on each ballot. We develop an RLA method that uses adaptively weighted averages of test supermartingales to efficiently audit IRV elections when CVRs are not available.
  arXiv  Detail & Related papers  (2023-07-20T15:55:34Z)
• Accelerating Voting by Quantum Computation [35.03314687289671]
  We propose a quantum-accelerated voting algorithm that can be applied to any anonymous voting rule. Our algorithm outputs the correct winner with high probability in $Thetaleft(fracntextMOVright)$ time.
  arXiv  Detail & Related papers  (2023-01-08T07:29:38Z)
• Auditing Ranked Voting Elections with Dirichlet-Tree Models: First Steps [23.14629947453497]
  Ranked voting systems are used in many places around the world. There is no known risk-limiting audit (RLA) method for STV other than a full hand count. We present a new approach to auditing ranked systems that uses a statistical model, a Dirichlet-tree, that can cope with high-dimensional parameters in a computationally efficient manner.
  arXiv  Detail & Related papers  (2022-06-29T13:06:42Z)
• Identifying Possible Winners in Ranked Choice Voting Elections with Outstanding Ballots [0.0]
  ranked-choice voting (RCV) allows voters to rank their choices, and the results are computed in rounds. RCV election outcomes are not always apparent on election night, and can take several weeks to be published. We present an algorithm for efficiently computing possible winners of RCV elections from partially known ballots.
  arXiv  Detail & Related papers  (2022-06-25T22:08:15Z)
• A First Approach to Risk-Limiting Audits for Single Transferable Vote Elections [27.102139020324678]
  Risk-limiting audits (RLAs) are an increasingly important method for checking that the reported outcome of an election is, in fact, correct. This paper presents the first approach to risk-limiting audits for single transferable vote (STV) elections.
  arXiv  Detail & Related papers  (2021-12-18T12:36:39Z)
• Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules [58.8640284079665]
  We study the problem of bribery in multiwinner elections, for the case where the voters cast approval ballots (i.e., sets of candidates they approve) We consider a number of approval-based multiwinner rules (AV, SAV, GAV, RAV, approval-based Chamberlin--Courant, and PAV) In general, our problems tend to be easier when we limit out bribery actions on increasing the number of approvals of the candidate that we want to be in a winning committee.
  arXiv  Detail & Related papers  (2021-04-19T08:26:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.