A parameterized perspective on protecting elections
From MaRDI portal
Publication:2034407
Abstract: We study the parameterized complexity of the optimal defense and optimal attack problems in voting. In both the problems, the input is a set of voter groups (every voter group is a set of votes) and two integers and corresponding to respectively the number of voter groups the attacker can attack and the number of voter groups the defender can defend. A voter group gets removed from the election if it is attacked but not defended. In the optimal defense problem, we want to know if it is possible for the defender to commit to a strategy of defending at most voter groups such that, no matter which voter groups the attacker attacks, the outcome of the election does not change. In the optimal attack problem, we want to know if it is possible for the attacker to commit to a strategy of attacking voter groups such that, no matter which voter groups the defender defends, the outcome of the election is always different from the original (without any attack) one.
Recommendations
Cites work
- Combinatorial \(n\)-fold integer programming and applications
- Combinatorial voter control in elections
- Complexity of control by partitioning veto and maximin elections and of control by adding candidates to plurality elections
- Complexity of manipulation with partial information in voting
- Complexity of manipulative actions when voting with ties
- Control complexity in Bucklin and fallback voting: an experimental analysis
- Copeland Voting Fully Resists Constructive Control
- Determining possible and necessary winners given partial orders
- Elections with few voters: candidate control can be easy
- Frugal bribery in voting
- Handbook of Computational Social Choice
- How hard is it to control an election?
- scientific article; zbMATH DE number 6747953 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
- Introduction to algorithms.
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Kernelization complexity of possible winner and coalitional manipulation problems in voting
- Kernelization. Theory of parameterized preprocessing
- Learning and approximating the optimal strategy to commit to
- Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
- Local distance constrained bribery in voting
- Manipulative elicitation -- a new attack on elections with incomplete preferences
- More natural models of electoral control by partition
- Multimode control attacks on elections
- New Approximations for Coalitional Manipulation in Scoring Rules
- Normalized range voting broadly resists control
- On the computational complexity of variants of combinatorial voter control in elections
- On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard
- Online voter control in sequential elections
- Parameterized algorithms
- Parameterized complexity of candidate control in elections and related digraph problems
- Parameterized complexity of control and bribery for \(d\)-approval elections
- Parameterized complexity of control by voter selection in Maximin, Copeland, Borda, Bucklin, and Approval election systems
- Parameterized complexity of control problems in Maximin election
- Parameterized computational complexity of control problems in voting systems
- Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
- Parametrized complexity theory.
- Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control
- Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
- The complexity of priced control in elections
- The shield that never was: societies with single-peaked preferences are more open to manipulation and control
- Weighted electoral control
- Where are the hard manipulation problems?
Cited in
(5)
This page was built for publication: A parameterized perspective on protecting elections
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2034407)
