Computational complexity of manipulation: a survey

DOI10.1134/S0005117916030012MaRDI QIDQ334204zbMATH OpenOpenAlexFDO

Authors Yuliya Veselova

Publication date 1 November 2016

Published in Automation and Remote Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s0005117916030012

Mathematics Subject Classification ID

Social choice (91B14) Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to game theory, economics, and finance (91-02)

Recommendations

• The computational difficulty of manipulating an election
• Is computational complexity a barrier to manipulation?
• Manipulation can be hard in tractable voting systems even for constant-sized coalitions
• Collective decision making procedures protected from manipulation. (A survey of the problem)
• Where are the hard manipulation problems?

Cites work

• scientific article; zbMATH DE number 5764882 (Why is no real title available?)
• A Richer Understanding of the Complexity of Election Systems
• A characterization of the maximin rule in the context of voting
• Exact results on manipulability of positional voting rules
• How hard is it to control an election?
• Independence of clones as a criterion for voting rules
• Is it ever safe to vote strategically?
• Manipulation of Voting Schemes: A General Result
• Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
• On the degree of manipulability of social choice rules
• Reducibility among combinatorial problems
• Single transferable vote resists strategic voting
• Some further results on the manipulability of social choice rules
• Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
• The complexity of theorem-proving procedures
• The computational difficulty of manipulating an election
• Voting schemes for which it can be difficult to tell who won the election
• When are elections with few candidates hard to manipulate?

Cited in

(7)

• Incentive compatibility and strategy-proofness of mechanisms of organizational behavior control: retrospective, state of the art, and prospects of theoretical research
• Manipulation can be hard in tractable voting systems even for constant-sized coalitions
• Is computational complexity a barrier to manipulation?
• Introduction to computational social choice
• The geometry of manipulation -- a quantitative proof of the Gibbard-Satterthwaite theorem
• Complexity of strategic behavior in multi-winner elections
• Structured preferences: a literature survey

This page was built for publication: Computational complexity of manipulation: a survey

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