Complexity of Manipulating and Controlling Approval-Based Multiwinner Voting

2023/02/22 by Yang, Yongjie · 2 citations
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2302.11291

Abstract

We investigate the complexity of several manipulation and control problems under numerous prevalent approval-based multiwinner voting rules. Particularly, the rules we study include approval voting (AV), satisfaction approval voting (SAV), net-satisfaction approval voting (NSAV), proportional approval voting (PAV), approval-based Chamberlin-Courant voting (ABCCV), minimax approval voting (MAV), etc. We show that these rules generally resist the strategic types scrutinized in the paper, with only a few exceptions. In addition, we also obtain many fixed-parameter tractability results for these problems with respect to several natural parameters, and derive polynomial-time algorithms for certain special cases.

Cited by

• How Hard Is It to Impact the Impact of Your Paper?
• Algorithms for Candidate Control in Greedy Participatory Budgeting Rules

Related

• On the Complexity of Destructive Bribery in Approval-Based Multi-winner Voting
• On the Parameterized Complexity of Controlling Approval-Based Multiwinner Voting: Destructive Model & Sequential Rules
• Computational Aspects of Multi-Winner Approval Voting
• Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules
• Algorithms for two variants of Satisfaction Approval Voting