Complexity of Manipulating and Controlling Approval-Based Multiwinner Voting

Yongjie YangIJCAI 2019 · DOI

TL;DR

This paper dives into the computational complexity of manipulating and controlling outcomes in multiwinner voting systems, specifically those based on approval voting. The authors reveal that while many of these systems are surprisingly resistant to manipulation and control, they also identify specific scenarios and voting rules where these strategic behaviors become computationally challenging, offering a nuanced understanding of their robustness.

What Problem Does This Paper Address?

In democratic processes, ensuring fair and representative outcomes is paramount. When selecting a committee (multiwinner voting) rather than a single winner, the complexity of strategic manipulation and external control becomes a significant concern. Voters might try to influence the outcome to their advantage, or external agents might attempt to steer the election towards specific candidates. This paper tackles the question of how computationally difficult it is to perform these strategic actions for various approval-based multiwinner voting rules. Unlike single-winner voting, where manipulation is well-studied, multiwinner voting introduces complexities in defining voter preferences over committees and in analyzing the impact of strategic votes. The authors aim to map out the computational landscape of these problems for several prominent rules, including Approval Voting (AV), Satisfaction Approval Voting (SAV), Net-Satisfaction Approval Voting (NSAV), Proportional Approval Voting (PAV), Approval-based Chamberlin-Courant Voting (ABCCV), and Minimax Approval Voting (MAV).

Methods

The core of this paper lies in computational complexity analysis. The authors employ standard techniques such as NP-hardness reductions, particularly from the classic VERTEX COVER problem, to demonstrate that certain manipulation and control problems are computationally intractable. They also explore fixed-parameter tractability (FPT) to understand how complexity changes with respect to specific parameters like the number of manipulators or candidates. For problems found to be tractable, they develop polynomial-time algorithms. A key aspect of their work is defining and analyzing two new manipulation problems: Cardinality-Based Coalition Manipulation (CBCM) and Subset-Based Coalition Manipulation (SBCM), where groups of voters coordinate to improve the election outcome without necessarily fixing a target committee. They also extend four standard single-winner control problems to the multiwinner setting: Constructive Control by Adding/Deleting Voters (CCAV/CCDV) and Constructive Control by Adding/Deleting Candidates (CCAC/CCDC).

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity analysis and does not involve empirical evaluation on specific datasets.

Key Insights and Ideas

  • Nuanced Robustness: Contrary to a blanket assumption of vulnerability, many multiwinner voting rules exhibit significant resistance to manipulation and control, especially when the number of manipulators is small.
  • Parameter Sensitivity: The computational difficulty of these problems is highly sensitive to parameters like the number of manipulators, the size of the committee to be elected, and the number of candidates. This suggests that while some scenarios are intractable, others can be solved efficiently.
  • New Manipulation Models: The introduction of CBCM and SBCM provides a more realistic model for coalition manipulation, where manipulators aim to improve the outcome rather than achieve a specific, pre-defined committee.
  • Control Problem Generalizations: Extending single-winner control problems to the multiwinner setting reveals interesting differences and similarities in how these rules respond to external interventions.
  • FPT as a Practical Tool: The identification of FPT results highlights that even for computationally hard problems, efficient algorithms can exist if certain parameters are small, offering practical avenues for analysis.

Key Results

The paper presents a comprehensive complexity analysis for various manipulation and control problems across six multiwinner voting rules.

Manipulation (CBCM/SBCM): * Generally NP-hard for most rules, even with a large number of manipulators. * However, for AV, SAV, and NSAV, these problems become polynomial-time solvable when the number of manipulators is a constant. * These problems are FPT with respect to the number of candidates.

Control Problems: * CCAV/CCDV: Mostly NP-hard, even for a single-winner scenario (k=1), for SAV, NSAV, and MAV. For AV, these are FPT with respect to the number of candidates. * CCAC: AV is immune. SAV and NSAV are NP-hard even for k=1. PAV and ABCCV are immune when the number of distinguished candidates equals k. * CCDC: AV is polynomial-time solvable. SAV and NSAV are NP-hard. PAV and ABCCV are polynomial-time solvable when the number of distinguished candidates equals k. MAV is polynomial-time solvable when k=1. * Several control problems are shown to be FPT with respect to the number of candidates or the combined parameter of added/deleted candidates and the number of voters.

A summary table (Table 1 in the paper) provides a concise overview of these results, categorizing problems as NP-hard, polynomial-time solvable, immune, or fixed-parameter tractable.

Limitations and Future Work

The authors acknowledge that their study is based on worst-case analysis, and practical performance might differ. They suggest that further investigation is needed to understand the real-world difficulty of these problems. Additionally, they point out that for rules like PAV, CCAV, and MAV, where winner determination itself is NP-hard, the manipulation and control problems might belong to even higher complexity classes, leaving this as an open area for future research. Exploring parameterized complexity with respect to only the number of voters for CCAC/CCDC is also suggested as an interesting avenue.

Summary updated

BibTeX
@inproceedings{yang2019complexity,
  author = {Yongjie Yang},
  title = {{Complexity of Manipulating and Controlling Approval-Based Multiwinner Voting}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/90},
}
Figure