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%2F68407700%3A21240%2F20%3A00343698" target="_blank" >RIV/68407700:21240/20:00343698 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1145/3396855" target="_blank" >https://doi.org/10.1145/3396855</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/3396855" target="_blank" >10.1145/3396855</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 is a winner in the perturbed 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 to favour candidates. As our main result, we show that R-Multi-Bribery is fixed-parameter tractable parameterized by the number of candidates |C| with only a single-exponential dependence on |C|, for many natural voting rules R, including all natural scoring protocols, maximin rule, Bucklin rule, Fallback rule, SP-AV, and any C1 rule. The vast majority of previous work done in the setting of few candidates proceeds by grouping voters into at most |C|! types by their preference, constructing an integer linear program with |C|!2 variables, and solving it by Lenstra's algorithm in time |C|!|C|!2, hence double-exponential in |C|. Note that it is not possible to encode a large number of different voter costs in this way and still obtain a fixed-parameter algorithm, as that would increase the number of voter types and hence the dimension. These two obstacles of double-exponential complexity and restricted costs have been formulated as "Challenges #1 and #2"of the "Nine Research Challenges in Computational Social Choice"by Bredereck et al. Hence, our result resolves the parameterized complexity of R-Swap-Bribery for the aforementioned voting rules plus Kemeny's rule, and for all rules except Kemeny brings the dependence on |C| down to single-exponential. The engine behind our progress is the use of a new integer linear programming formulation, using so-called "n-fold integer programming."Since its format is quite rigid, we introduce "extended n-fold IP,"which allows many useful modeling tricks. Then, we model R-Multi-Bribery as an extended n-fold IP and ...
Czech name
—
Czech description
—
Classification
Type
J<sub>SC</sub> - Article in a specialist periodical, which is included in the SCOPUS database
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
<a href="/en/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Research Center for Informatics</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2020
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
Name of the periodical
ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION
ISSN
2167-8375
e-ISSN
—
Volume of the periodical
8
Issue of the periodical within the volume
3
Country of publishing house
US - UNITED STATES
Number of pages
28
Pages from-to
"12:1"-"12:28"
UT code for WoS article
000577153400001
EID of the result in the Scopus database
2-s2.0-85093653671