Chen, J., Hatschka, C., & Simola, S. H. E. (2024, December 11). Multi-Winner Reconfiguration [Poster Presentation]. 38th Annual Conference on Neural Information Processing Systems, Vancouver, Canada. http://hdl.handle.net/20.500.12708/210385
E192-01 - Forschungsbereich Algorithms and Complexity
-
Datum (veröffentlicht):
11-Dez-2024
-
Veranstaltungsname:
38th Annual Conference on Neural Information Processing Systems
en
Veranstaltungszeitraum:
10-Dez-2024 - 15-Dez-2024
-
Veranstaltungsort:
Vancouver, Kanada
-
Keywords:
multi-winner reconfiguration model; Social Choice; Parameterized algorithms
en
Abstract:
We introduce a multi-winner reconfiguration model to examine how to transition between subsets of alternatives (aka. committees) through a sequence of minor yet impactful modifications, called reconfiguration path. We analyze this model under four approval-based voting rules: Chamberlin-Courant (CC), Proportional Approval Voting (PAV), Approval Voting (AV), and Satisfaction Approval Voting (SAV). The problem exhibits computational intractability for CC and PAV, and polynomial solvability for AV and SAV. We provide a detailed multivariate complexity analysis for CC and PAV, demonstrating that although the problem remains challenging in many scenarios, there are specific cases that allow for efficient parameterized algorithms.