• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Глава

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

С. 79-88.

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