Диссертация (1137313), страница 8
Текст из файла (страница 8)
В Приложении А приведено описание пра44вила передачи голосов, которое является одим из множества его модификаций.Однако данный результат справедлив для любого варианта, так как NP-полнотаманипулирования доказывается авторами для определения единственного победителя по правилу передачи голосов, что является частью любой процедурыэтого класса. В [49] была доказана NP-полнота манипулирования результатомправил Болдуина и Нансона.Расширим модель на случай коалиционного манипулирования и рассмотримслучай без назначения весов, т.е. вес голоса одинаков для всех избирателей.Для простоты под словосочетанием «коалиционное манипулирование» будемпонимать именно случай с одинаковыми весами.
Введем определение соответствующей вычислительной задачи.Задача коалиционного манипулирования при правиле (КМ-F). Да⃗− , ины предпочтения всех избирателей, кроме манипулирующей коалиции, ⃗ для манипуликандидат . Требуется найти такой профиль предпочтений ⃗ , ⃗− ), или доказать, что такогорующей коалиции , при котором {} = (профиля нет.Все результаты о NP-полноте ИМ-F находят здесь применение, так как если индивидуальное манипулирование является NP-полным, то при переходе ккоалиционной модели NP-полнота сохраняется (иными словами, ИМ-F можетбыть сведена к КМ-F).С другой стороны, простота вычислений для коалиционного манипулирования в еще более сложной модели, где избиратели имеют неодинаковый вес вголосовании, означает, что в модели без весов правило будет также легко манипулируемым (полиномиальность коалиционного манипулирования при взвешенном голосовании влечет полиномиальность КМ-F).45Результаты по сложности индивидуального и коалиционного манипулирования при отсутствии весов обобщены в таблице 1.1.Таблица 1.1.
Конструктивное манипулирование в голосовании с одинаковымвесом голосовПравило относительного большинстваТурнир с выбываниемПравило БордаПравило ветоПравило передачи голосовДвухступенчатая мажоритарная системаПравило КоуплендаПравило Коупленда второго порядкаПравило НансонаПравило БолдуинаПравило БаклинаПроцедура упорядоченных парМаксиминная процедура1.4.2ИМ-FP [12]P [50]P [12]P [12]NP-п [53]P [52]P [12]NP-п [12]NP-п [49]NP-п [49]P [55]NP-п [55]P [12]КМ-FP [50]P [50]NP-т [51]P [52]NP-п [53]P [52]P [54]NP-п [12]NP-п [49]NP-п [49]P [55]NP-п [55]NP-п [55]Голосование с назначением весов и ограничением на множество кандидатовТеперь в добавление к коалиционной манипулируемости введем возможностьназначения весов голосам избирателей.
Пусть = (1 , ..., ) – вектор, -й элемент которого означает вес голоса избирателя , который обычно предполагаютрациональным числом, т.е. = ˜ /˜, где ˜ – общий знаменатель 1 , ..., . Таким образом, избиратель с весом голоса может представлять коалицию из˜ невидимых избирателей, имеющих одинаковые предпочтения , а ˜ – общееколичество невидимых избирателей. Такая интерпретация удобна тем, что позволяет для анонимных правил коллективного выбора определить результат напрофиле предпочтений, где заведомо отсутствует анонимность (равноправность46⃗ и весах , т.е.
взвешенный произбирателей). Информацию о предпочтениях ⃗ , можно записать в виде обыкновенного профиляфиль предпочтений ⃗ = (˜1 1 , ..., ˜ ) = (1 , ..., 1 , ..., , ..., ).⏟⏞⏟ ⏞˜1˜Конечно, усложняя задачу добавлением весов, мы будем иметь сохранениерезультатов о NP-полноте вследствие того, что задача КМ-F сводима к задачеКМВ-F. Более того, оказывается, что для подавляющего большинства рассматриваемых правил в такой формулировке манипулирование будет NP-полным.Поэтому вводится дополнительное предположение, на этот раз упрощающее манипулирование. Так как сложность манипулирования обычно возрастает экспоненциально в зависимости от числа кандидатов, то логично было бы ограничитьчисло кандидатов некоторой константой.
Если начинать с минимального числакандидатов, то при = 2 манипулирование, вообще говоря, не имеет смысла,и построение предпочтений для манипулирующих избирателей заключается всообщении своих истинных предпочтений относительно кандидатов. Затем, постепенно увеличивая заданное ограничение, можно «нащупать» тот порог, прикотором задача становится «сложной», т.е. решаемой в худшем случае толькопри помощи полного перебора.В списке легко манипулируемых правил в задаче КМВ-F без ограничения начисло альтернатив находится правило относительного большинства и турнирс выбыванием.
Очевидно, что для правила относительного большинства существует только одна стратегия коалиционного манипулирования независимо отчисла кандидатов – проголосовать за своего любимого кандидата. Для турнирас выбыванием алгоритм построения предпочтений коалиции более сложный, нополиномиальный по числу избирателей и кандидатов.47В [50] доказано, что для любого правила подсчета очков кроме правила относительного большинства КМВ-F в голосовании с тремя кандидатами являетсяNP-полной задачей. К таким правилам относятся правило Борда и правилоодобряющего голосования с квотой.
Частный случай правила одобряющего голосования с квотой – обратное правило относительного большинства, или правило вето, где = −1. Интересно, что несмотря на простоту индивидуальногоманипулирования и простоту самих правил подсчета очков задача коалиционного манипулирования с неодинаковыми весами является сложной.Остальные результаты по сложности манипулирования в задаче КМВ-Fпредставлены в таблице 1.2.Таблица 1.2. Манипулирование при взвешенном голосованииКоличество кандидатовПравило относительного большинстваТурнир с выбываниемПравило Борда3P [50]P [50]NPп [50]Правило ветоNPп [50]Правило передачи голо- NPсовп [50]Двухступенчатая ма- NPжоритарная системап [50]Правило КоуплендаP [50]Правило НансонаПравило БолдуинаP [49]NPп [56]Максиминная процеду- P [50]раКМВ-F4≥7P [50] P [50]ДКМВ-F34≥7P [50] P [50] P [50]P [50]NPп [50]NPп [50]NPп [50]NPп [50]NPп [50]NPп [49]NPп [56]NPп [50]P [50]P [50]P [50]P [50]P [50]P [50]P [50]P [50]P [50]NPп [50]NPп [50]P [50]NPп [50]NPп [50]P [50]NPп [50]NPп [50]P [50]P [49]NPп [49]NPп [49]P [50]NPп [49]NPп [49]P [50]48P [50]NPп [50]NPп [50]NPп [50]NPп [50]NPп [50]NPп [49]NPп [56]NPп [50]NPп [49]P [50]1.4.3Деструктивное манипулированиеДругой тип манипулирования результатом голосования – деструктивный –имеет целью не победу любимого кандидата, а поражение нелюбимого.
Сформулируем задачу.Задача деструктивного коалиционного манипулирования при взвешенном голосовании при правиле (ДКМВ-F). Даны предпочтения всех⃗− , вектор весов всех избираизбирателей, кроме манипулирующей коалиции, телей = ( , − ) и кандидат . Требуется найти такой профиль предпочте⃗ для манипулирующей коалиции , при котором ∈ний / (⃗ , ⃗−− ), илидоказать, что такого профиля нет. Для правила со случайным исходом дополнительно заданы число 0 ≤ ≤ 1 и распределение вероятностей на множествевозможных реализаций правила .
Требуется найти такой профиль предпочте-⃗ , при котором вероятность выигрыша кандидата меньше, чем , илиний доказать, что такого профиля нет.Деструктивное манипулирование интересно как с точки зрения практики, таки теоретически. Если манипулирующим избирателям не представляется возможность добиться выбора желаемого ими кандидата, то вполне можно ожидать, что они захотят, по крайней мере, не допустить победы какого-то определенного кандидата, может быть, наименее предпочтительного. Кроме того,деструктивное манипулирование всегда не сложнее конструктивного, а значит,правила голосования в большей степени подвержены стратегическому поведению такого типа со стороны избирателей.
Действительно, чтобы решить задачудеструктивного манипулирования, достаточно решить задачу конструктивногоманипулирования для каждого из кандидатов кроме , т.е. задача ДКМВ-Fсводима к задаче КМВ-F.491.4.4Манипулирование с неполной информациейВо всех рассмотренных постановках задачи манипулирования предполагалось наличие полной информации у всех избирателей о предпочтениях остальных. Несомненно, это предположение является довольно сильным, и наличиенеполной информации должно усложнить задачу манипулирования. В исследованиях, посвященных данной теме, под неполной информацией подразумевается следующее. Коалиции избирателей теперь известен не конкретный про-⃗− , а некоторое распределение вероятностей на () − , множестве всехфиль возможных профилей предпочтений остальных избирателей, и задание такогораспределения очень трудоемко. Однако даже при простых распределениях вероятностей на множестве предпочтений для каждого кандидата задача манипулирования при неполной информации по крайней мере так же трудна, как изадача КМВ [50].1.5Заключение по Главе 1В данной главе представлен обзор литературы, посвященной анализу степени манипулируемости правил.
Первой задачей исследований было выявитьусловия, при которых правила подвержены манипулированию, и, возможно,найти неманипулируемые процедуры. Однако результаты, описанные в разделе1.2.2, говорят о том, что защищенность от манипулирования часто несовместима с другими разумными свойствами процедур, которые делают ее в некоторомсмысле «честной».Поэтому возможность манипулирования имеет смысл не исключить, а затруднить или ограничить.
Во-первых, барьером для манипулирования можетслужить высокая вычислительная сложность поиска стратегии. В то же времяжелательно, чтобы вычисление победителя не было сложным. В данном об50зоре были рассмотрены именно такие правила, для которых манипулированиеявляется сложной задачей, а вычисление победителя просто.Оказалось, что при любой постановке задачи достаточно сложными для манипулирования являются правило передачи голосов и правила Болдуина и Нансона. Как было отмечено в разделе 1, эти же правила характеризуются такженаименьшей вероятностью манипулирования, а значит, можно считать их наиболее защищенными от манипулирования со стороны избирателей. С другойстороны, есть правила, для которых манипулирование просто независимо отпостановки задачи.
Это правило относительного большинства и турнир с выбыванием. Первое из них в то же время является одним из самых уязвимыхс точки зрения вероятности манипулирования. Наконец, интересным являетсяпример правила Борда и максиминной процедуры. Эти правила не являются многошаговыми и просты для вычисления победителя, для решения задачииндивидуального манипулирования примени́м простой жадный алгоритм, нокоалиционное манипулирование для этих правил является трудным.Во-вторых, для разных правил манипулирование возможно в разном количестве возможных ситуаций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
