Options
Voting and bribing in single-exponential time
Citation Link: https://doi.org/10.15480/882.14153
Publikationstyp
Journal Article
Date Issued
2020-06-20
Sprache
English
Institut
TORE-DOI
TORE-URI
Volume
8
Issue
3
Article Number
12
Citation
ACM Transactions on Economics and Computation 8 (3): 12 (2020)
Publisher DOI
Scopus ID
ArXiv ID
Publisher
ACM
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.
Subjects
Voting system
swap bribery
integer programming
DDC Class
004: Informatik
More Funding Information
Deutsche Forschungsgemeinschaft (DFG) (Projekt MN 59/4-1)
Loading...
Name
3396855.pdf
Type
Main Article
Size
1.61 MB
Format
Adobe PDF