On the Complexity of Winner Verification and Candidate Winner for Multiwinner Voting Rules
Chinmay Sonar, Palash Dey, Neeldhara Misra
Abstract
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) dissatisfaction 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 Theta_2^P. Our contribution fills an essential gap in the literature for these important multi-winner rules.
BibTeX
@inproceedings{ijcai2020p13,
title = {On the Complexity of Winner Verification and Candidate Winner for Multiwinner Voting Rules},
author = {Sonar, Chinmay and Dey, Palash and Misra, Neeldhara},
booktitle = {Proceedings of the Twenty-Ninth International Joint Conference on
Artificial Intelligence, {IJCAI-20}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Christian Bessiere},
pages = {89--95},
year = {2020},
month = {7},
note = {Main track},
doi = {10.24963/ijcai.2020/13},
url = {https://doi.org/10.24963/ijcai.2020/13},
}