Диссертация (1137313), страница 7
Текст из файла (страница 7)
Для измерения расстояниямежду предпочтениями автором предлагается использовать функцию из [41],равную мощности симметрической разности бинарных отношений, представляющих предпочтения. Было введено понятие правила коллективного выбора,локально защищенного от манипулирования – если для каждого манипулирования, возможного при данном правиле, избирателю требуется изменить своепредпочтение, которое находится на расстоянии больше, чем 1, от его искреннего предпочтения.39Вопрос манипулируемости был исследован посредством численных экспериментов в [42], где была вычислена частота появления циклов и возможностиманипулирования для трех правил коллективного выбора: правила относительного большинства, правила Борда, и функции Кемени [41].Подробное изучение поведения индексов манипулируемости для различныхправил голосования было начато Келли в [43]. В этой работе впервые процедуры выбора сравниваются друг с другом по вероятности манипулирования в них.Продолжением этой линии исследований является [3], в которой индекс манипулируемости Келли был вычислен посредством численных экспериментов.
Вэтой же работе для устранения несравнимости альтернатив в выборе был применен алфавитный порядок. Такой метод является одним из самых удобных,однако, в этом случае для коллективного выбора нарушается свойство нейтральности – равноправности всех альтернатив в голосовании. В дополнение киндексу Келли, в работе были предложены новые индексы манипулируемости.Расширенная версия индекса – отношение числа профилей, в которых ровно избирателей имеют возможность манипулировать, к общему количеству профилей предпочтений. А также представлен индекс свободы манипулирования. Внем для каждого профиля вычисляется среднее количество стратегий успешного манипулирования для избирателей в профиле, а затем берется среднее такихзначений по всем профилям.Манипулируемость правил голосования коалициями избирателей была исследована в [6, 44].
Авторами была рассмотрена как модель IC, так и модельIAC для случая трех альтернатив. Очевидно, что доля профилей предпочтений, подверженных манипулированию со стороны коалиции, намного больше,чем при индивидуальном манипулировании, и возрастает в зависимости от количества избирателей в коалиции. Так, в [6] показано, что при 12 избирателях40и трех кандидатах правило Борда подвержено манипулированию коалицией из3 участников больше, чем в половине случаев.
В [44] рассматривается вероятность того, что среди избирателей найдется какая-либо коалиция, котораясможет исказить свои предпочтения так, чтобы итог голосования для всех членов коалиции был более выгоден. Оказалось, что для правила передачи голосовэта вероятность составляет примерно 16 % для 171 избирателя и трех альтернатив, тогда так для правила относительного большинства и правила Борда95,8 % и 99,8 % соответственно.В [45] вопрос манипулируемости был рассмотрен с точки зрении существования возможности ответного манипулирования.
Расчет индексов был произведендля трех альтернатив и числа избирателей до 40 в модели IAC. Правило Борда,наиболее манипулируемое среди рассматриваемых ими правил коллективноговыбора, оказалось наименее манипулируемым в случае, если принимаются вовнимание ответные манипулирования.Следующие публикации, [5,46] расширяют исследование манипулируемости внескольких направлениях. В них рассмотрено манипулирование со стороны одного избирателя, имеющее целью улучшить результат голосования, использованы различные показатели степени манипулируемости в случае множественноговыбора для соответственно пяти и десяти правил в условиях модели IC, числоальтернатив увеличено до 5, а количество избирателей до 100. Этот же вопросрассматривается в [47], где используется модель IAC, а количество избирателейувеличено до 10000 при трех альтернативах.Так как результат правила выбора может быть представлен несколькимикандидатами, набравшими одинаковое количество очков, то необходимо либоввести правило перехода от множественного выбора к одиночному (например,алфавитное правило, как в [3], либо расширить предпочтения избирателя на41множество всех непустых подмножеств кандидатов [4, 5, 46].
Во втором случаедоля манипулируемых профилей для правила относительного большинства стремя кандидатами достигает 46 % для 7 избирателей и постепенно снижаетсядо 20 % для 96 избирателей. Устранение множественности выбора предоставляет избирателям меньше возможностей для манипулирования, поэтому показатели манипулируемости приблизительно на треть меньше в этом случае.
Срединаименее манипулируемых правил в исследованиях [5, 46, 47] были выделеныправило передачи голосов, правило Нансона и правило Болдуина, наиболее манипулируемое – правило относительного большинства.1.4Вычислительная сложность манипулированияВ [12] вопрос о степени манипулируемости был поставлен иначе. Пусть многиеправила допускают возможность стратегического поведения, но тогда что представляет собой задача поиска нужной стратегии для манипулирующего избирателя? Насколько трудоемка эта задача? Предположим, что два правила A и Bманипулируемы в одинаковом числе случаев. Однако чтобы выбрать стратегиюдля манипулирования в процедуре A, нужно просто составить предпочтения поопределенному правилу.
В то же время для процедуры B нужно осуществить перебор всех возможных вариантов расстановки кандидатов в бюллетене, потомучто неизвестно, как тот или иной вариант повлияет на результат голосования.В этой ситуации нельзя считать эти две процедуры в равной степени манипулируемыми, и был рассмотрен следующий вопрос: является ли манипулированиерезультатом правила В более сложным, чем манипулирование результатом правила А, т.е. сравнивался класс сложности задач манипулирования результатомправил А и В.42Правила голосования, для манипулирования в которых существует полиномиальный алгоритм поиска стратегии, стали считать легко манипулируемыми.А те правила, где поиск манипулирующей стратегии принадлежит классу NPполных задач – трудно манипулируемыми.
Дальнейшее развитие этого направления заключалось в определении класса сложности для правил голосованияпри различной постановке задачи манипулирования: индивидуальное или коалиционное манипулирование, конструктивное или деструктивное и т.д. Оказалось, что эти условия существенно влияют на оценку сложности. Поэтому частодобавление того или иного условия требует решения отдельной задачи.Рассмотрим различные постановки задачи манипулирования и перечислимосновные результаты по вычислительной сложности соотвествующих задач дляразличных правил.1.4.1Конструктивное манипулирование без весовВпервые вопрос о вычислительной сложности задачи манипулирования результатом голосования был поставлен в [12]. В ней исследуется самая простаяформулировка задачи голосования: манипулирование индивидуальное, конструктивное, с одинаковым весом избирателей и с предположением о наличииполной информации обо всех предпочтениях остальных избирателей.
Дадимформальное определение соответствующей вычислительной задачи.Задача индивидуального манипулирования при правиле (ИМ-F).⃗− , и кандиДаны предпочтения всех избирателей, кроме манипулирующего, дат . Требуется найти такое предпочтение для избирателя , при котором{} = ( , ⃗− ), или доказать, что такого предпочтения нет.Для теории вычислительной сложности необычно то, что высокая сложностьявляется положительным свойством. Однако желательно, чтобы результат пра-43вила голосования вычислялся легко, т.е.
за полиномиальное время, а манипулирование было бы сложным. Правила, для которых само определение победителя является сложной задачей, заведомо трудно манипулируемы. Такие правилабыли найдены в [48]: это правило Доджсона и правило Кемени. Оказалось, чтозадача определения победителя по этим правилам является NP-трудной, поэтому они неудобны для практического использования. С точки зрения практического применения наиболее важными являются результаты, когда манипулирование представляет собой вычислительно сложную задачу, но результатправила вычислим за полиномиальное время.В [12] показано, что для некоторых правил коллективного выбора (правило простого большинства, правило Борда, максиминная процедура и правилоКоупленда) задача ИМ может быть решена с помощью простого жадного алгоритма, имеющего полиномиальную сложность.
Отметим, что среди легко манипулируемых правил особое положение занимает правило относительного большинства. При любой постановке задачи манипулирования, где единственнойцелью является победа любимого кандидата, стратегия строится одинаково: напервое место ставится кандидат , а остальные кандидаты могут располагатьсяпроизвольным образом, т.е. в этом случае можно говорить об отсутствии стимулов к стратегическому поведению. Тогда для решения любой задачи конструктивного манипулирования для правила относительного большинства необходимо лишь посчитать результат выборов, когда все манипулирующие избирателиголосуют за , и сложность такой задачи – это сложность самой процедуры,().В то же время, даже при такой простой постановке задачи правило передачиголосов и правило Коупленда второго порядка трудно манипулируемы (задачаИМ для них является NP-полной).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
