Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
The Complexity of Fully Proportional Representation for Single-Crossing Electorates
verfasst von : Piotr Skowron, Lan Yu, Piotr Faliszewski, Edith Elkind
Erschienen in: Algorithmic Game Theory
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.