2013/07/04 by Piotr Skowron, Skowron, Piotr, Lan Yu +6
Computer Science · Economics, Econometrics and Finance · #68Q17 #Advanced Graph Theory Research #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.1307.1252
23 pages
arxiv created 2013/07/04 · openalex publication_date 2013/07/04 · arxiv updated 2013/07/05 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
We study the complexity of winner determination in single-crossing elections under two classic fully proportional representation rules---Chamberlin--Courant's rule and Monroe's rule. Winner determination for these rules is known to be NP-hard for unrestricted preferences. We show that for single-crossing preferences this problem admits a polynomial-time algorithm for Chamberlin--Courant's rule, but remains NP-hard for Monroe's rule. Our algorithm for Chamberlin--Courant's rule can be modified to work for elections with bounded single-crossing width. To circumvent the hardness result for Monroe's rule, we consider single-crossing elections that satisfy an additional constraint, namely, ones where each candidate is ranked first by at least one voter (such elections are called narcissistic). For single-crossing narcissistic elections, we provide an efficient algorithm for the egalitarian version of Monroe's rule.