Computational complexity of manipulation: a survey

DOI10.1134/S0005117916030012zbMATH Open1348.91109OpenAlexW2326459646MaRDI QIDQ334204FDOQ334204

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

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?

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)

Cites Work

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

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)