Szczegóły publikacji
Opis bibliograficzny
Complexity of Shift Bribery in committee elections / Robert Bredereck, Piotr FALISZEWSKI, Rolf Niedermeier, Nimrod Talmon // ACM Transactions on Computation Theory ; ISSN 1942-3454. — 2021 — vol. 13 iss. 3 art. no. 20, s. 1–25. — Bibliogr. s. 23–25, Abstr. — Publikacja dostępna online od: 2021-12-23. — An extended abstract of this article appeared in the Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI’16), pages 2452–2458
Autorzy (4)
- Bredereck Robert
- AGHFaliszewski Piotr
- Niedermeier Rolf
- Talmon Nimrod
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 138823 |
|---|---|
| Data dodania do BaDAP | 2022-01-25 |
| Tekst źródłowy | URL |
| DOI | 10.1145/3470647 |
| Rok publikacji | 2021 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | ACM Transactions on Computation Theory |
Abstract
Given an election, a preferred candidate p, and a budget, the SHIFT BRIBERY problem asks whether p can win the election after shifting p higher in some voters' preference orders. Of course, shifting comes at a price (depending on the voter and on the extent of the shift) and one must not exceed the given budget. We study the (parameterized) computational complexity of SHIFT BRIBERY for multiwinner voting rules where winning the election means to be part of some winning committee. We focus on the well-established SNTV, Bloc, k-Borda, and Chamberlin-Courant rules, as well as on approximate variants of the Chamberlin-Courant rule. We show that SHIFT BRIBERY tends to be harder in the multiwinner setting than in the single-winner one by showing settings where SHIFT BRIBERY is computationally easy in the single-winner cases, but is hard (and hard to approximate) in the multiwinner ones.
