Voting and Bribing in Single-Exponential Time
Voting and Bribing in Single-Exponential Time
复制标题
单指数时间内的投票和贿赂
DOI：
10.1145/3396855
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Matthias Mnich
中科院分区：
文献类型：
--
作者：
D. Knop;Martin Koutecký;Matthias Mnich
我们在R-Multi-Bribery问题中引入了有关贿赂的一般问题，目的是以最低费用贿赂一组选民，以便在投票规则R.选民指派撤回投票的价格，以他们的优先顺序交换了两个连续的候选人的职位，并扰乱了他们的认可数以偏爱候选人。是固定参数可通过候选人数量| C |的参数，只有单个指数依赖于| c | AV和任何C1规则。变量，并通过Lenstra的算法在时间| C |！固定参数算法，因为这将增加选民类型的数量，从而增加了这两个障碍。 Bredereck等人的计算社会选择挑战单个指数。我们介绍了许多有用的建模技巧。
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 apply an algorithm of Hemmecke et al. [Math. Prog. 2013].
登录
查看更多内容
巴克林的操纵、贿赂和竞选管理的复杂性以及后备投票
影响因子：
1.9
作者：
P. Faliszewski;Y. Reisch;J. Rothe;L. Schend
通讯作者：
L. Schend
路径破坏博弈：贿赂和概率模型
影响因子：
0.5
作者：
A. Rey;J. Rothe;A. Marple
通讯作者：
A. Marple
候选人很少的选举：价格、权重和覆盖问题
DOI：
10.1007/978-3-319-23114-3_25
发表时间：
2015
期刊：
影响因子：
--
作者：
Robert Bredereck;Piotr Faliszewski;Rolf Niedermeier;Piotr Skowron;Nimrod Talmon
通讯作者：
Nimrod Talmon
基于统一前提的配额规则判断汇总中操纵和贿赂的复杂性
DOI：
10.1016/j.mathsocsci.2015.03.006
发表时间：
2015
期刊：
Math. Soc. Sci.
影响因子：
--
作者：
D. Baumeister;G. Erdélyi;O. Erdélyi;J. Rothe
通讯作者：
J. Rothe