Journal article icon

Journal article

The complexity of fully proportional representation for single-crossing electorates.

Abstract:

© 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

Actions


Access Document


Publisher copy:
10.1016/j.tcs.2014.12.012

Authors


Skowron, P More by this author
Faliszewski, P More by this author
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Journal:
Theor. Comput. Sci.
Volume:
569
Issue:
C
Pages:
43-57
Publication date:
2015
DOI:
ISSN:
0304-3975
URN:
uuid:909fa8d9-bb9f-4ea0-80aa-877a1a8f8f00
Source identifiers:
518402
Local pid:
pubs:518402

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP