Диссертация (Степень манипулируемости процедур агрегирования), страница 5

Тогда, если для всехтаких и ожидаемая полезность от набора больше, чем от набора , то считается лучше, чем . Ясно, что если и не даны, то этот принцип недает полного упорядочения подмножств .Авторами также используется свойство единогласия для процедур, однакоего формулировка отлична от приведенной в [22]:Определение 1.10. Правило удовлетворяет свойству единогласия (по Чин⃗ ∈ () ∀ ∈ если ∀ ∈ ∀ ∈ ∖{} , то ∈ (⃗ ).гу и Чжоу), если ∀При таком определении единогласие следует из неманипулируемости автоматически, поэтому в своей теореме авторы рассматривают только правила,удовлетворяющие этому свойству.Теорема 1.2.4.

[25] Если правило коллективного выбора защищено от манипулирования и || ≥ 3, то оно является диктаторским.Похожая модель манипулирования в условиях множественного выбора быларассмотрена в [26], где также используется понятие функции полезности длясравнения наборов альтернатив. Однако распределение вероятностей для каждого набора является общим для всех избирателей, а не субъективным. Предполагается, что избиратель имеет стимул манипулировать, если для любых⃗ ) и ( ′ , ⃗− ) существует функция полезраспределений вероятностей на (⃗− )ности избирателя , , такая, что ожидаемая полезность от набора (′ , 27⃗ ) (в отличие от [25], где рассматривались все , согласубольше, чем от (ющиеся с ).

Авторами была доказана несовместимость неманипулируемостии отсутствия диктатора со свойствами остаточной разрешимости и ненавязанности.Определение 1.11. Пусть у всех избирателей, кроме одного, , предпочтенияодинаковые и – на первом месте, а – на втором.

Предпочтения -ого либо такие же, либо – на первом месте, – на втором. Если выбор правила во всех таких случаях состоит из единственной альтернативы, то правилоудовлетворяет свойству остаточной разрешимости.Определение 1.12. Правило удовлетворяет свойству ненавязанности, ес⃗ такой, что ∈ (⃗ ).ли ∀ ∈ ∃Теорема 1.2.5. [26] При || ≥ 3 не существует защищенного от манипулирования правила коллективного выбора , удовлетворяющего одновременносвойствам остаточной разрешимости, ненавязанности и отсутствия диктатора.Наконец, в работах [27–29] рассмотрено несколько методов расширения предпочтений, в том числе и лексикографические. В [28] доказано, что при заданныхметодах расширения предпочтений не существует защищенных от манипулирования правил коллективного выбора, удовлетворяющих свойствам анонимно-⃗ ∈ () такие,сти, нейтральности и условию C1 (range condition: ∃ ∈ &∃⃗ ) = {}).

В [29] показано, что этот результат следует из теоремы,что (представленной в более ранней работе тех же авторов [27].1.2.3Манипулирование при неполной информацииОсновная предпосылка, которая используется в описанных в предыдущемразделе работах – наличие у каждого избирателя полной информации об истинных предпочтениях всех остальных участников голосования. Поэтому в каж28дой конкретной ситуации манипулирующий избиратель может точно рассчитать результат манипулирования, предполагая, что голоса остальных останутсяискренними и неизменными. Если по каким-то причинам не вся информациястановится доступна избирателю, то результат манипулирования не всегда возможно посчитать точно.Одна из первых попыток дать формализацию задаче манипулирования принеполной информации сделана в [30].

Как было замечено авторами, для того,чтобы манипулировать, избирателю необходимо знать достаточно о предпочтениях остальных избирателей и иметь возможность посчитать, приведут ли егостратегические действия к более выгодному результату.Доказательство теоремы типа Гиббарда-Саттертуэйта для случая с неполной информацией было сделано в [11].

Авторы предлагают такую интерпретацинеполной информации: пусть перед голосованием проводится опрос избирате-⃗ . Затем избиралей, на котором они сообщают свои искренние предпочтения, телям сообщаются результаты опроса, представленные в некотором агрегиро-⃗ ). Функция называется функцией публичной информацииванном виде, ((ФПИ), авторы рассматривают следующие виды ФПИ.⃗ ) = ⃗ .1.

