Voting and Bribing in Single-Exponential Time

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Voting and Bribing in Single-Exponential Time

Popis výsledku v původním jazyce

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 ...

Název v anglickém jazyce

Voting and Bribing in Single-Exponential Time

Popis výsledku anglicky

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 ...

Druh

J_SC - Článek v periodiku v databázi SCOPUS

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Výzkumné centrum informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION

ISSN

2167-8375

e-ISSN

—

Svazek periodika

8

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

28

Strana od-do

"12:1"-"12:28"

Kód UT WoS článku

000577153400001

EID výsledku v databázi Scopus

2-s2.0-85093653671