Chen, J., Hatschka, C., & Simola, S. (2023). Efficient Algorithms for Monroe and CC Rules in Multi-Winner Elections with (Nearly) Structured Preferences. In ECAI 2023 : 26th European Conference on Artificial Intelligence, September 30–October 4, 2023, Kraków, Poland. Including 12th Conference on Prestigious Applications of Intelligent Systems (PAIS 2023). Proceedings (pp. 397–404). IOS Press. https://doi.org/10.3233/FAIA230296
E192-01 - Forschungsbereich Algorithms and Complexity
-
Published in:
ECAI 2023 : 26th European Conference on Artificial Intelligence, September 30–October 4, 2023, Kraków, Poland. Including 12th Conference on Prestigious Applications of Intelligent Systems (PAIS 2023). Proceedings
ECAI 2023: 26th European Conference on Artificial Intelligence
-
Event date:
30-Sep-2023 - 4-Oct-2023
-
Event place:
Krakow, Poland
-
Number of Pages:
8
-
Publisher:
IOS Press
-
Peer reviewed:
Yes
-
Keywords:
Efficient Algorithms; multi-winner elections; Social Choice; winner determination
en
Abstract:
We investigate winner determination for two popular proportional representation systems: the Monroe and Chamberlin-Courant (abbrv. CC) systems. Our study focuses on (nearly) single-peaked resp. single-crossing preferences. We show that for single-crossing approval preferences, winner determination of the Monroe rule is polynomial, and for both rules, winner determination mostly admits FPT algorithms with respect to the number of voters to delete to obtain single-peaked or single-crossing preferences. Our results answer some complexity questions from the literature [19, 29, 22].
en
Project title:
Structural and Algorithmic Aspects of Preference-based Problems in Social Choice: VRG18-012 (WWTF Wiener Wissenschafts-, Forschu und Technologiefonds)
CC BY-NC 4.0