Профиль предпочтений (ФПИ-Profile): (⃗)2. Анонимный профиль предпочтений (ФПИ-Ballot): (=⃗(⃗ )=(1 , ..., ! ).3. Количество очков, набранных кандидатами согласно функции (ФПИ-⃗ ) = (⃗ ⃗ ) = ((1 , ⃗ ), ..., ( , ⃗ )).Score): (⃗ ) = (⃗ ).4. Ранжирование кандидатов согласно функции (ФПИ-Rank): (⃗ ) = (⃗ ).5. Победители по правилу (ФПИ-Winner): (296. Матрица взвешенного графа мажоритарного отношения (ФПИ-WMG):(⃗ ) = (⃗ ), где (⃗ ) = |{ ∈ : }|.⃗ ) = (⃗ ), где7. Матрица графа мажоритарного отношения (MG): ( (⃗ ) =⎧⎪⎪⎪1,⎪⎪⎪⎨⃗ ) > (⃗ ) ,если (−1, если (⃗ ) > (⃗ ) ,⎪⎪⎪⎪⎪⎪⎩0,иначе.⃗ ) = 0.8. Нулевая ФПИ (Zero-ФПИ): не дает какой-либо информации, (⃗ ) о профиле предпочтений и знаяТаким образом, обладая информацией (свои собственные предпочтения, избиратель имеет множество согласующихсяс этой информацией профилей предпочтений – информационное множество(⃗ ).(⃗ )′′ ) = (⃗ )}= {⃗−∈ () ∖{} : ( , ⃗−.Определение 1.13.

Пусть даны две ФПИ и ′ . Если ∀⃗ ∈ () и ∀ ∈ (⃗ )выполнено ′ (⃗ )⊆ , то является не менее информативной, чем ′ .Таким образом, чем у́же информационное множество (чем меньше множество возможных ситуаций с точки зрения избирателя), тем более информативнаФПИ. Очевидно, что наиболее информативной является ФПИ-Profile.Понятие информационного множества избирателя для обозначения множества профилей предпочтений, согласующихся с имеющейся у избирателя информацией, используется и в работе [10]. Авторы предлагают модель, в которой каждому избирателю известна лишь часть информации о предпочтенияхдругих, а именно некоторое подмножество для каждого избирателя, часть30упорядоченных по предпочтительности пар.

В случае с неполной информациейизбиратель не знает, какой из профилей его информационного множества реализовался в действительности. Поэтому предполагается, что избиратель имеетстимул манипулировать, если при некоторой его стратегии результат во всехпрофилях информационного множества не станет для него хуже, и существуют профили, где результат станет лучше [10, 11].Определение 1.14. Дана правило и профиль ⃗ . Избиратель имеет стимул к манипулированию при ФПИ , если существуют предпочтения ̃︀ ∈ ()такие, что(⃗ )′′ (̃︀ , ⃗−) (⃗ ) или (̃︀ , ⃗−) (⃗ );(⃗ )⃗ ′ ) (⃗ ).такой, что (̃︀ , −⃗′ ∈ а) ∀−⃗′ ∈ б) ∃−Определение 1.15. Правило называется подверженным манипулированию при ФПИ , если ∃ ∈ и ∃⃗ ∈ () , в котором имеет стимул кманипулированию при ФПИ .В рамках этой модели авторы [10] рассматривают вычислительную сложность манипулирования для различных правил, и этот вопрос будет рассмотренв следующем разделе Главы 1.Чтобы некоторым образом формализовать условия, при которых избирательимеет возможность манипулировать при неполной информации, в работе [11]вводится понятие сильной вычислимости из данной ФПИ для правил коллективного выбора.Определение 1.16.

Если информации (⃗ ) достаточно, чтобы избиратель мог вычислить результат правила при всех возможных вариантах голосованияэтим избирателем, ̃︀ ∈ (), то правило называется сильно вычислимым изФПИ .31Теорема 1.2.6. [11] При || ≥ 3 любое однозначное правило коллективного выбора, удовлетворяющее свойству ненавязанности и отсутствия диктатора,сильно вычислимое из ФПИ , является подверженным манипулированию приФПИ .Результат теоремы означает, что, если ФПИ предоставляет достаточно информации для того, чтобы избиратель мог точно посчитать результат правилапри манипулировании, то правило подвержено манипулированию точно так же,как и в случае с полной информацией. Однако сильная вычислимость не является необходимым условием.

Как показано в [11], правило может быть подвержено манипулированию и тогда, когда оно не является сильно вычислимым изданной ФПИ.Для работы с множественностью выбора в [11] используется алфавитное пра-вило : 2 ∖ {∅} → : предположим заранее заданным некоторый линейныйпорядок на , ..., и из данного множества альтернатив выбираем ту,которая доминирует по все остальные альтернативы в множестве.Далее мы перечислим основные результаты из [11] о случаях манипулируемости правил или защищенности от манипулирования с тем, чтобы сопоставитьс результатами, представленными в Главе 2.Теорема 1.2.7.

[11] При || ≥ 3 и четном числе избирателей любое правилоколлективного выбора, удовлетворяющее критерию Кондорсе, при алфавитномправиле устранения множественности выбора, подвержено манипулированиюпри ФПИ-MG.Теорема 1.2.8. [11] При || ≥ 3 и ≥ 4 любое правило правило подсчета очков, удовлетворяющее свойству единогласия, при алфавитном правиле устранения множественности выбора, подвержено манипулированию при ФПИ-Winner.32В [11] рассматривается также несколько случаев защищенности правил отманипулирования, в том числе вырожденный случай, случай с нулевой информацией.

При нулевой информации, очевидно, любое правило защищено от манипулирования. Кроме того, приводятся следующие две теоремы.Теорема 1.2.9. [11] При ≥ 2 − 2 и алфавитном правиле устранения множественности выбора правило вето защищено от манипулирования при ФПИWinner.Теорема 1.2.10.

[11] При ≥ 10 и алфавитном правиле устранения множественности выбора правило относительного большинства защищено от манипулирования при ФПИ-MG.1.3Оценка степени манипулируемости правил коллективного выбораКак было замечено Аланом Гиббардом: «назвать правило манипулируемым –это не значит сказать, что в данной ситуации какой-то избиратель имеет стимулманипулировать.

Это значит сказать, что в какой-то из возможных ситуацийкто-то сможет манипулировать».Так как практически все разумные процедуры подвержены манипулированию, то возникает необходимость сравнивать степень манипулируемости разных правил. Один из подходов к решению этой задачи – вероятностный – рассматривает степень манипулируемости как вероятность возникновения такойситуации, при которой возможно манипулирование. Обзору результатов этойобласти и посвящен данный раздел.Чтобы посчитать вероятность некоторого события (в нашем случае, возникновения возможности индивидуального или коалиционного манипулирования),необходимо задать множество элементарных исходов.