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

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

Веселова Ю. А.

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

Ключевые слова: коллективный выбор, social choice, вычислительная сложность, манипулирование, manipulation, Computational Complexity

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА: Разработка и исследование новых математических моделей в социально-экономической и политической сферах (2016)