• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Вычислительная сложность манипулирования: обзор проблемы

Автоматика и телемеханика. 2016. Т. 77. № 3. С. 7-32.

When a society needs to make a collective decision one could apply some aggregation method, particularly, voting. One of the main problems with voting is the manipulability of voting rules. We say a social choice rule is vulnerable to manipulation if there exists at least one voter who can achieve a better voting result by misrepresenting her preferences. The popular approach to comparing manipulability of social choice rules is defining a complexity class of the corresponding manipulation problem. This paper provides a survey into manipulation complexity literature considering variety of problems with different assumptions and constraints.