Multimode control attacks on elections
From MaRDI portal
Abstract: In 1992, Bartholdi, Tovey, and Trick opened the study of control attacks on elections---attempts to improve the election outcome by such actions as adding/deleting candidates or voters. That work has led to many results on how algorithms can be used to find attacks on elections and how complexity-theoretic hardness results can be used as shields against attacks. However, all the work in this line has assumed that the attacker employs just a single type of attack. In this paper, we model and study the case in which the attacker launches a multipronged (i.e., multimode) attack. We do so to more realistically capture the richness of real-life settings. For example, an attacker might simultaneously try to suppress some voters, attract new voters into the election, and introduce a spoiler candidate. Our model provides a unified framework for such varied attacks, and by constructing polynomial-time multiprong attack algorithms we prove that for various election systems even such concerted, flexible attacks can be perfectly planned in deterministic polynomial time.
Recommendations
Cited in
(33)- Optimal defense against election control by deleting voter groups
- A geometric model of sensitivity of multistage elections to change
- On the complexity of bribery with distance restrictions
- Multivariate complexity analysis of Swap Bribery
- On the approximability of Dodgson and Young elections
- A parameterized perspective on protecting elections
- Resolute control: forbidding candidates from winning an election is hard
- Complexity of control in judgment aggregation for uniform premise-based quota rules
- Control complexity in Bucklin and fallback voting: a theoretical analysis
- Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting
- Parameterized complexity of voter control in multi-peaked elections
- Combinatorial voter control in elections
- Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
- Studies in Computational Aspects of Voting
- On the computational complexity of variants of combinatorial voter control in elections
- Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control
- The complexity of priced control in elections
- Solving hard control problems in voting systems via integer programming
- Prices matter for the parameterized complexity of shift bribery
- More natural models of electoral control by partition
- Parameterized complexity of control by voter selection in Maximin, Copeland, Borda, Bucklin, and Approval election systems
- New candidates welcome! Possible winners with respect to the addition of new candidates
- The complexity of manipulative attacks in nearly single-peaked electorates
- Proportional approval voting, harmonic \(k\)-median, and negative association
- The Complexity of Controlling Condorcet, Fallback, and k-Veto Elections by Replacing Candidates or Voters
- Socially desirable approximations for dodgson’s voting rule
- Hardness and algorithms for electoral manipulation under media influence
- The possible winner with uncertain weights problem
- Parameterized complexity of control problems in Maximin election
- Is computational complexity a barrier to manipulation?
- On the complexity of winner determination and strategic control in conditional approval voting
- Strategic candidacy equilibria for common voting rules
- Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections
This page was built for publication: Multimode control attacks on elections
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3081454)
