Is computational complexity a barrier to manipulation?
From MaRDI portal
Publication:656822
DOI10.1007/s10472-011-9255-9zbMath1230.91044arXiv1007.0776OpenAlexW2127641921MaRDI QIDQ656822
Publication date: 13 January 2012
Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1007.0776
Voting theory (91B12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Social choice (91B14)
Related Items (3)
Tennis manipulation: can we help Serena Williams win another tournament? Or can we control a knockout tournament with reasonable complexity? ⋮ The Complexity of Controlling Condorcet, Fallback, and k-Veto Elections by Replacing Candidates or Voters ⋮ Solving hard control problems in voting systems via integer programming
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules
- The shield that never was: societies with single-peaked preferences are more open to manipulation and control
- Incompleteness and incomparability in preference aggregation: complexity results
- Parameterized complexity of candidate control in elections and related digraph problems
- Single transferable vote resists strategic voting
- 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
- Easy problems are sometimes hard
- The TSP phase transition
- The computational difficulty of manipulating an election
- Multimode Control Attacks on Elections
- Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
- When are elections with few candidates hard to manipulate?
- Manipulating Tournaments in Cup and Round Robin Competitions
- Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
- How Hard Is Bribery in Elections?
- The Economics of Matching: Stability and Incentives
- Manipulation of Voting Schemes: A General Result
- Algorithms and Computation
- Random constraint satisfaction: Flaws and structure
- A physicist's approach to number partitioning
This page was built for publication: Is computational complexity a barrier to manipulation?
