Szczegóły publikacji
Opis bibliograficzny
Bribery as a measure of candidate success: complexity results for approval-based multiwinner rules / Piotr FALISZEWSKI, Piotr Skowron, Nimrod Talmon // W: AAMAS 2017 [Dokument elektroniczny] : sixteenth international conference on Autonomous Agents and Multiagent Systems : 8–12 May 2017, São Paulo, Brazil / eds. S. Das [et al.]. — Wersja do Windows. — Dane tekstowe. — [USA] : International Foundation for Autonomous Agents and Multiagent Systems, cop. 2017. — S. 6–14. — Wymagania systemowe: Adobe Reader. — Tryb dostępu: http://www.aamas2017.org/proceedings/pdfs/p6.pdf [2017-05-26]. — Bibliogr. s. 14, Abstr.
Autorzy (3)
- AGHFaliszewski Piotr
- Skowron Piotr
- Talmon Nimrod
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 105900 |
|---|---|
| Data dodania do BaDAP | 2017-06-06 |
| Rok publikacji | 2017 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Konferencja | International Joint Conference on Autonomous Agents and Multiagent Systems 2017 |
Abstract
We study the problem of bribery in multiwinner elections, for the case where the voters cast approval ballots (i.e., sets of candidates they approve) and the bribery actions are limited to: adding an approval to a vote, deleting an approval from a vote, or moving an approval within a vote from one candidate to the other. We consider a number of approval-based multiwinner rules (AV, SAV, GAV, RAV, approval-based Chamberlin–Courant, and PAV). We find the landscape of complexity results quite rich, going from polynomial-time algorithms through NP-hardness with constant-factor approximations, to outright inapproximability. Moreover, in general, our problems tend to be easier when we limit out bribery actions on increasing the number of approvals of the candidate that we want to be in a winning committee (i.e., adding approvals only for this preferred candidate, or moving approvals only to him or her). We also study parameterized complexity of our problems, with a focus on parameterizations by the numbers of voters or candidates.
