Prices matter for the parameterized complexity of shift bribery

DOI10.1016/J.IC.2016.08.003MaRDI QIDQ342714zbMATH OpenOpenAlexFDO

Authors Robert Bredereck, Jiehua Chen, Piotr Faliszewski, André Nichterlein, Rolf Niedermeier

Publication date 18 November 2016

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.01253

zbMATH Keywords

computational social choicefixed-parameter tractability (FPT)\(\mathsf{W}\)-hardnessFPT approximation schememultivariate complexity analysisvoting and rank aggregation

Mathematics Subject Classification ID

Social choice (91B14) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Voting theory (91B12)

Abstract: In the Shift Bribery problem, we are given an election (based on preference orders), a preferred candidate $p$, and a budget. The goal is to ensure that $p$ wins by shifting $p$ higher in some voters' preference orders. However, each such shift request comes at a price (depending on the voter and on the extent of the shift) and we must not exceed the given budget. We study the parameterized computational complexity of Shift Bribery with respect to a number of parameters (pertaining to the nature of the solution sought and the size of the election) and several classes of price functions. When we parameterize Shift Bribery by the number of affected voters, then for each of our voting rules (Borda, Maximin, Copeland) the problem is W[2]-hard. If, instead, we parameterize by the number of positions by which $p$ is shifted in total,then the problem is fixed-parameter tractable for Borda and Maximin,and is W[1]-hard for Copeland. If we parameterize by the budget, then the results depend on the price function class. We also show that Shift Bribery tends to be tractable when parameterized by the number of voters, but that the results for the number of candidates are more enigmatic.

Recommendations

• Complexity of shift bribery in committee elections
• Approximation and hardness of shift-bribery
• Large-scale election campaigns: combinatorial shift bribery
• Multivariate complexity analysis of swap bribery
• Multivariate complexity analysis of Swap Bribery

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A Multivariate Complexity Analysis of Lobbying in Multiple Referenda
• A Short Introduction to Computational Social Choice
• Anyone but him: the complexity of precluding an alternative
• Average parameterization and partial kernelization for computing medians
• Combinatorial voter control in elections
• Determining possible and necessary winners given partial orders
• Determining the winner of a Dodgson election is hard
• Editing graphs to satisfy degree constraints: a parameterized approach
• Elections with few candidates: prices, weights, and covering problems
• Fundamentals of parameterized complexity
• Handbook of Computational Social Choice
• How hard is bribery in elections?
• How hard is it to control an election?
• Integer Programming with a Fixed Number of Variables
• Large-scale election campaigns: combinatorial shift bribery
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• Multimode control attacks on elections
• Multivariate complexity analysis of Swap Bribery
• Network flows. Theory, algorithms, and applications.
• New races in parameterized algorithmics
• Parameterized algorithms
• Parameterized computational complexity of Dodgson and Young elections
• Parametrized complexity theory.
• Studies in Computational Aspects of Voting
• Swap bribery
• Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules
• Towards a dichotomy for the possible winner problem in elections based on scoring rules
• Voting schemes for which it can be difficult to tell who won the election

Cited in

(18)

• The complexity of online bribery in sequential elections
• Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting
• Large-scale election campaigns: combinatorial shift bribery
• Elections with few candidates: prices, weights, and covering problems
• Computational complexity characterization of protecting elections from bribery
• Campaign management under approval-driven voting rules
• Often Harder than in the Constructive Case: Destructive Bribery in CP-nets
• Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
• Kernelization complexity of possible winner and coalitional manipulation problems in voting
• How hard is safe bribery?
• Multivariate complexity analysis of swap bribery
• The complexity of priced control in elections
• Complexity of shift bribery in committee elections
• scientific article; zbMATH DE number 7450032 (Why is no real title available?)
• Local distance constrained bribery in voting
• Frugal bribery in voting
• Hardness and algorithms for electoral manipulation under media influence
• Approximation and hardness of shift-bribery

This page was built for publication: Prices matter for the parameterized complexity of shift bribery

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q342714)