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
- 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) - Computing Voting Rules with Elicited Incomplete Votes [11.550634521005968]
We study voting rules that are computable by querying voters about $t m$ candidates.
For scoring rules that are computable with limited-sized queries, we give parameterized upper and lower bounds on the number of such queries.
arXiv Detail & Related papers (2024-02-16T22:17: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) - 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) - Online Approval Committee Elections [20.217228946041168]
We show how to compute committees with maximal expected score.
We assume $k$ candidates need to be selected. The candidates appear over time. Each time one appears, it must be immediately selected or rejected.
arXiv Detail & Related papers (2022-02-14T16:06:47Z) - 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) - Adaptive Combinatorial Allocation [77.86290991564829]
We consider settings where an allocation has to be chosen repeatedly, returns are unknown but can be learned, and decisions are subject to constraints.
Our model covers two-sided and one-sided matching, even with complex constraints.
arXiv Detail & Related papers (2020-11-04T15:02:59Z) - MS-Ranker: Accumulating Evidence from Potentially Correct Candidates for
Answer Selection [59.95429407899612]
We propose a novel reinforcement learning based multi-step ranking model, named MS-Ranker.
We explicitly consider the potential correctness of candidates and update the evidence with a gating mechanism.
Our model significantly outperforms existing methods that do not rely on external resources.
arXiv Detail & Related papers (2020-10-10T10:36:58Z)
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.