Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules

• URL: http://arxiv.org/abs/2104.09130v1
• Date: Mon, 19 Apr 2021 08:26:40 GMT
• Title: Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules
• Authors: Piotr Faliszewski and Piotr Skowron and Nimrod Talmon
• Abstract summary: 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.
• Score: 58.8640284079665
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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) and the bribery actions are limited to: adding an approval to a vote, deleting an approval from a vote, or moving an approval within a vote from one candidate to the other. We consider a number of approval-based multiwinner rules (AV, SAV, GAV, RAV, approval-based Chamberlin--Courant, and PAV). We find the landscape of complexity results quite rich, going from polynomial-time algorithms through NP-hardness with constant-factor approximations, to outright inapproximability. Moreover, 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 (i.e., adding approvals only for this preferred candidate, or moving approvals only to him or her). We also study parameterized complexity of our problems, with a focus on parameterizations by the numbers of voters or candidates.

Related papers

• Multiwinner Temporal Voting with Aversion to Change [30.15852603215344]
  We study two-stage committee elections where voters have dynamic preferences over candidates. At each stage, a committee is chosen under a given voting rule. We show a full complexity dichotomy for the class of Thiele rules.
  arXiv  Detail & Related papers  (2024-08-20T17:16:54Z)
• 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)
• 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)
• On the Complexity of Winner Determination and Strategic Control in Conditional Approval Voting [13.207754600697138]
  Conditional Minisum (CMS) is a voting rule for multi-issue elections with preferential dependencies. We show that CMS can be viewed as a solution that achieves a satisfactory tradeoff between expressiveness and computational efficiency.
  arXiv  Detail & Related papers  (2022-02-03T16:15:54Z)
• 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)
• Modeling Voters in Multi-Winner Approval Voting [24.002910959494923]
  We study voting behavior in single-winner and multi-winner approval voting scenarios with varying degrees of uncertainty. We find that people generally manipulate their vote to obtain a better outcome, but often do not identify the optimal manipulation. We propose a novel model that takes into account the size of the winning set and human cognitive constraints.
  arXiv  Detail & Related papers  (2020-12-04T19:24:28Z)
• 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)
• Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
  We study the public persuasion problem in the general setting with: (i) arbitrary state spaces; (ii) arbitrary action spaces; (iii) arbitrary sender's utility functions. We provide a quasi-polynomial time bi-criteria approximation algorithm for arbitrary public persuasion problems that, in specific settings, yields a QPTAS.
  arXiv  Detail & Related papers  (2020-02-12T18:59:18Z)
• Evaluating approval-based multiwinner voting in terms of robustness to noise [10.135719343010177]
  We show that approval-based multiwinner voting is always robust to reasonable noise. We further refine this finding by presenting a hierarchy of rules in terms of how robust to noise they are.
  arXiv  Detail & Related papers  (2020-02-05T13:17:43Z)

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.