Szczegóły publikacji
Opis bibliograficzny
Achieving fully proportional representation: approximability results / Piotr Skowron, Piotr FALISZEWSKI, Arkadii Slinko // Artificial Intelligence ; ISSN 0004-3702. — 2015 — vol. 222, s. 67–103. — Bibliogr. s. 102–103, Abstr. — Publikacja dostępna online od: 2015-01-30
Autorzy (3)
- Skowron Piotr
- AGHFaliszewski Piotr
- Slinko Arkadii
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 88290 |
|---|---|
| Data dodania do BaDAP | 2015-03-19 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.artint.2015.01.003 |
| Rok publikacji | 2015 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Artificial Intelligence |
Abstract
We study the complexity of (approximate) winner determination under the Monroe and Chamberlin-Courant multiwinner voting rules, which determine the set of representatives by optimizing the total satisfaction or dissatisfaction of the voters with their representatives. The total (dis)satisfaction is calculated either as the sum of individual (dis)satisfactions in the utilitarian case or as the (dis)satisfaction of the worst off voter in the egalitarian case. We provide good approximation algorithms for the satisfaction-based utilitarian versions of the Monroe and Chamberlin-Courant rules, and inapproximability results for the dissatisfaction-based utilitarian versions of these rules and also for all egalitarian cases. Our algorithms are applicable and particularly appealing when voters submit truncated ballots. We provide experimental evaluation of the algorithms both on real-life preference-aggregation data and on synthetic preference data. These experiments show that our simple and fast algorithms can, in many cases, find near-perfect solutions. (C) 2015 Elsevier B.V. All rights reserved.
