# On the complexity of Winner Verification and Candidate Winner for Multiwinner Voting Rules

arXiv: https://arxiv.org/abs/2004.13933 · HTML: https://mlsanity.com/paper/2004.13933/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Apr 2020.

## Built on by (most cited first, 2 of 2)

- [DiRe Committee : Diversity and Representation Constraints in Multiwinner Elections](https://mlsanity.com/paper/2107.07356/) (2021)
- [The Complexity of Learning Approval-Based Multiwinner Voting Rules](https://mlsanity.com/paper/2110.00254/) (2021)

## Abstract (arXiv)

The Chamberlin-Courant and Monroe rules are fundamental and well-studied rules in the literature of multi-winner elections. The problem of determining if there exists a committee of size k that has a Chamberlin-Courant (respectively, Monroe) score of at most r is known to be NP-complete. We consider the following natural problems in this setting: a) given a committee S of size k as input, is it an optimal k-sized committee, and b) given a candidate c and a committee size k, does there exist an optimal k-sized committee that contains c? In this work, we resolve the complexity of both problems for the Chamberlin-Courant and Monroe voting rules in the settings of rankings as well as approval ballots. We show that verifying if a given committee is optimal is coNP-complete whilst the latter problem is complete for Theta2P. We also demonstrate efficient algorithms for the second problem when the input consists of single-peaked rankings. Our contribution fills an essential gap in the literature for these important multi-winner rules.