Is computational complexity a barrier to manipulation?
From MaRDI portal
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.
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
Cites work
- scientific article; zbMATH DE number 5764882 (Why is no real title available?)
- scientific article; zbMATH DE number 44383 (Why is no real title available?)
- scientific article; zbMATH DE number 1341905 (Why is no real title available?)
- A physicist's approach to number partitioning
- Algorithms and Computation
- Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules
- Easy problems are sometimes hard
- How hard is bribery in elections?
- How hard is it to control an election?
- Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
- Incompleteness and incomparability in preference aggregation: complexity results
- Junta distributions and the average-case complexity of manipulating elections
- Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
- Manipulating Tournaments in Cup and Round Robin Competitions
- Manipulation of Voting Schemes: A General Result
- Multimode control attacks on elections
- Parameterized complexity of candidate control in elections and related digraph problems
- Random constraint satisfaction: Flaws and structure
- Single transferable vote resists strategic voting
- Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
- The Economics of Matching: Stability and Incentives
- The TSP phase transition
- The computational difficulty of manipulating an election
- The shield that never was: societies with single-peaked preferences are more open to manipulation and control
- When are elections with few candidates hard to manipulate?
- Where are the hard manipulation problems?
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
- Junta distributions and the average-case complexity of manipulating elections
- The Complexity of Controlling Condorcet, Fallback, and k-Veto Elections by Replacing Candidates or Voters
- Where are the hard manipulation problems?
- Barriers to manipulation in voting
- Solving hard control problems in voting systems via integer programming
- Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules
- When are elections with few candidates hard to manipulate?
- Computational complexity of manipulation: a survey
- Complexity of strategic behavior in multi-winner elections
- Manipulation can be hard in tractable voting systems even for constant-sized coalitions
- Search versus decision for election manipulation problems
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)
