Multivariate complexity analysis of Swap Bribery

DOI10.1007/s00453-011-9568-4zbMath1283.68161OpenAlexW2049720957MaRDI QIDQ1759677

Britta Dorn, Ildikó Schlotter

Publication date: 21 November 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9568-4

zbMATH Keywords

computational social choiceparameterized complexitySwap Bribery

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) Social choice (91B14)

Related Items (20)

Parameterized Resiliency Problems via Integer Linear Programming ⋮ Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control ⋮ The complexity of priced control in elections ⋮ On the hardness of bribery variants in voting with CP-nets ⋮ Studies in Computational Aspects of Voting ⋮ Prices matter for the parameterized complexity of shift bribery ⋮ How hard is safe bribery? ⋮ The possible winner with uncertain weights problem ⋮ Kernelization complexity of possible winner and coalitional manipulation problems in voting ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ Bribery in voting with CP-nets ⋮ Local distance constrained bribery in voting ⋮ Approximation and hardness of shift-Bribery ⋮ Campaign management under approval-driven voting rules ⋮ Frugal bribery in voting ⋮ Robustness among multiwinner voting rules ⋮ Exact algorithms for weighted and unweighted Borda manipulation problems ⋮ Unnamed Item ⋮ Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting ⋮ Parameterized resiliency problems

Cites Work

• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Dichotomy for voting systems
• On the parameterized complexity of multiple-interval graph problems
• Parameterized computational complexity of control problems in voting systems
• Parameterized complexity of candidate control in elections and related digraph problems
• Towards a dichotomy for the possible winner problem in elections based on scoring rules
• On complexity of lobbying in multiple referenda
• Determining Possible and Necessary Winners Given Partial Orders
• Integer Programming with a Fixed Number of Variables
• Multimode Control Attacks on Elections
• Reflections on Multivariate Algorithmics and Problem Parameterization
• When are elections with few candidates hard to manipulate?
• On Problem Kernels for Possible Winner Determination under the k-Approval Protocol
• Swap Bribery
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• How Hard Is Bribery in Elections?
• Kernelization: New Upper and Lower Bound Techniques
• Color-coding

This page was built for publication: Multivariate complexity analysis of Swap Bribery