2022/02/24 by Jiehua Chen, Sanjukta Roy, Chen, Jiehua +1 · 1 citation
Economics, Econometrics and Finance · Social Sciences · #Artificial Intelligence (cs.AI) #Computer Science and Game Theory (cs.GT) #Electoral Systems and Political Participation #European Monetary and Fiscal Policies #FOS: Computer and information sciences #Game Theory and Voting Systems #Multiagent Systems (cs.MA)
paper · pdf · doi:10.48550/arxiv.2202.12006
openalex publication_date 2022/02/24 · openalex created_date 2022/04/03 · openalex updated_date 2026/07/28
Answering an open question by Betzler et al. [Betzler et al., JAIR'13], we resolve the parameterized complexity of the multi-winner determination problem under two famous representation voting rules: the Chamberlin-Courant (in short CC) rule [Chamberlin and Courant, APSR'83] and the Monroe rule [Monroe, APSR'95]. We show that under both rules, the problem is W[1]-hard with respect to the sum β of misrepresentations, thereby precluding the existence of any f(β) ⋅ |I|O(1) -time algorithm, where |I| denotes the size of the input instance.