Determining Winners in Elections with Absent Votes
- URL: http://arxiv.org/abs/2310.07150v1
- Date: Wed, 11 Oct 2023 02:52:16 GMT
- Title: Determining Winners in Elections with Absent Votes
- Authors: Qishen Han and Am\'elie Marian and Lirong Xia
- Abstract summary: We study the determining winner with the absent votes problem when the votes are top-truncated.
We show that the WAV problem is NP-complete for the single transferable vote.
We propose a special case of positional scoring rule such that the problem can be computed in time.
- Score: 26.675597212113658
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: An important question in elections is the determine whether a candidate can
be a winner when some votes are absent. We study this determining winner with
the absent votes (WAV) problem when the votes are top-truncated. We show that
the WAV problem is NP-complete for the single transferable vote, Maximin, and
Copeland, and propose a special case of positional scoring rule such that the
problem can be computed in polynomial time. Our results in top-truncated
rankings differ from the results in full rankings as their hardness results
still hold when the number of candidates or the number of missing votes are
bounded, while we show that the problem can be solved in polynomial time in
either case.
Related papers
- Verifying Proportionality in Temporal Voting [29.69443607539022]
We study a model of temporal voting where there is a fixed time horizon, and at each round the voters report their preferences over the available candidates.
We focus on the complexity of verifying whether a given outcome offers proportional representation.
arXiv Detail & Related papers (2025-02-09T16:30:34Z) - Efficient Lower Bounding of Single Transferable Vote Election Margins [56.12949230611067]
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.
arXiv Detail & Related papers (2025-01-24T13:39:23Z) - 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) - 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) - 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) - Expected Frequency Matrices of Elections: Computation, Geometry, and
Preference Learning [58.23459346724491]
We use the "map of elections" approach of Szufa et al. (AAMAS 2020) to analyze several well-known vote distributions.
We draw the "skeleton map" of distributions, evaluate its robustness, and analyze its properties.
arXiv Detail & Related papers (2022-05-16T17:40:22Z) - The Complexity of Learning Approval-Based Multiwinner Voting Rules [9.071560867542647]
We study the learnability of multiwinner voting, focusing on the class of approval-based committee scoring (ABCS) rules.
Our goal is to learn a target rule (i.e., to learn the corresponding scoring function) using information about the winning committees of a small number of profiles.
We prove that deciding whether there exists some ABCS rule that makes a given committee winning in a given profile is a hard problem.
arXiv Detail & Related papers (2021-10-01T08:25:05Z) - 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.