Szczegóły publikacji
Opis bibliograficzny
Algorithms for Destructive Shift Bribery / Andrzej Kaczmarczyk, Piotr FALISZEWSKI // W: AAMAS 2016 [Dokument elektroniczny] : Autonomous Agents and Multiagent Systems : international conference : 9–13 May 2016, Singapore / eds. J. Thangarajah [et al.]. — Wersja do Windows. — Dane tekstowe. — [USA] : International Foundation for Autonomous Agents and Multiagent Systems, cop. 2016. — e-ISBN: 978-1-4503-4239-1. — S. 305–313. — Wymagania systemowe: Adobe Reader. — Tryb dostępu: http://trust.sce.ntu.edu.sg/aamas16/pdfs/p305.pdf [2016-04-29]. — Bibliogr. s. 312–313, Abstr.
Autorzy (2)
- Kaczmarczyk Andrzej
- AGHFaliszewski Piotr
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 97567 |
|---|---|
| Data dodania do BaDAP | 2016-05-10 |
| Rok publikacji | 2016 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Konferencja | International Joint Conference on Autonomous Agents and Multiagent Systems 2016 |
Abstract
We study the complexity of Destructive Shift Bribery. In this problem, we are given an election with a set of candidates and a set of voters (ranking the candidates from best to worst, each), a despised candidate d (typically, one of the current winners), a budget B, and prices for shifting d down in voters' rankings. The goal is to ensure that d is not a winner of the election. We show that this problem is polynomial-time solvable for all scoring protocols (encoded in unary) and the Maximin rule, but is NP-hard for the Copeland rule. This contrasts with the results for the constructive setting (known from the literature), for which the problem is polynomial-time solvable for k-Approval family of rules, but is NP-hard for the Borda, Copeland, and Maximin rules.
