How hard is it to control an election?
From MaRDI portal
Publication:1200886
DOI10.1016/0895-7177(92)90085-YzbMath0757.90008MaRDI QIDQ1200886
Michael A. Trick, John J. III Bartholdi, Craig A. Tovey
Publication date: 16 January 1993
Published in: Mathematical and Computer Modelling (Search for Journal in Brave)
Related Items (76)
Tennis manipulation: can we help Serena Williams win another tournament? Or can we control a knockout tournament with reasonable complexity? ⋮ Isomorphic Distances Among Elections ⋮ The Complexity of Controlling Condorcet, Fallback, and k-Veto Elections by Replacing Candidates or Voters ⋮ Algorithms for gerrymandering over graphs ⋮ Generalized juntas and NP-hard sets ⋮ The learnability of voting rules ⋮ Condorcet-consistent and approximately strategyproof tournament rules ⋮ The possible winner problem with uncertain weights revisited ⋮ Resolute control: forbidding candidates from winning an election is hard ⋮ Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control ⋮ The complexity of priced control in elections ⋮ Studies in Computational Aspects of Voting ⋮ Control of Condorcet voting: complexity and a relation-algebraic approach ⋮ Solving hard control problems in voting systems via integer programming ⋮ Optimal defense against election control by deleting voter groups ⋮ Vote trading in public elections ⋮ Computational complexity of manipulation: a survey ⋮ Prices matter for the parameterized complexity of shift bribery ⋮ The complexity of probabilistic lobbying ⋮ The control complexity of \(r\)-Approval: from the single-peaked case to the general case ⋮ Controlling weighted voting games by deleting or adding players with or without changing the quota ⋮ Normalized range voting broadly resists control ⋮ Parameterized complexity of control by voter selection in Maximin, Copeland, Borda, Bucklin, and Approval election systems ⋮ Comparing multiagent systems research in combinatorial auctions and voting ⋮ Complexity of control in judgment aggregation for uniform premise-based quota rules ⋮ Constraint-based electoral districting using a new compactness measure: an application to Portugal ⋮ NP-hardness of two edge cover generalizations with applications to control and bribery for approval voting ⋮ Priced gerrymandering ⋮ Group control for consent rules with consecutive qualifications ⋮ Hotelling-Downs equilibria: moving beyond plurality variants ⋮ The possible winner with uncertain weights problem ⋮ The shield that never was: societies with single-peaked preferences are more open to manipulation and control ⋮ On the complexity of bribery and manipulation in tournaments with uncertain information ⋮ Copeland Voting Fully Resists Constructive Control ⋮ Complexity of manipulation and bribery in premise-based judgment aggregation with simple formulas ⋮ The nonmanipulative vote-deficits of voting rules ⋮ Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey ⋮ New candidates welcome! Possible winners with respect to the addition of new candidates ⋮ Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules ⋮ Manipulation can be hard in tractable voting systems even for constant-sized coalitions ⋮ On the Computational Complexity of Variants of Combinatorial Voter Control in Elections ⋮ Parameterized complexity of control problems in Maximin election ⋮ Is computational complexity a barrier to manipulation? ⋮ Duplication monotonicity in the allocation of indivisible goods ⋮ The complexity of manipulative attacks in nearly single-peaked electorates ⋮ Voting Procedures, Complexity of ⋮ On complexity of lobbying in multiple referenda ⋮ Control complexity in Borda elections: solving all open cases of offline control and some cases of online control ⋮ Bribery and Control in Stable Marriage ⋮ The complexity of controlling candidate-sequential elections ⋮ Control complexity in Bucklin and fallback voting: a theoretical analysis ⋮ Control complexity in Bucklin and fallback voting: an experimental analysis ⋮ Computer science and decision theory ⋮ Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control ⋮ Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections ⋮ A parameterized perspective on protecting elections ⋮ Obtaining a proportional allocation by deleting items ⋮ Binary linear programming solutions and non-approximability for control problems in voting systems ⋮ Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting ⋮ Hybrid Elections Broaden Complexity-Theoretic Resistance to Control ⋮ Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control ⋮ Computational Aspects of Approval Voting ⋮ Anyone but him: the complexity of precluding an alternative ⋮ Parameterized computational complexity of control problems in voting systems ⋮ Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers ⋮ Parameterized complexity of voter control in multi-peaked elections ⋮ Parameterized complexity of candidate control in elections and related digraph problems ⋮ Controlling sub-tournaments: easy or hard problem? Theoretical vs. practical analysis ⋮ Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems ⋮ Network-Based Vertex Dissolution ⋮ Complexity of shift bribery for iterative voting rules ⋮ Structural control in weighted voting games ⋮ Parameterized Complexity of Control and Bribery for d-Approval Elections ⋮ Combinatorial voter control in elections ⋮ Exploiting social influence to control elections based on positional scoring rules ⋮ Parameterized complexity of control and bribery for \(d\)-approval elections
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sophisticated voting outcomes and agenda control
- Voting schemes for which it can be difficult to tell who won the election
- Single transferable vote resists strategic voting
- Recognizing majority-rule equilibrium in spatial voting games
- The computational difficulty of manipulating an election
- New directions in cryptography
- Path Independence, Rationality, and Social Choice
- The Theory of Round Robin Tournaments
This page was built for publication: How hard is it to control an election?
