Prices matter for the parameterized complexity of shift bribery

DOI10.1016/j.ic.2016.08.003zbMath1354.91052arXiv1502.01253OpenAlexW1899117973MaRDI QIDQ342714

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

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

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

Related Items (13)

The complexity of online bribery in sequential elections ⋮ The complexity of priced control in elections ⋮ How hard is safe bribery? ⋮ Hardness and algorithms for electoral manipulation under media influence ⋮ Kernelization complexity of possible winner and coalitional manipulation problems in voting ⋮ Unnamed Item ⋮ Local distance constrained bribery in voting ⋮ Approximation and hardness of shift-Bribery ⋮ Campaign management under approval-driven voting rules ⋮ Frugal bribery in voting ⋮ Computational complexity characterization of protecting elections from bribery ⋮ Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting ⋮ Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules
• Editing graphs to satisfy degree constraints: a parameterized approach
• Average parameterization and partial kernelization for computing medians
• Anyone but him: the complexity of precluding an alternative
• Voting schemes for which it can be difficult to tell who won the election
• How hard is it to control an election?
• Multivariate complexity analysis of Swap Bribery
• Towards a dichotomy for the possible winner problem in elections based on scoring rules
• Parameterized computational complexity of Dodgson and Young elections
• Combinatorial voter control in elections
• Parametrized complexity theory.
• Large-Scale Election Campaigns: Combinatorial Shift Bribery
• Studies in Computational Aspects of Voting
• Determining the winner of a Dodgson election is hard
• New Races in Parameterized Algorithmics
• Determining Possible and Necessary Winners Given Partial Orders
• Integer Programming with a Fixed Number of Variables
• Multimode Control Attacks on Elections
• Elections with Few Candidates: Prices, Weights, and Covering Problems
• Swap Bribery
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• How Hard Is Bribery in Elections?
• Handbook of Computational Social Choice
• A Short Introduction to Computational Social Choice
• A Multivariate Complexity Analysis of Lobbying in Multiple Referenda
• Parameterized Algorithms

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