Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
From MaRDI portal
Publication:2436695
DOI10.1007/s10472-013-9359-5zbMath1286.68207MaRDI QIDQ2436695
Publication date: 25 February 2014
Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10472-013-9359-5
68T99: Artificial intelligence
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
91B14: Social choice
Related Items
The Complexity of Controlling Condorcet, Fallback, and k-Veto Elections by Replacing Candidates or Voters, Toward Computing the Margin of Victory in Single Transferable Vote Elections, Manipulation complexity of same-system runoff elections, Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control, On the hardness of bribery variants in voting with CP-nets, Control of Condorcet voting: complexity and a relation-algebraic approach, The complexity of manipulative attacks in nearly single-peaked electorates, Path-disruption games: bribery and a probabilistic model, Optimal defense against election control by deleting voter groups, Complexity of shift bribery for iterative voting rules, 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 Borda elections: solving all open cases of offline control and some cases of online control, Control complexity in Bucklin and fallback voting: an experimental analysis, On the Computational Complexity of Variants of Combinatorial Voter Control in Elections
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Normalized range voting broadly resists control
- The geometry of manipulation -- a quantitative proof of the Gibbard-Satterthwaite theorem
- Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules
- The complexity of manipulative attacks in nearly single-peaked electorates
- Independence of clones as a criterion for voting rules
- A characterization of the single-peaked domain
- 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
- Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
- Algorithms for the coalitional manipulation problem
- Generalized juntas and NP-hard sets
- Dichotomy for voting systems
- Frequency of correctness versus average polynomial time
- Approximability of Dodgson's rule
- Anyone but him: the complexity of precluding an alternative
- Parameterized computational complexity of control problems in voting systems
- Voting schemes for which it can be difficult to tell who won the election
- Single transferable vote resists strategic voting
- The effect of social homogeneity on coincidence probabilities for pairwise proportional lottery and simple majority rules
- How hard is it to control an election?
- Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
- A comparison of polynomial time reducibilities
- Constant scoring rules, Condorcet criteria and single-peaked preferences
- The computational difficulty of manipulating an election
- On asymptotic strategy-proofness of classical social choice rules
- How large should a coalition be to manipulate an election?
- Control complexity in Bucklin and fallback voting: a theoretical analysis
- Control complexity in Bucklin and fallback voting: an experimental analysis
- Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized
- On asymptotic strategy-proofness of the plurality and the run-off rules
- Computational Aspects of Approval Voting
- Studies in Computational Aspects of Voting
- Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates
- Search versus Decision for Election Manipulation Problems
- Integer Programming with a Fixed Number of Variables
- Multivariate Complexity Analysis of Swap Bribery
- Multimode Control Attacks on Elections
- Notes on Levin’s Theory of Average-Case Complexity
- A Quantitative Version of the Gibbard–Satterthwaite Theorem for Three Alternatives
- Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
- Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
- Parameterized Computational Complexity of Dodgson and Young Elections
- When are elections with few candidates hard to manipulate?
- On Problem Kernels for Possible Winner Determination under the k-Approval Protocol
- Swap Bribery
- Eliciting Single-Peaked Preferences Using Comparison Queries
- Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
- Average Case Complete Problems
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Manipulation of Voting Schemes: A General Result
- An Actual Application of Collective Choice Theory to the Selection of Trajectories for the Mariner Jupiter/Saturn 1977 Project
- Exact analysis of Dodgson elections
- Complete sets and closeness to complexity classes
- A Richer Understanding of the Complexity of Election Systems
- A quantitative gibbard-satterthwaite theorem without neutrality
- Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems
- Algorithms and Computation
