2012/08/08 by Piotr Skowron, Piotr Faliszewski, Skowron, Piotr +3 · 2 citations
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #68Q17 #Auction Theory and Applications #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #F.2.2 #FOS: Computer and information sciences #Game Theory and Voting Systems #I.2.11 #Multiagent Systems (cs.MA) #acm:68Q17 #cs.GT #cs.MA #msc:68Q17
paper · pdf · doi:10.48550/arxiv.1208.1661
26 pages, 1 figure
openalex publication_date 2012/08/08 · arxiv created 2013/01/27 · arxiv updated 2013/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We model Monroe's and Chamberlin and Courant's multiwinner voting systems as a certain resource allocation problem. We show that for many restricted variants of this problem, under standard complexity-theoretic assumptions, there are no constant-factor approximation algorithms. Yet, we also show cases where good approximation algorithms exist (briefly put, these variants correspond to optimizing total voter satisfaction under Borda scores, within Monroe's and Chamberlin and Courant's voting systems).