Multiwinner Voting with Restricted Admissible Sets: Complexity and Strategyproofness

Yongjie Yang, Jianxin WangIJCAI 2018 · OpenReview

Abstract

Multiwinner voting aims to select a subset of candidates (the winners) from admissible sets, according to the votes cast by voters. A special class of multiwinner rules—the k-committee selection rules where the number of winners is predefined—have gained considerable attention recently. In this setting, the admissible sets are all subsets of candidates of size exactly k. In this paper, we study admissible sets with combinatorial restrictions. In particular, in our setting, we are given a graph G whose vertex set is the candidate set. Admissible sets are the subsets of candidates whose induced subgraphs belong to some special class G of graphs. We consider different graph classes G and investigate the complexity of multiwinner determination problem for prevalent voting rules in this setting. In addition, we investigate the strategyproofness of many rules for different classes of admissible sets.

Introduction

In standard multiwinner voting, often referred to as $k$-committee selection, the only constraint on the winning set is its size. However, real-world applications often involve structural relationships between candidates. For example, a committee might need to be "connected" to ensure effective collaboration, or an "independent set" to avoid conflicts of interest. This paper, presented at IJCAI-18, introduces a graph-based framework to analyze the computational complexity and strategyproofness of voting rules under these combinatorial restrictions.

Methods and Framework

The authors model candidates as vertices in a graph $G = (C, A)$, where edges represent relationships such as travel links or professional conflicts. The set of admissible winners $\mathcal{A}_C^{\mathcal{G}}$ is restricted to subsets of candidates whose induced subgraphs belong to a specific graph class $\mathcal{G}$.

The study evaluates six common approval-based voting rules:

  • AV (Approval Voting) and SAV (Satisfaction Approval Voting)
  • NAV (Net-Approval Voting) and NSAV (Net-SAV)
  • PAV (Proportional Approval Voting) and CCAV (Chamberlin-Courant Approval Voting)

The research focuses on two primary areas: the complexity of the Winner Determination (WD) problem and the strategyproofness of these rules when restricted to specific graph properties like connectivity, independence, or bounded radius.

Complexity of Winner Determination

The complexity of finding a winner varies significantly based on the graph constraints. While most rules are polynomial-time solvable (P) in the "Universal" case (no constraints), adding structural requirements often leads to NP-hardness.

Complexity results for various graph classes and voting rules.

Key insights include:

  • Independence is Hard: Requiring the winners to be an independent set makes all studied rules NP-hard, as it effectively embeds the classic Maximum Independent Set problem.
  • The "Net" Penalty: Rules like NAV and NSAV, which penalize candidates for being disapproved, become NP-hard under connectivity constraints. This occurs because a voter might be forced to include a "bad" (disapproved) candidate to act as a bridge to connect "good" candidates.
  • Treewidth as a Solution: Despite general NP-hardness, most rules become Fixed-Parameter Tractable (FPT) if the candidate graph has a low treewidth (i.e., it is "tree-like").

Strategyproofness under Constraints

A rule is strategyproof if a voter cannot achieve a more preferred outcome by misreporting their preferences. The study finds that graph constraints can strip away strategyproofness from rules that normally possess it.

Strategyproofness of rules across different graph properties (Uni: Universal, Fix: Fixed-size, Ind: Independent, Co: Connected, Rad: Bounded Radius).

For instance, while Approval Voting (AV) is strategyproof in standard $k$-committee selection, it loses this property when winners must form an independent set. Conversely, Chamberlin-Courant Approval Voting (CCAV) stands out for its resilience, remaining strategyproof across all studied graph properties.

Conclusion and Future Work

This work demonstrates that the "topology" of candidates significantly impacts the computational and game-theoretic properties of multiwinner voting. Future research may explore extending proportionality axioms to variable-sized committees with graph constraints or using propositional logic to represent even more complex admissible set requirements.

Summary updated

Abstract

Multiwinner voting aims to select a subset of candidates (the winners) from admissible sets, according to the votes cast by voters. A special class of multiwinner rules—the k-committee selection rules where the number of winners is predefined—have gained considerable attention recently. In this setting, the admissible sets are all subsets of candidates of size exactly k. In this paper, we study admissible sets with combinatorial restrictions. In particular, in our setting, we are given a graph G whose vertex set is the candidate set. Admissible sets are the subsets of candidates whose induced subgraphs belong to some special class G of graphs. We consider different graph classes G and investigate the complexity of multiwinner determination problem for prevalent voting rules in this setting. In addition, we investigate the strategyproofness of many rules for different classes of admissible sets.
BibTeX
@inproceedings{yang2018multiwinner,
  author = {Yongjie Yang and Jianxin Wang},
  title = {{Multiwinner Voting with Restricted Admissible Sets: Complexity and Strategyproofness}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=SkWe6mfuWr},
}
Figure