© 2014 Elsevier B.V. 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...Expand abstract
- Publisher copy:
- Copyright date:
articletitle: The complexity of fully proportional representation for single-crossing electorates
journaltitle: Theoretical Computer Science
copyright: Copyright © 2014 Elsevier B.V. All rights reserved.