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
Last month
3
checked on Jun 2, 2023

SCOPUSTM   
Citations

8
Last Week
0
Last month
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.