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

В ситуациях, когда коллективу требуется принять решение на основе множества индивидуальных предпочтений, применяется тот или иной метод агрегирования, в частности голосование. Одной из главных проблем для любого недиктаторского правила коллективного выбора является возможность у избирателей добиться более выгодного для себя исхода голосования при помощи искажения своих предпочтений. Такие действия со стороны избирателей называются манипулированием или стратегическим голосованием. Один из подходов, используемых для сравнения правил по степени манипулируемости, – выявление класса сложности задачи манипулирования при том или ином методе агрегирования. Представлен обзор по исследованию классов сложности задач манипулирования при различных предположениях и ограничениях модели.