Szczegóły publikacji
Opis bibliograficzny
Complexity of Shift Bribery in committee elections / Robert Bredereck, Piotr FALISZEWSKI, Rolf Niedermeier, Nimrod Talmon // W: AAAI-16 [Dokument elektroniczny] : thirtieth AAAI conference on Artificial Intelligence : February 12–17 2016, Phoenix, Arizona USA / Association of the Advancement of Artificial Intelligence. — Wersja do Windows. — Dane tekstowe. — Palo Alto : AAAI Press, [2016]. — e-ISBN: 978-157735760-5. — S. 2452–2458. — Wymagania systemowe: Adobe Reader. — Tryb dostępu: http://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/1236... [2016-04-29]. — Bibliogr. s. 2458, Abstr.
Autorzy (4)
- Bredereck Robert
- AGHFaliszewski Piotr
- Niedermeier Rolf
- Talmon Nimrod
Dane bibliometryczne
| ID BaDAP | 97563 |
|---|---|
| Data dodania do BaDAP | 2016-05-10 |
| Rok publikacji | 2016 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Konferencja | National Conference of the American Association for Artificial Intelligence 2016 |
Abstract
We study the (parameterized) complexity of SHIFT BRIBERY for multiwinner voting rules. We focus on the SNTV, Bloc, k-Borda, and Chamberlin–Courant rules, as well as on ap- proximate variants of the Chamberlin–Courant rule, since the original rule is NP-hard to compute. We show that SHIFT BRIBERY tends to be significantly harder in the multi-winner setting than in the single-winner one by showing settings where SHIFT BRIBERY is easy in the single-winner cases, but is hard (and hard to approximate) in the multi-winner ones. We show that the non-monotonicity of those rules which are based on approximation algorithms for the Chamberlin–Courant rule sometimes affects the complexity of SHIFT BRIBERY.
