Диссертация (1137313), страница 13
Текст из файла (страница 13)
Таким образом, каждому профилю соответствует не просто 1или 0, а число из [0, 1] – мера манипулируемости профиля.85Пример 2.4. Снова обратимся к условиям Примера 2.2. Пусть неискренняястратегия избирателя 3 – ˜3 = (, , )посчитаем мощность информационного(⃗ )множества избирателя 3 и мощность 3(˜3 ).⃗ )) = имеем два типа профилей информационного множества:При ( (⃗ ) = {}; 2) (⃗ ) = {, , }.
В профилях первого типа избиратели1) (отдают голос за альтернативу , альтернативы и можно расположить в ихпредпочтениях 4 способами. В профилях второго типа избиратель 1 голосуетза , второй – за (или наоборот), и для каждого избирателя имеется два возможных типа предпочтений. Итого, второму случаю соответствует 8 профилей(⃗ )предпочтений. Мощность информацонного множества || = 4 + 8 = 12.Успех от манипулирования достигается только в профилях второго типа, по(⃗ )этому | 3(˜3 )| = 8.
Следовательно, (3, ⃗ , ( (⃗ ))) = 2/3. Таккак стимул остальных избирателей манипулировать в данном профиле равен 0,⃗ , учитываемая в индексе 3 .то 2/3 – мера маниулируемости Итак, 3 – сумма мер манипулируемости для всех профилей предпочтений,деленная на число всех профилей, (!) .
Индекс 3 ( , , , ) можно интерпретировать как агрегированный показатель стимула избирателей к манипулированию3 ( , , , ) =∑︁max ((, ⃗ , (⃗ ))/(!) .⃗ ∈()По определению, 2 ( , , , )∈≤ 1 ( , , , ) и 3 ( , , , ) ≤1 ( , , , ). В случае полной информации, (⃗ ) = ⃗ , все три индекса совпадают,1 ( , , , ) = 2 ( , , , ) = 3 ( , , , ).86Теорема 2.5.1. Если правило сильно вычислимо из ФПИ , то2 ( , , , ) = 3 ( , , , ) = 1 ( , , , ).Доказательство. Предположим, избиратель имеет стимул манипулировать⃗ , заявляя неискренние предпочтения ˜ .
Так какпри ФПИ в профиле (⃗ )′′′′ сильно вычислимо из ФПИ , то ∀⃗−, ⃗−∈ (˜ , ⃗−) =(⃗ )(⃗ )′′′ (˜ , ⃗−) и (˜ , ⃗−) (⃗ ). Следовательно, (˜ ) = и(, ⃗ , (⃗ )) = 1. Очевидно, что если нет таких ∈ , что имеет сти⃗ , (⃗ ))) = 0. Такиммул манипулировать при ФПИ , то max∈ ((, образом, 3 ( , , , ) = 1 ( , , , ) и по Теореме 2.4.1, 1 ( , , , ) =1 ( , , , ). Поэтому, если есть избиратель, имеющий стимул манипулиро⃗ , то его манипулирование успешно во всех профилях предвать при ФПИ в (⃗ )почтений из его информационного множества ⃗ . Следователь, включая но, 2 ( , , , ) = 1 ( , , , ) = 1 ( , , , ).Далее индексы 2 and 3 рассматриваются только для правила относительного большинства, как наиболее типичного и простого примера правилаколлективного принятия решений.
Результат следующей теоремы противопоставляется результату Теоремы 2.4.2 и дает представление об асимптотическомповедении индекса стимула к манипулированию, 3 , при стремящемся кбесконечности числе избирателей.Теорема 2.5.2. а) lim→∞ 3 ( , , , ) = 0 при методахLeximin и Leximax;б) lim→∞ 3 ( , 1 , , ) = 0 при алфавитном правиле устранения несравнимости.Доказательство. Предположим,чтоизбиратель имеет предпочтения1 2 3 ... . Согласно Leximin и Leximax, избиратель имеет стимул мани87пулировать при ФПИ в двух случаях: 1) единственным победителем является⃗ )| > 1 & 1 ∈альтернатива из множества {3 , 4 ,..., }); 2) | (/ (⃗ ).
При⃗ )| > 1.Leximin существует третий случай: 3) | (1) Рассмотрим случай 1, пусть альтернатива 3 является единственным по (⃗ )бедителем. В информационном множестве ⃗ ′ тасуществует профиль −кой, что количество очков, набранное второй наилучшей для альтернативой,′2 , на одно очко меньше, чем количество очков у 3 , т.е. (2 , ( , ⃗−)) =′(3 , ( , ⃗−)) − 1.
Если, манипулируя, проголосует за 2 , то результат ли-бо не изменится, либо будут выбраны две альтернативы, {2 , 3 }, что болеепредпочтительно для , чем {3 } согласно Leximin и Leximax. Стимул из-⃗ , (⃗ )), – это доля профилейбирателя к манипулированию, (, ′′′⃗−∈ () ∖{} , т.ч. (2 , ( , ⃗−)) = (3 , ( , ⃗−)) − 1 в общем числе профи-⃗ ′ ) = {3 }.лей, т.ч.
( , −Рассмотрим множество анонимных профилей (^1 , ..., ^ ), т.ч. ^ 1 + ... + ^ = − 1, где ^ - число избирателей, голосующих за -ю альтернативу. Обозначимℳ = {(^1 , ..., ^ ) ∈ Z^ 1 + ... + ^ = − 1 & ∀ ∈ {1, ..., } ∖ {3}, ^3 > ^ },+ : и1 = {(^1 , ..., ^ ) ∈ Z^ 1 + ... + ^ = − 1 & ∀ ∈ {1, ..., } ∖ {3},+ : ^3 > ^ , ^2 = ^ 3 − 1}.Далее посчитаем сумму профилей предпочтений в множествах ℳ и 1 спомощью функции (ℳ) =∑︁(^1 ,...,^ )∈(^1 + ... + ^ )!(( − 1)!)−1 .^ 1 !...^ !88Таким образом, стимул избирателя может быть выражен как(, ⃗ , (⃗ )) = (1 )/(ℳ).Рассмотрим множество анонимных профилей, в которых какие-либо две альтернативы имеют одинаковое количество очков.2 = {(^1 , ..., ^ ) ∈ Z+ : ^ 1 + ... + ^ = − 1, ∃, , ..
^ = ^ }.Общее количество профилей предпочтений равно (!) . Тогда доля профилей, где по правилу относительного большинства какие-либо альтернативы набирают одинаковое количество очков, равна (2 )/(!)3 . Так как вероятностьничьи стремится к 0 при числе избирателей, стремящемся к бесконечности [59],lim→∞ (2 )/(!)3 = 0.Возьмем произвольную точку из 1 , ⃗ = (^1 , ^ 2, ^ 2 + 1, ..., ^ ), и поставим всоответствие ей точку из 2 , ⃗′ = (^1 +1, ^ 2, ^ 2 , ..., ^ ). Таким образом, каждойточке из 1 соответствует только одна точка из 2 .
Оценим(⃗′ )!!2 + 1=/=≤ 0,(⃗)(1 + 1)!2 !2 !4 !... ! 1 !2 !(2 + 1)!4 !... ! 1 + 1т.е. (⃗′ ) ≥ (⃗), а следовательно, lim→∞ (1 )/(!) = 0. Так как вероятность ничьи среди победителей голосования также стремится к 0, тоlim→∞ (ℳ)/(!) = 1/ и(1 )/(!)(1 )lim=lim= 0.→∞ (ℳ)/(!)→∞ (ℳ)Доля профилей предпочтений, имеющих единственного победителя по правилу относительного большинства, в которых хотя бы один избиратель имеетстимул манипулировать при ФПИ-Winner, стремится к 1 (как показано в Теоре-89ме 2.4.2), однако величина стимула к манипулированию такого типа стремитсяк 0.2) Случаи 2 и 3 предполагают наличие ничьи среди победителей голосования, и манипулирующий избиратель в этом случае голосует за наиболее пред-⃗ ) в случае 2, и за альтернативу, котораяпочтительную альтернативу в (⃗ ) и лучше, чем наихудшая альтернатива в (⃗ ) в случаесодержится в (3.
Несмотря на то, что стимул к манипулированию для избирателя равен 1 вобоих случаях, доля профилей, в которых среди победителей есть ничья, стремится к 0.Таким образом, мы получаем, что lim→∞ 3 ( , , , ) = 0при Leximin и Leximax.3) Если используетcя алфавитное правило устранения множественности вы-⃗ ) = {3 }, либо Б ) | (⃗ )| > 1бора, и победителем является 3 , то либо А) (⃗ ) ∖ {3 }, 3 . Избиратель снова имеет стимул манипулировать,и ∀ ∈ (голосуя за 2 . В случае А), если 3 2 , то избиратель не сможет изменить⃗− , ′ ) = {3 , 2 } и 2 3 , то альтернатива 2 станет порезультат, если (бедителем.
В случае Б ) манипулирующий избиратель может сделать 2 побе-⃗ ). Таким образом, доля профилей предпочтедителем, только если 2 ∈ (ний, в которых манипулирование успешно, меньше, чем при методах Leximin иLeximax, а следовательно, она также стремится к 0 при бесконечном увеличениичисла избирателей.2.5.1Вычислительные экспериментыРассмотрим предложенные два индекса для правила относительного большинства в серии вычислительных экспериментов, сделанных в MatLab при помощи комплекса программ, описанного в разделе 2.6.
Так как правило отно-90110.80.80.60.60.40.40.2246810121416180.220а) ФПИ-Rank2468101214161820б) ФПИ-Winner0.80.6I0.4102000.202I1I32468101214161820в) ФПИ-WMGРисунок 2.12. Значения 1 , 2 и 3 для правила относительного большинствапри Leximinсительного большинства сильно вычислимо из ФПИ-Ballot, ФПИ-Positions иФПИ-Score, 2 и 3 для этих ФПИ равны 1 ( , , , ), вероятности манипулирования в случае полной информации (по Теореме (2.5.1)). Крометого, так как 1 ( , , 3, ) в большинстве случаев имеет значение 0,вычислений 2 ( , , 3, ) и 3 ( , , 3, ) не проводилось.Результаты вычислений представлены на рисунках 2.12-2.14.
По оси абсцисс– число избирателей от 3 до 20, по оси ординат – значения индексов.Некоторые выводыИндекс успеха к манипулированию, 2 , вычисленный для ФПИ-Rank и ФПИWinner, оказался равным индексу 1 ( , , , ). Это означает,⃗ ′ ∈ (⃗ ) ,что если для избирателя существуют профили предпочтений −(⃗ )где манипулирование успешно, (∃˜ (˜ ) ̸= ∅), то не существует таких⃗ ′ , где то же самое манипулирование приведет к худшему резульпрофилей −тату. Действительно, правило относительного большинства сильно вычислимо из данных ФПИ и монотонно, следовательно, избиратель знает победителей и имеет возможность повлиять на результат в лучшую для себя сторону91110.80.80.60.60.40.40.20.202468101214161802024а) ФПИ-Rank68101214161820б) ФПИ-Winner0.50.40.3I102000.20.102I1I32468101214161820в) ФПИ-WMGРисунок 2.13.
Значения 1 , 2 и 3 для правила относительного большинствапри Leximax0.60.80.50.60.40.40.30.20.20.12468101214161802024а) ФПИ-Rank10.50.40.60.30.40.20.20.124681012148101214161820161820б) ФПИ-Winner0.8061618020в) ФПИ-1Winner2468101214г) ФПИ-WMGI102002I1I3Рисунок 2.14. Значения 1 , 2 и 3 для правила относительного большинствапри алфавитном правиле устранения множественности выбора92без опасности ухудшить его. Разумеется, это не выполнено для ФПИ-WMG,2 ( , , , ) ≤ 1 ( , , , ), потому что победитель не может быть вычислен по взвешенному графу мажоритарного отношения, и голосование неискренне может как улучшить, так и ухудшить рузультатвыбора.Индексы 2 и 3 в большинстве случаев строго меньше, чем 1 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
