Szczegóły publikacji
Opis bibliograficzny
Approximation algorithms for BalancedCC multiwinner rules / Markus Brill, Frank Sommer, Piotr FALISZEWSKI, Nimrod Talmon // W: AAMAS 2019 [Dokument elektroniczny] : 18th international conference on Autonomous Agents and MultiAgent Systems : 13–17 May 2019, Montreal : proceedings. — Wersja do Windows. — Dane tekstowe. — [Montreal] : International Foundation for Autonomous Agents and MultiAgent Systems (IFAAMAS), cop. 2019. — (AAMAS Conference proceedings ; ISSN 2523-5699). — e-ISBN: 978-1-4503-6309-9. — S. 494–502. — Wymagania systemowe: Adobe Reader. — Tryb dostępu: http://www.ifaamas.org/Proceedings/aamas2019/pdfs/p494.pdf [2019-06-07]. — Bibliogr. s. 502, Abstr.
Autorzy (4)
- Brill Markus
- Sommer Frank
- AGHFaliszewski Piotr
- Talmon Nimrod
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 122138 |
|---|---|
| Data dodania do BaDAP | 2019-07-04 |
| Rok publikacji | 2019 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Konferencja | International Joint Conference on Autonomous Agents and Multiagent Systems 2019 |
| Czasopismo/seria | AAMAS Conference proceedings |
Abstract
X-BalancedCC multiwinner voting rules constitute an attractive but computationally intractable compromise between the proportionality provided by the Monroe rule and the diversity provided by the Chamberlin–Courant rule. We show how to use the Greedy- Monroe algorithm to get improved approximation results for the X-BalancedCC rules and for the Chamberlin–Courant rule, by appropriately setting a “schedule” for the sizes of virtual districts. We describe a polynomial-time algorithm for computing a schedule that guarantees high approximation ratio, but show that finding the best possible schedule for a given election is NP-hard. We further evaluate our algorithms experimentally and show that they perform very well in practice.
