Voting and Bribing in Single-Exponential Time
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10367616" target="_blank" >RIV/00216208:11320/17:10367616 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2017.46" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.STACS.2017.46</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2017.46" target="_blank" >10.4230/LIPIcs.STACS.2017.46</a>
Alternative languages
Result language
angličtina
Original language name
Voting and Bribing in Single-Exponential Time
Original language description
We introduce a general problem about bribery in voting systems. In the R-Multi-Bribery problem, the goal is to bribe a set of voters at minimum cost such that a desired candidate wins the manipulated election under the voting rule R. Voters assign prices for withdrawing their vote, for swapping the positions of two consecutive candidates in their preference order, and for perturbing their approval count for a candidate. As our main result, we show that R-Multi-Bribery is fixed-parameter tractable parameterized by the number of candidates for many natural voting rules R, including Kemeny rule, all scoring protocols, maximin rule, Bucklin rule, fallback rule, SP-AV, and any C1 rule. In particular, our result resolves the parameterized of R-Swap Bribery for all those voting rules, thereby solving a long-standing open problem and "Challenge #2" of the 9 Challenges in computational social choice by Bredereck et al. Further, our algorithm runs in single-exponential time for arbitrary cost; it thus improves the earlier double-exponential time algorithm by Dorn and Schlotter that is restricted to the unit-cost case for all scoring protocols, the maximin rule, and Bucklin rule.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
ISBN
978-3-95977-028-6
ISSN
1868-8969
e-ISSN
neuvedeno
Number of pages
14
Pages from-to
1-14
Publisher name
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of publication
Dagstuhl, Germany
Event location
Hannover
Event date
Mar 8, 2017
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—