Is computational complexity a barrier to manipulation?

DOI10.1007/s10472-011-9255-9zbMath1230.91044arXiv1007.0776OpenAlexW2127641921MaRDI QIDQ656822

Toby Walsh

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

zbMATH Keywords

computational complexitysocial choicemanipulationstable marriage

Mathematics Subject Classification ID

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?