Multivariate complexity analysis of swap bribery

DOI10.1007/978-3-642-17493-3_12MaRDI QIDQ3058696zbMATH OpenOpenAlexFDO

Authors B. Dorn, Ildikó Schlotter

Publication date 7 December 2010

Published in Parameterized and Exact Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: We consider the computational complexity of a problem modeling bribery in the context of voting systems. In the scenario of Swap Bribery, each voter assigns a certain price for swapping the positions of two consecutive candidates in his preference ranking. The question is whether it is possible, without exceeding a given budget, to bribe the voters in a way that the preferred candidate wins in the election. We initiate a parameterized and multivariate complexity analysis of Swap Bribery, focusing on the case of k-approval. We investigate how different cost functions affect the computational complexity of the problem. We identify a special case of k-approval for which the problem can be solved in polynomial time, whereas we prove NP-hardness for a slightly more general scenario. We obtain fixed-parameter tractability as well as W[1]-hardness results for certain natural parameters.

Recommendations

• Multivariate complexity analysis of Swap Bribery
• Prices matter for the parameterized complexity of shift bribery
• Voting and bribing in single-exponential time
• Complexity of shift bribery in committee elections
• How hard is bribery in elections?

Cites work

• Dichotomy for voting systems
• How hard is bribery in elections?
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Integer Programming with a Fixed Number of Variables
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• On complexity of lobbying in multiple referenda
• On problem kernels for possible winner determination under the k-approval protocol
• On the parameterized complexity of multiple-interval graph problems
• Parameterized complexity of candidate control in elections and related digraph problems
• Parameterized computational complexity of control problems in voting systems
• Reflections on multivariate algorithmics and problem parameterization
• Swap bribery
• Towards a dichotomy for the possible winner problem in elections based on scoring rules
• When are elections with few candidates hard to manipulate?

Cited in

(4)

• Multivariate complexity analysis of Swap Bribery
• Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
• Prices matter for the parameterized complexity of shift bribery
• Computational complexity characterization of protecting elections from bribery

This page was built for publication: Multivariate complexity analysis of swap bribery

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