Диссертация (1137313), страница 11
Текст из файла (страница 11)
Если правило сильно вычислимо из ФПИ , то1 ( , , , ) = 1 ( , , , ).Доказательство. Пусть – искренние предпочтения избирателя . Избира-⃗ ). Так как сильно вычислимо из , то длятель получает информацию (всех неискренних предпочтений ̃︀ ∈ (() ∖ { }) и для любых двух профилей67⃗′ , ⃗′′ ∈ ( ) , (̃︀ , ⃗′ ) =из информационного множества избирателя, ⃗−−−′′ ). Кроме того, результат (̃︀ , ⃗′ ) известен избирателю. Таким об (̃︀ , ⃗−−′ ) (⃗ ) либо выполнеразом, при любом данном ̃︀ , соотношение (̃︀ , ⃗− ⃗⃗′ ∈ ( ) , либо не выполнено для всех ⃗′ ∈ ( ) .но для всех ⃗−−(⃗ )⃗′ ∈ Если ∃̃︀ ∈ (() ∖ { }), т.ч. ∀−⃗ ′ ) ( , ⃗ ′ ), зна, (̃︀ , −−⃗ ′ ) (⃗ ).
Следовательно, во всех профилях предчит в том числе и (̃︀ , −⃗ , где есть избиратель, имеющий стимул манипулировать при ФПИпочтений , также существует избиратель (тот же самый), имеющий стимул манипули⃗ существует избиратель, имеющийровать при ФПИ-Profile. И обратно: если в стимул манипулировать при ФПИ-Profile, то он же имеет стимул манипулировать при ФПИ . Следовательно, количество манипулируемых профилей одинаково при ФПИ и ФПИ-Profile, т.е. 1 ( , , , ) = 1 ( , , , ).Рассмотрим случай наименее информативной ФПИ: избирателям доступнаинформация только о победителях голосования (т.е.
ФПИ-Winner или ФПИ1Winner, если используется правило устранения множественности выбора).Теорема 2.4.2 показывает, как ведет себя индекс манипулируемости 1 дляправила относительного большинства при стремящемся к бесконечностичисле избирателей. С точки зрения практики этот случай также интересен:информацию в виде списка победителей опроса достаточно просто представитьизбирателям.Теорема 2.4.2. а) lim→∞ 1 ( , , , ) = 1 при методахLeximin и Leximax; б) lim→∞ 1 ( , 1 , , ) = 1 при алфавитном правиле устранения несравнимости.68Доказательство.
Пусть (⃗ ) = (⃗ ). Предположим, что победитель голосования – альтернатива , и что для избирателя альтернатива – наименеепредпочтительная. Найдем стратегию ˜ , которая с точки зрения выигрыша нехуже для , чем его искренние предпочтения ... .Так как в правиле относительного большинства считаются только альтернативы, находящиеся на первом месте в предпочтениях, мы можем говоритьпросто, что при искренних предпочтениях избиратель голосует за .
Если не выигрывает при искренних предпочтениях избирателя, , то нет такойстратегии, при которой альтернатива выиграла бы, следовательно, в ˜ альтернатива не на первом месте.Пусть избиратель голосует за свою вторую по предпочтительности альтерна-⃗ ) > (, ⃗ ) = (, ⃗− ).
(, (˜ , ⃗− )) = (, ⃗− )+1.тиву, , т.е. ˜ ...˜ . (, (⃗ )∀⃗− ∈ (⃗ )⃗− )) ≥ (, (˜ , ⃗− )), и ∃⃗− ∈ , (, (˜ , такой, что(, (˜ , ⃗− )) = (, (˜ , ⃗− )). Следовательно, если избиратель голосует за, то либо (˜ , ⃗− ) = {}, либо (˜ , ⃗− ) = {, }. Согласно Leximin иLeximax, исход {, } лучше, чем {} для , т.е. избиратель имеет стимул кманипулированию.Если используется алфавитное правило устранения множественности выбо-⃗ )) = {}, может бытьра, и - это ФПИ-1Winner, то результат правила, ( (⃗ ) = {}, либо | (⃗ )| > 1получен двумя возможными способами. Либо (⃗ ) ∖ {}, , и избиратель не может различать эти две ситуи ∀ ∈ (ации.
Если , то голосование за сделает победителем в случае ничьи (˜ , ⃗− ) = {, }. Если , то возможно, что ∈ (⃗ ) и голосование за сделает его победителем, (˜ , ⃗− ) = {}. Таким образом, если выигрываетнаименее предпочтительная альтернатива, избиратель имеет стимул манипулировать, голосуя за свою вторую по предпочтительности альтернативу.69Доля профилей предпочтений, где победитель единственен, стремится к 1, если число избирателей стремится к бесконечности1(если используется правилоустранения множественности выбора, то победитель всегда единственен). Найдем среди них долю профилей, где хотя бы один избиратель имеет выигрывающую альтернативу на последнем месте в предпочтениях.
Согласно предыдущимрассуждениям, все такие профили будут манипулируемы.Рассмотрим множество профилей предпочтений для избирателей с фиксированным распределением голосов: ^ 1 = 1 голосов подано за 1 , ^ 2 = 2 за 2 , и т.д. ( = ^ 1 + ... + ^ ). Число профилей в данном множестве=!(( − 1)!) .^ 1 !^2 !...^ !Число профилей, где альтернатива 1 не занимает последнее место в предпочтениях1 =!(( − 1)!)^ 1 (( − 1)! − ( − 2)!)^ 2 ...(( − 1)! − ( − 2)!)^ ^ 1 !^2 !...^ !.Доля профилей, где 1 не занимает последнее место, во множестве профилейс фиксированным распределением голосов равны(( − 1)!)^ 1 (( − 1)! − ( − 2)!)^ 2 ...(( − 1)! − ( − 2)!)^ 1==(( − 1)!)^ 1 (( − 1)!)^ 2 ...(( − 1)!)^ (︂1= 1−−1)︂^ 2(︂1...
1 −−1)︂^ (︂1= 1−−1)︂−^1.1 Как показано в [59], вероятность ничьи между любыми двумя альтернативами при правиле относительного большинствастремится к 0 при стремящемся к бесконечности числе избирателей (по центральной предельной теореме).70Следовательно, доля профилей, где хотя бы один избиратель имеет альтернативу 1 на последнем месте в предпочтениях)︂−^1(︂11− 1−−1.Наконец,(︃lim→∞(︂11− 1−−1)︂−^1 )︃(︃= lim→∞(︂11− 1−−1)︂(1−1 ) )︃= 1.Так, во множестве профилей с фиксированным распределением голосов,доля профилей, где 1 занимает последнее место хотя бы у одного избирателя, стремится к 1. Так как множество профилей с единственным победителем можно разбить на непересекающиеся подмножества профилей дляразличных распределений голосов, то во всем множестве доля профилейс 1 на последнем месте хотя бы у одного избирателя, стремится к 1.Итого, lim→∞ 1 ( , , , ) = 1 при Leximin и Leximax, иlim→∞ 1 ( , 1 , , ) = 1 при алфавитном правиле устранениянесравнимости.Таким образом, не всегда уменьшение информативности ведет к снижениюманипулируемости.
Кроме того, существует частный случай, когда манипулирование возможно в 100% профилей предпочтений.Теорема 2.4.3. При методе Leximin 1 (, , 3, 3) = 1.Доказательство. Так как = 3 и = 3, существует два возможных типа графа мажоритарного отношения: 1) ∃ ∈ () (перестановка, элемент сим-⃗ )(1),(2) = 1,метрической группы на множестве {1, 2, ..., }) такой, что ( (⃗ )(2),(3) = 1, (⃗ )(1),(3) = 1 (мажоритарное отношение транзитивно);71⃗ )(1),(2) = 1, (⃗ )(2),(3) = 1, (⃗ )(3),(1) = 12) ∃ ∈ (), т.ч.
((мажоритарное отношение циклично) (см. рисунок 2.5)а) Граф мажоритарного отношениятипа 1б) Граф мажоритарного отношениятипа 2Рисунок 2.5Рассмотрим случай 1. Без потери общности предположим, что (1) =1, (2) = 2, (3) = 3. В любом профиле предпочтений ⃗ , соответствующемтакому мажоритарному отношению, имеет место |{ ∈ : 1 2 }| ≥ 2.
Пустьэто будут избиратели 1 и 2 . В то же время |{ ∈ : 2 3 }| ≥ 2, и это могутбыть избиратели 1 , 3 , либо 2 , 3 , либо 1 , 2 . Таким образом, в любом случаесуществует по крайней мере один избиратель с предпочтениями 1 2 , 2 3 .По свойству транзитивности 1 3 . Для этого избирателя все профили пред-⃗− ∈ () ∖{} , в которых мажоритарное отношение ( , ⃗− )почтений соответствует типу 1, составляют информационное множество избирателя , (⃗ ).Для этого графа мажоритарного отношения элементы взвешенного графамажоритарного отношения удовлетворяют следующим неравенствам:3 ≥ 1,2 (⃗ ) ≥ 2, 3 ≥ 1,3 (⃗ ) ≥ 2, 1 ≥ 2,1 (⃗ ) ≥ 0,3 ≥ 2,3 (⃗ ) ≥ 2, 1 ≥ 3,1 (⃗ ) ≥ 0, 1 ≥ 3,2 (⃗ ) ≥ 0.72⃗) =Так как ( , ⃗ ∈ , ( ),∑︀ранг Борда для 1 – это значение измножества {4, 5, 6}, для 2 – {2, 3, 4}, а для 3 - {0, 1, 2}.
Следовательно, во всех (⃗ )профилях предпочтений из результат правила Борда – это либо {1 },либо {1 , 2 }. Если избиратель меняет свои предпочтения на ′ такие, что1 ′ 3 ′ 2 , то 2 больше не имеет возможности быть выбранным, в то время как3 все еще не имеет достаточно очков, чтобы быть выбранным вместе с 1 . Такимобразом, во всех профилях предпочтений, для которых граф мажоритарногоотношения имеет тип 1, существует по крайней мере один избиратель, имеющийстимул манипулировать.Рассмотрим тип 2. Существует два мажоритарных отношения, соответствую-⃗ )1,2 = 1, (⃗ )2,3 = 1, (⃗ )3,1 = 1, и (⃗ )1,3 = 1,щих этому типу: ( (⃗ )3,2 = 1, (⃗ )2,1 = 1. Во всех 12 профилях предпочтений, имеющихциклическое мажоритарное отношение, результат правила Борда – {1 , 2 , 3 }, илюбой избиратель , имеющий предпочтения 1 2 3 получит более предпчтительный для него результат голосования, если заявит неискренние предпочтения 2 ′ 1 ′ 3 , так как {2 } для него лучше, чем {1 , 2 , 3 } согласноLeximin.Таким образом, во всех профилях предпочтений существует хотя бы одинизбиратель, имеющий стимул манипулировать при правиле Борда, ФПИ-MG иметоде расширения предпочтений Leximin.Наконец, приведем результат об устойчивости к манипулированию дляправила Коупленда при ФПИ-Winner.Теорема 2.4.4.
При методе Leximax, 1 (, , 3, ) = 0 длянечетного числа избирателей.73Доказательство. Так как число избирателей нечетно, а число альтернатив 3,то результат правила Коупленда состоит либо из одной альтернативы, либо извсех трех, {, , } (парадокс Кондорсе).⃗ ) = (⃗ ) = {}, то существует два возможных мажоритарныхЕсли (отношения: 1) , , и 2) , , .Очевидно, что избиратели с предпочтениями и не имеют стимула манипулировать.Для избирателя, имеющего альтернативу на втором месте в предпочтениях, ( ), единственный более предпочтительный по Leximax идостижимый результат – {, , }. Такой исход может быть получен в мажоритарных отношениях А) , , или Б ) , , .
Еслиимеет место 1 (2), то мажоритарное отношение А (Б ) может быть получено, если избиратель манипулирует, заявляя предпочтения ( ). Вэтом случае он либо меняет мажоритарное отношение на , , ( , , ), либо ничего не меняет. Однако если имеет место 2 (1), тоизбиратель, заявляя ( ), может изменить мажоритарное отношениена , , ( , , ), и победителем станет альтернатива (), являющаяся наименее предпочтительной для избирателя. Мажоритарноеотношение Б (А) не может быть получено, так как избиратель не может изменить на . Следовательно, избиратели, имеющие на втором месте впредпочтениях, не имеют стимула манипулировать при ФПИ-Winner.Для избирателей, имеющих на последнем месте в предпочтениях, любойдругой исход является более предпочтительным, чем {}.
Однако ни один изних не является достижимым: если выигрывает несмотря на то, что избиратели, имеющие предпочтения или , голосуют искренне, тогданикакое другое (неискреннее) предпочтение не может изменить мажоритарное74отношение на или . Следовательно, ни у одного избирателя нет стимула манипулировать, если победитель единственен.Рассмотрим случай с исходом {, , }. Пусть лучшая альтернатива для избирателя – , и пусть . Для этого избирателя единственный исход, которыйлучше, чем {, , } по Leximax – это {}.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
