Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
From MaRDI portal
Publication:2436695
Recommendations
- The shield that never was: societies with single-peaked preferences are more open to manipulation and control
- Anyone but him: the complexity of precluding an alternative
- Control and bribery in voting
- The computational difficulty of manipulating an election
- Manipulation can be hard in tractable voting systems even for constant-sized coalitions
Cites work
- A characterization of the single-peaked domain
- A comparison of polynomial time reducibilities
- A quantitative gibbard-satterthwaite theorem without neutrality
- A Quantitative Version of the Gibbard–Satterthwaite Theorem for Three Alternatives
- A Richer Understanding of the Complexity of Election Systems
- Algorithms and Computation
- Algorithms for the coalitional manipulation problem
- An Actual Application of Collective Choice Theory to the Selection of Trajectories for the Mariner Jupiter/Saturn 1977 Project
- Anyone but him: the complexity of precluding an alternative
- Approximability of Dodgson's rule
- Average Case Complete Problems
- Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates
- Complete sets and closeness to complexity classes
- Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules
- Complexity of strategic behavior in multi-winner elections
- Computational Aspects of Approval Voting
- Constant scoring rules, Condorcet criteria and single-peaked preferences
- Control complexity in Bucklin and fallback voting: a theoretical analysis
- Control complexity in Bucklin and fallback voting: an experimental analysis
- Dichotomy for voting systems
- Eliciting single-peaked preferences using comparison queries
- Exact analysis of Dodgson elections
- Frequency of correctness versus average polynomial time
- Generalized juntas and NP-hard sets
- Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
- How hard is it to control an election?
- How large should a coalition be to manipulate an election?
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1008518 (Why is no real title available?)
- scientific article; zbMATH DE number 1072538 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (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
- Independence of clones as a criterion for voting rules
- Integer Programming with a Fixed Number of Variables
- Junta distributions and the average-case complexity of manipulating elections
- Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
- Manipulation of Voting Schemes: A General Result
- Multimode control attacks on elections
- Multivariate complexity analysis of swap bribery
- Normalized range voting broadly resists control
- Notes on Levin's theory of average-case complexity
- On asymptotic strategy-proofness of classical social choice rules
- On asymptotic strategy-proofness of the plurality and the run-off rules
- On problem kernels for possible winner determination under the k-approval protocol
- Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems
- Parameterized complexity of control problems in Maximin election
- Parameterized computational complexity of control problems in voting systems
- Parameterized Computational Complexity of Dodgson and Young Elections
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Search versus decision for election manipulation problems
- Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
- Single transferable vote resists strategic voting
- Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized
- Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
- Studies in Computational Aspects of Voting
- Swap bribery
- The complexity of manipulative attacks in nearly single-peaked electorates
- The computational difficulty of manipulating an election
- The effect of social homogeneity on coincidence probabilities for pairwise proportional lottery and simple majority rules
- The geometry of manipulation -- a quantitative proof of the Gibbard-Satterthwaite theorem
- The shield that never was: societies with single-peaked preferences are more open to manipulation and control
- Voting schemes for which it can be difficult to tell who won the election
- Voting systems that combine approval and preference
- When are elections with few candidates hard to manipulate?
Cited in
(21)- Optimal defense against election control by deleting voter groups
- The computational difficulty of manipulating an election
- Protecting elections by recounting ballots
- 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
- 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
- Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
- The complexity of manipulative attacks in nearly single-peaked electorates
- The Complexity of Controlling Condorcet, Fallback, and k-Veto Elections by Replacing Candidates or Voters
- Control and bribery in voting
- Toward Computing the Margin of Victory in Single Transferable Vote Elections
- Path-disruption games: bribery and a probabilistic model
- Hardness and algorithms for electoral manipulation under media influence
- The shield that never was: societies with single-peaked preferences are more open to manipulation and control
This page was built for publication: Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2436695)
