Abstract
In multiwinner approval voting, the goal is to select a k-member committee based on voters' approval ballots. A well-studied concept of proportionality in this context is the justified representation (JR) axiom, which demands that no large cohesive group of voters remains unrepresented. However, the JR axiom may conflict with other desiderata, such as social welfare (the number of approvals obtained by committee members) or coverage (the number of voters who approve at least one committee member). In this article, we investigate the price of imposing the JR axiom (as well as the more demanding extended justified representation axiom) on social welfare and coverage. Our approach is twofold: We derive worst-case bounds on the loss of welfare/coverage caused by imposing JR and study the computational complexity of finding committees with high welfare that provide JR (obtaining hardness results, approximation algorithms, and an exact algorithm for one-dimensional preferences).
| Original language | English (US) |
|---|---|
| Article number | 11 |
| Journal | ACM Transactions on Economics and Computation |
| Volume | 12 |
| Issue number | 3 |
| DOIs | |
| State | Published - Sep 6 2024 |
Funding
This project has received funding from the European Research Council (ERC) under the European Union\u2019s Horizon 2020 research and innovation programme (grant agreement No 101002854), from the Deutsche Forschungsgemeinschaft under grant BR 4744/2-1, from JST PRESTO under grant number JPMJPR20C1, from the Singapore Ministry of Education under grant number MOE-T2EP20221-0001, and from an NUS Start-up Grant. A preliminary version of the article appeared in Proceedings of the 36th AAAI Conference on Artificial Intelligence, February-March 2022. We thank the anonymous reviewers of AAAI 2022 and ACM Transactions on Economics and Computation for their valuable comments. This project has received funding from the European Research Council (ERC) under the European Union\u2019s Horizon 2020 research and innovation programme (grant agreement No 101002854), from the Deutsche Forschungsgemeinschaft under grant BR 4744/2-1, from JST PRESTO under grant number JPMJPR20C1, from the Singapore Ministry of Education under grant number MOE-T2EP20221-0001, and from an NUS Start-up Grant. A preliminary version of the article appeared in Proceedings of the 36th AAAI Conference on Artificial Intelligence, February\u2013March 2022 [Elkind et al. ].
Keywords
- Additional Key Words and PhrasesJustified representation
- computational social choice
- multiwinner voting
ASJC Scopus subject areas
- Computer Science (miscellaneous)
- Statistics and Probability
- Economics and Econometrics
- Marketing
- Computational Mathematics