Вычислительная сложность манипулирования в задаче голосования
When a society needs to take a collective decision one could apply some aggregation method, particularly, voting. One of the main problems with voting is manipulation. We say a voting rule is vulnerable to manipulation if there exists at least one voter who can achieve a better voting result by misrepresenting his or her preferences. The popular approach to comparing manipulability of voting rules is defining complexity class of the corresponding manipulation problem. This paper provides a survey into manipulation complexity literature considering variety of problems with different assumptions and restrictions.