Computational complexity of manipulation: A survey

Аннотация

In situations when a group of people has to make a decision based on the set of individual preferences, they use a certain aggregation method, in particular, voting. One of the main problems for any non-dictatorial social choice rule is the possibility for the voters to achieve a more preferable outcome of the voting by misrepresenting their preferences. Such actions on behalf of the voters are called manipulation, or strategic voting. One approach used to compare social choice rules in terms of how hard they are to manipulate is to find the complexity classes of manipulation problems for a given aggregation method. In this work, we present a survey of the studies of complexity classes of manipulation problems under various model assumptions and constraints.