Диссертация (1137313), страница 12
Текст из файла (страница 12)
Однако избиратель ничего не можетсделать, чтобы поменять мажоритарное отношение на .Следовательно, при нечетном числе избирателей, трех альтернативах и методе расширения предпочтений Leximax правило Коупленда не подверженоманипулированию, если известна информация только о победителях голосования.2.4.2Вычислительные экспериментыВ данном разделе представлены результаты вычисления индекса 1 в MatLabс использованием программного комплекса, описанного в разделе 2.6. Рассматривались оба метода расширения предпочтений, Leximin и Leximax, а такжеслучай с применением алфавитного правила устранения множественности выбора, число альтернатив – 3, число избирателей – от 3 до 15. Несмотря на то,что число избирателей невелико, оно оказалоь достаточным для того, чтобывыявить основные закономерности в поведении индекса.
Так как все рассматриваемые правила обладают свойством анонимности, мы не вычисляем индексдля ФПИ-Ballot. Кроме того, так как правила подсчета очков сильно вычислимы из ФПИ-Profile, ФПИ-Ballot, ФПИ-Positions и ФПИ-Score, то по Теореме 1значения индекса 1 будут для этих ФПИ одинаковыми. Аналогичное объяснение применимо и в случае правила Коупленда и ФПИ-WMG.Чтобы проверить, имеет ли данный избиратель стимул к манипулированиюпри ФПИ , необходимо иметь все профили предпочтений из его информаци-75онного множества, в противном случае можно пропустить именно те профили,которые делают манипулирование выгодным.
По этой причине сокращение перебора за счет случайного выбора профилей неприменимо в данном случае. Дляуменьшения объема затраченных вычислительных ресурсов было использованомножество анонимных профилей, число которых (!+−1)!/((!−1)!!). Длякаждого анонимного профиля, т.е. вектора распределения типов предпочтенийкаждого вида, ⃗ = (1 , ..., ! ), строится один из !/(1 !...! !) соответствующих ему обыкновенных профилей.
Для него проверяется, имеет ли хотя бы одинизбиратель стимул манипулировать при данной ФПИ . Если профиль манипулируем, то в индексе 1 числитель увеличивается на !/(1 !...! !), так как всепрофили, соответствующие данному анонимному профилю, будут манипулируемы. Таким образом, результаты вычислительных экспериментов представляютсобой не приближенные, а точные значения индексов.Программа для вычисления индекса была написана в MatLab, описание программного комплекса представлено в разделе 2.6, исходные коды модулей программы приведены в Приложении B.
Результаты вычислений представлены нарисунках 2.6-2.11, где по оси абсцисс располагается количество избирателей, ,а по оси ординат – значения 1 ( , , 3, ).На графиках видно, что доля профилей, допускающих манипулирование, нестановится меньше при менее информативной ФПИ. И хотя не наблюдаетсястрого монотонной зависимости между информативностью ФПИ и значениями1 , можно легко видеть, что для большинства рассматриваемых значений приLeximin и Leximax для правила относительного большинства и правила Бордавыполнено1 ( , , 3, ) ≥ 1 ( , , 3, ) ≥ 1 ( , , 3, ),76110.80.80.60.60.40.40.20.202468101214160а) Правило относительногобольшинства2468101214161416б) Правило Борда110.80.80.60.60.40.40.20.2002468101214110.80.80.60.60.40.40.20.2246810124681012г) Двухступенчатая мажоритарнаясистемав) Правило вето021614016д) Правило передачи голосов2468101214е) Правило Коупленда1 Profile0.5 Positions0 Score01020RankWinnerРисунок 2.6.
Значения 1 ( , , 3, ) при Leximin7716110.80.80.60.60.40.40.20.20246810121416024а) Правило относительногобольшинства68101214161416б) Правило Борда110.80.80.60.60.40.40.20.2002468101214110.80.80.60.60.40.40.20.2246810124681012г) Двухступенчатая мажоритарнаясистемав) Правило вето021614016д) Правило передачи голосов2468101214е) Правило Коупленда1 Profile0.5 Positions0 Score01020RankWinnerРисунок 2.7.
Значения 1 ( , , 3, ) при Leximax7816110.80.80.60.60.40.40.20.20246810121416024а) Правило относительногобольшинства68101214161416б) Правило Борда110.80.80.60.60.40.40.20.2002468101214110.80.80.60.60.40.40.20.2246810124681012г) Двухступенчатая мажоритарнаясистемав) Правило вето021614016д) Правило передачи голосов246810121416е) Правило КоуплендаProfilePositions1Score0.50Rank01020Winner1WinnerРисунок 2.8. Значения 1 ( , , 3, ) при алфавитном правиле устранениянесравнимости79а для правила передачи голосов и двухступенчатой мажоритарной системы1 ( , , 3, ) ≥ 1 ( , , 3, ) ≥ 1 ( , , 3, ) ≥≥ 1 ( , , 3, ).При алфавитном правиле устранения множественности выбора выполнены теже неравенства для большинства рассматриваемых значений , а также1 ( , 1 , 3, ) ≥ 1 ( , , 3, ).Получаем, что наибольшие значения индекса манипулируемости 1 для этихправил соответствуют наименее информативной ФПИ, из которой вычислимрезультат голосования.
Более того, при правиле относительного большинства иправиле Борда уже начиная с 10 избирателей в 95% случаев найдется избиратель, которому будет выгодно исказить свои предпочтения при ФПИ-Winner cLeximin/Leximax и при ФПИ-1Winner c алфавитным правилом (в случае правила относительного большинства вычисления иллюстрируют результат Теоремы2.4.2).Для правила Коупленда при Leximin значения индекса 1 слабо возрастаютвдоль цепочки ФПИ от Profile до Rank для всех от 3 до 15. При Leximax иалфавитном правиле выполнены следующие неравенства1 (, , 3, ) ≥ 1 (, , 3, ) ≥ 1 (, , 3, ) ≥≥ 1 (, , 3, ) ≥ 1 (, , 3, ).Интересныйэффект,которыйнаблюдается– это периодичность индекса 1мякакпикидляправилаКоуплендас высокой амплитудой. В то вре-1 (, , 3, ) (для80LeximinиLeximax)и1 (, 1 , 3, ) (для алфавитного правила устранения несравнимости) приближаются к 1 с ростом , наименьшие значения этих же индексовблизки к нулю и являются минимальными среди всех остальных ФПИ.
Виднотакже, что для Leximax и ФПИ-Winner правило Коупленда не подверженоманипулированию, если число избирателей нечетно (Теорема 2.4.4).Для правила вето графики выглядят иначе: наибольшие значения индекса1 соответствуют ФПИ-Rank, а значения 1 ( , , 3, ) для Leximin иLeximax не выше, чем 1 ( , , 3, ) и 1 ( , , 3, ). При алфавитном правиле устранения множественности выбора правило вето не подвержено манипулированию при ФПИ-1Winner, что иллюстрирует результат Теоремы 6 в [11].110.50.502468101214160а) Правило относительногобольшинства2468101214161416б) Правило Борда110.50.500246810121416110.50.524681012144681012г) Двухступенчатая мажоритарнаясистемав) Правило вето02016д) Правило передачи голосов2468101214е) Правило КоуплендаWMGMGРисунок 2.9.
Значения 1 ( , , 3, ) при Leximin8116Остальные нулевые значения индекса относятся к случаям, когда правилоне вычислимо из ФПИ. Так, индекс 1 ( , , 3, ) равен 0 для правила относительного большинства, вето, правила передачи голосов. В то же время,значения 1 ( , , 3, ) для правила Борда очень высокие, а в случае трехизбирателей мы имеем 100% манипулируемость для метода Leximin. Однаконесмотря на то, что правило относительного большинства не вычислимо изФПИ-WMG, значения индекса 1 ( , , 3, ) довольно высокие: 0,30,5.
В то же время, информация о графе мажоритарного отношения (ФПИ-MG)в большинстве случаев не позволяет избирателям выбрать стратегию манипулирования, так как результат может быть как более выгодным, так и менее, ииндекс 1 ( , , 3, ) равен 0, начиная с 5, с 7 и с 9 избирателей дляLeximin, Leximax и алфавитного правила, соответственно.110.50.502468101214160а) Правило относительногобольшинства2468101214161416б) Правило Борда110.50.500246810121416110.50.524681012144681012г) Двухступенчатая мажоритарнаясистемав) Правило вето02016д) Правило передачи голосов2468101214е) Правило КоуплендаWMGMGРисунок 2.10.
Значения 1 ( , , 3, ) при Leximax8216110.50.502468101214160а) Правило относительногобольшинства2468101214161416б) Правило Борда110.50.500246810121416110.50.524681012144681012г) Двухступенчатая мажоритарнаясистемав) Правило вето02016д) Правило передачи голосов246810121416е) Правило КоуплендаWMGMGРисунок 2.11. Значения 1 ( , , 3, ) при алфавитном правиле устранениянесравнимостиНекоторые выводы.
Так как самого факта подверженности правил голосования манипулированию при неполной информации недостаточно, было решеновыяснить, в какой мере правила подвержены такому манипулированию. Послетеоретического анализа и вычислительных экспериментов, представленных вданном разделе, мы можем сделать вывод о том, что вероятность манипулирования нельзя рассматривать как основной индекс манипулируемости в случаенеполной информации, так как это может привести к неправильной интерпретации результатов. Действительно, близкая к 1 вероятность манипулированияозначает, что практически всегда в большом коллективе найдется хотя бы одинизбиратель, для которого манипулирование будет хотя бы с очень малой вероятностью, но более выгодно, чем искреннее голосование.
При этом в большом83числе случаев манипулирование не приведет к успеху, так как степень влиянияотдельного избирателя крайне мала. Чтобы учесть эти аспекты, необходиморассмотреть другие показатели манипулируемости.2.5Успех манипулирования и стимул к манипулированиюПолученные в предыдущем разделе результаты противоречат интуитивномупредположению о том, что манипулируемость должна быть тем меньше, чемменьше информации у избирателей, и чем больше число участников голосования.
Следовательно, индекс 1 в данном случае не показывает нам полнуюкартину манипулирования.Вводятся в рассмотрение следующие два индекса: вероятность успеха манипулирования2и индекс стимула к манипулированию. Пусть(⃗ ) (⃗ )′(˜ ) = {⃗−∈ ′: (⃗ ) (˜ , ⃗−)}.– множество тех профилей информационного множества избирателя , в которых манипулирование при помощи стратегии ˜ приведет к худшему результату. Пусть(⃗ ) (⃗ )′′(˜ ) = {⃗−∈ : (˜ , ⃗−) (⃗ )}.– множество профилей информационного множества избирателя , в которыхманипулирование при помощи стратегии ˜ приведет к успеху.Обозначим через 2 вероятность того, что в случайно выбранном профилехотя бы один избиратель имеет стимул манипулировать и его манипулирование2 Авторами [3] в индексе свободы манипулирования + также рассматривалась вероятность успеха манипулирования, однако1совершенно в ином ракурсе. 1+ – вероятность того, что манипулирование будет успешно при случайном выборе профиля,случайном выборе избирателя и случайном выборе неискренней стратегии манипулирования в предположении о наличии полнойинформации.84успешно в этом профиле.
Формально2 ( , , , ) = |{⃗ ∈ () : ∃ ∈ ∃˜ ∈ (),(⃗ ) (⃗ )(˜ ) = ∅ & (˜ ) ̸= ∅}|/(!) .Пример 2.3. Рассмотрим условия Примера 2.2. Как было показано, избиратель 3 имеет стимул манипулировать при правиле относительного большинстваи ФПИ-1Winner, следовательно, этот профиль учитывается в индексе 1 . Нотак как избиратели 1 и 2 не имеют стимула манипулировать, а манипулиро-⃗ , то в индексе успехавание избирателя 3 не приводит к успеху в профиле манипулирования, 2 , этот профиль не учитывается.Другое свойство манипулирования при неполной информации: количествопрофилей из информационного множества избирателя, где манипулированиеприводит к успеху, может быть очень малым по сравнению с мощностью всегоинформационного множества. Чтобы его учесть, введем переменную, измеряю-⃗ , (⃗ )),щую стимул к манипулированию для каждого избирателя, (, ⎧⃗)(⎪| (˜ )|⎪⎪, если избиратель max˜⃗⎪( ) ∈()⎪||⎪⎨⃗⃗(, , ( )) = имеет стимул манипулировать при ФПИ ,⎪⎪⎪⎪⎪⎪⎩0, иначе.Далее для данного профиля вычисляется максимальный по всем избирателям стимул к манипулированию, который и ставится в соответствие профилюпредпочтений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
