Is computational complexity a barrier to manipulation?

DOI10.1007/S10472-011-9255-9zbMATH Open1230.91044arXiv1007.0776OpenAlexW2127641921MaRDI QIDQ656822FDOQ656822

Authors: Toby Walsh 

Publication date: 13 January 2012

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Abstract: When agents are acting together, they may need a simple mechanism to decide on joint actions. One possibility is to have the agents express their preferences in the form of a ballot and use a voting rule to decide the winning action(s). Unfortunately, agents may try to manipulate such an election by misreporting their preferences. Fortunately, it has been shown that it is NP-hard to compute how to manipulate a number of different voting rules. However, NP-hardness only bounds the worst-case complexity. Recent theoretical results suggest that manipulation may often be easy in practice. To address this issue, I suggest studying empirically if computational complexity is in practice a barrier to manipulation. The basic tool used in my investigations is the identification of computational "phase transitions". Such an approach has been fruitful in identifying hard instances of propositional satisfiability and other NP-hard problems. I show that phase transition behaviour gives insight into the hardness of manipulating voting rules, increasing concern that computational complexity is indeed any sort of barrier. Finally, I look at the problem of computing manipulation of other, related problems like stable marriage and tournament problems.

Full work available at URL: https://arxiv.org/abs/1007.0776

Recommendations

• Computational tractability -- beyond Turing?
• Computational complexity of manipulation: a survey
• Where are the hard manipulation problems?
• Computational versus causal complexity
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• The computational difficulty of manipulating an election
• scientific article; zbMATH DE number 1042857

zbMATH Keywords

computational complexitymanipulationsocial choicestable marriage

Mathematics Subject Classification ID

Social choice (91B14) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Voting theory (91B12)

Cites Work

• Title not available (Why is that?)
• The Economics of Matching: Stability and Incentives
• Title not available (Why is that?)
• Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
• Manipulation of Voting Schemes: A General Result
• When are elections with few candidates hard to manipulate?
• Easy problems are sometimes hard
• The TSP phase transition
• Single transferable vote resists strategic voting
• How hard is it to control an election?
• The computational difficulty of manipulating an election
• Multimode control attacks on elections
• Where are the hard manipulation problems?
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• How hard is bribery in elections?
• Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules
• Algorithms and Computation
• 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
• Random constraint satisfaction: Flaws and structure
• Title not available (Why is that?)
• Junta distributions and the average-case complexity of manipulating elections
• Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
• Parameterized complexity of candidate control in elections and related digraph problems
• Manipulating Tournaments in Cup and Round Robin Competitions
• A physicist's approach to number partitioning

Cited In (13)

• Tennis manipulation: can we help Serena Williams win another tournament? Or can we control a knockout tournament with reasonable complexity?
• Complexity of manipulation with partial information in voting
• 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
• Solving hard control problems in voting systems via integer programming
• Computational complexity of manipulation: a survey
• Complexity of strategic behavior in multi-winner elections
• Where are the hard manipulation problems?
• Search versus decision for election manipulation problems
• Barriers to manipulation in voting
• The Complexity of Controlling Condorcet, Fallback, and k-Veto Elections by Replacing Candidates or Voters
• Junta distributions and the average-case complexity of manipulating elections
• When are elections with few candidates hard to manipulate?

This page was built for publication: Is computational complexity a barrier to manipulation?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q656822)