Combinatorial voter control in elections

DOI10.1016/j.tcs.2015.04.023zbMath1318.91057WikidataQ62039072 ScholiaQ62039072MaRDI QIDQ2346381

Rolf Niedermeier, Piotr Faliszewski, Laurent Bulteau, Jiehua Chen, Nimrod Talmon

Publication date: 1 June 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.04.023

zbMATH Keywords

voting; plurality rule; parameterized complexity; domain restrictions; Condorcet's rule; NP-hard election control problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

91B12: Voting theory

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

The complexity of priced control in elections, Prices matter for the parameterized complexity of shift bribery, Optimal defense against election control by deleting voter groups, Structured proportional representation, Are there any nicely structured preference profiles nearby?, On the Computational Complexity of Variants of Combinatorial Voter Control in Elections

Uses Software

• CP-nets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Experimental algorithms. 11th international symposium, SEA 2012, Bordeaux, France, June 7--9, 2012. Proceedings
• The complexity of manipulative attacks in nearly single-peaked electorates
• The shield that never was: societies with single-peaked preferences are more open to manipulation and control
• Parameterized complexity of control problems in Maximin election
• A simplified NP-complete satisfiability problem
• Anyone but him: the complexity of precluding an alternative
• Parameterized computational complexity of control problems in voting systems
• Parameterized complexity of candidate control in elections and related digraph problems
• How hard is it to control an election?
• Some simplified NP-complete graph problems
• Stable matching with preferences derived from a psychological model
• Control complexity in Bucklin and fallback voting: a theoretical analysis
• Single-crossing, strategic voting and the median choice rule
• A characterization of the single-crossing domain
• Parameterized complexity of Vertex Cover variants
• Parametrized complexity theory.
• Computationally Manageable Combinational Auctions
• Large-Scale Election Campaigns: Combinatorial Shift Bribery
• Studies in Computational Aspects of Voting
• Combinatorial Voter Control in Elections
• Integer Programming with a Fixed Number of Variables
• Multimode Control Attacks on Elections
• Eliciting Single-Peaked Preferences Using Comparison Queries
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• Minkowski's Convex Body Theorem and Integer Programming
• An Exploration in the Theory of Optimum Income Taxation