Szczegóły publikacji
Opis bibliograficzny
The complexity of fully proportional representation for single-crossing electorates / Piotr Skowron, Lan Yu, Piotr FALISZEWSKI, Edith Elkind // Theoretical Computer Science ; ISSN 0304-3975. — 2015 — vol. 569, s. 43–57. — Bibliogr. s. 57, Abstr.
Autorzy (4)
- Skowron Piotr
- Yu Lan
- AGHFaliszewski Piotr
- Elkind Edith
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 87741 |
|---|---|
| Data dodania do BaDAP | 2015-02-11 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.tcs.2014.12.012 |
| Rok publikacji | 2015 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Theoretical 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. We then consider elections that are both single-peaked and single-crossing, and develop an efficient algorithm for the egalitarian variant of Monroe's rule for such elections. While Betzler et al. [3] have recently presented a polynomial-time algorithm for this rule under single-peaked preferences, our algorithm has considerably better worst-case running time than that of Betzler et al. (C) 2014 Elsevier B.V. All rights reserved.
