Szczegóły publikacji
Opis bibliograficzny
The complexity of fully proportional representation for single-crossing electorates / Piotr Skowron, Lan Yu, Piotr FALISZEWSKI, Edith Elkind // W: Algorithmic game theory : 6th international symposium, SAGT 2013 : Aachen, Germany, October 21–23, 2013 : proceedings / ed. Berthold Vöcking. — Berlin ; Heidelberg : Springer-Verlag, cop. 2013. — (Lecture Notes in Computer Science ; ISSN 0302-9743 ; LNCS 8146. Advanced Research in Computing and Software Science). — ISBN: 978-3-642-41391-9; e-ISBN: 978-3-642-41392-6. — S. 1–12. — Bibliogr. s. 12, Abstr.
Autorzy (4)
- Skowron Piotr
- Yu Lan
- AGHFaliszewski Piotr
- Elkind Edith
Dane bibliometryczne
| ID BaDAP | 77880 |
|---|---|
| Data dodania do BaDAP | 2013-12-11 |
| DOI | 10.1007/978-3-642-41392-6_1 |
| Rok publikacji | 2013 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Konferencja | 6th International Symposium on Algorithmic Game Theory |
| Czasopismo/seria | Lecture Notes in Computer Science |
Abstract
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.