Publisher DOI: | 10.1145/3396855 | arXiv ID: | 1812.01852 | Title: | Voting and bribing in single-exponential time | Language: | English | Authors: | Knop, Dušan Koutecký, Martin Mnich, Matthias ![]() |
Issue Date: | 2020 | Publisher: | ACM | Source: | ACM Transactions on Economics and Computation (2020) | Abstract (english): | We introduce a general problem about bribery in voting systems. In theR-Multi-Briberyproblem,the goal is to bribe a set of voters at minimum cost such that a desired candidate wins the perturbedelection under the voting ruleR. Voters assign prices for withdrawing their vote, for swapping thepositions of two consecutive candidates in their preference order, and for perturbing their approval countto favour candidates.As our main result, we show thatR-Multi-Briberyis fixed-parameter tractable parameterized bythe number of candidates for many natural voting rulesR, including Kemeny rule, all scoring protocols,maximin rule, Bucklin rule, fallback rule, SP-AV, and any C1 rule. In particular, our result resolves theparameterized complexity ofR-Swap Briberyfor all those voting rules, thereby solving a long-standingopen problem and “Challenge #2” of the “Nine Research Challenges in Computational Social Choice”by Bredereck et al.Further, our algorithm runs in single-exponential time for arbitrary cost; it thus improves the earlierdouble-exponential time algorithm by Dorn and Schlotter that is restricted to the uniform-cost case forall scoring protocols, the maximin rule, and Bucklin rule. |
URI: | http://hdl.handle.net/11420/5436 | ISSN: | 2167-8383 | Journal: | ACM Transactions on Economics and Computation | Institute: | Algorithmen und Komplexität E-11 | Document Type: | Article | Project: | Multivariate Algorithmen für Scheduling mit hoher Multiplizität | More Funding information: | Deutsche Forschungsgemeinschaft (DFG) (Projekt MN 59/4-1) |
Appears in Collections: | Publications without fulltext |
Show full item record
Page view(s)
188
Last Week
1
1
Last month
3
3
checked on Jun 2, 2023
SCOPUSTM
Citations
8
Last Week
0
0
Last month
0
0
checked on Jun 30, 2022
Google ScholarTM
Check
Add Files to Item
Note about this record
Cite this record
Export
Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.