Диссертация (1137313), страница 10
Текст из файла (страница 10)
Граф мажоритарного отношения (MG): (В отличие [11] (см. раздел 1.2.3), мы не рассматриваем нулевую ФПИ, таккак она не представляет какого-либо практического интереса. Дополнительновводится в рассмотрение ФПИ-Positions, так как она является промежуточной между ФПИ-Ballot и ФПИ-Score и, кроме того, ключевой для определенияправил подсчета очков. Далее мы повторим некоторые определния, уже рассмотренные в Разеделе 1.2.3, для того, чтобы не нарушать последовательностьизложения материала.(⃗ )Информационное множество избирателя – (⃗ ), определяется как′′ ) = (⃗ )}= {⃗−∈ () ∖{} : ( , ⃗−.Определение 2.1. Для двух ФПИ и ′ , если ∀⃗ ∈ () и ∀ ∈ выполнено(⃗ ) ′ (⃗ )⊆ , то является не менее информативной, чем ′ .Определение 2.2. Дано правило и профиль ⃗ .
Избиратель имеет стимулк манипулированию при ФПИ , если существуют предпочтения ̃︀ ∈ ()такие, что(⃗ )′′ (̃︀ , ⃗−) (⃗ ) или (̃︀ , ⃗−) (⃗ );(⃗ )⃗ ′ ) (⃗ ).такой, что (̃︀ , −⃗′ ∈ а) ∀−⃗′ ∈ б) ∃−59Определение 2.3. Правило называется подверженным манипулированию⃗ ∈ () , в котором имеет стимул к манипулипри ФПИ , если ∃ ∈ и ∃рованию при ФПИ .Пусть 1 ( , , , ), – вероятность того, что в случайно выбранном профиле предпочтений существует хотя бы один избиратель, имеющий стимул кманипулированию при данном правиле и ФПИ .Далее мы будем называть этот индекс вероятностью манипулирования длякраткости изложения, хотя, конечно, его нужно понимать как вероятность возниконовения возможности манипулирования, так как иметь стимул к манипулированию еще не значит манипулировать.Для простоты исследования предполагаем, что все (!) профилей равновероятны (предпосылка Impartial Culture model – модели независимых предпочтений).
В этом случае 1 ( , , , ) – доля профилей предпочтений, где естьизбиратель, имеющий стимул к манипулированию при данном правиле иФПИ .Пример 2.2. Пусть используется правило относительного большинства и алфавитное правило устранения множественности выбора ( ), результаты⃗ ) = ( (⃗ )). Рассмотрим проопроса представлены ФПИ-1Winner, т.е. (филь предпочтений⎛⎞⎜ ⎟⎜⎟⎟⃗ = ⎜⎜ ⎟ .⎝⎠ (⃗ ) = {}, ( (⃗ )) = . Для третьего избирателя альтернатива на последнем месте в предпочтениях. Покажем, что он имеет стимул маниулировать.⃗ )) = возможно в двух случаях: 1) (⃗ ) = {};Действительно, ( (⃗ ) = {, , }. В первом случае () = 2, () = 1, и избиратель 32) (60не может повлиять на результат выбора. Во втором случае, если избиратель3 голосует за свою вторую наилучшую альтернативу, (заявляя неискренниепредпочтения ˜3 = (, , ) или ˜3 = (, , )), то альтернатива получит 2 голосаи будет выбрана единственным победителем, что более предпочтительно для избирателя 3, чем .
Таким образом, для части профилей информационного множества избирателя 3 результат выбора после манипулирования не изменится, нодля остальных профилей манипулирование приведет к успеху. Следовательно,⃗ при правиле относительногоизбиратель 3 имеет стимул манипулировать в большинства и ФПИ-1Winner.⃗ ) = {}Заметим, что при ФПИ-Winner избиратель 3 знает результат (и то, что манипулирование не приведет к успеху.
Следовательно, при ФПИWinner и прочих равных условиях избиратель 3 не имеет стимула к манипулированию.2.2.4Функции общественного благосостоянияВ данном разделе представлено описание используемых в исследовании правил. Необходимо определить не только результат правила коллективного выбо-⃗ ), но также ранжирование = ∪ и способ построения ФПИ-Score.ра, (∙ Правила подсчета очков. Любое правило из этого семейства определяетсявектором = (1 , ..., ), где обозначает количество очков, присваиваемых альтернативе за -ю позицию в индивидуальных предпочтениях избирателя. Общее количество очков для альтернативы ∈ рассчитывается⃗ ) = ⟨, ( , ⃗ )⟩.как скалярное произведение ( , Тогда ранжирование = ∪ определяется следующим образом: ∀ , ∈ а) ⇔ ( , ⃗ ) > ( , ⃗ ); б) ⇔ ( , ⃗ ) = ( , ⃗ ).– Правило относительного большинства (Plurality): = (1, 0, ..., 0).61– Правило вето (Veto): = (1, ..., 1, 0).– Правило Борда (Borda): = ( − 1, − 2, ..., 1, 0).∙ Двухступенчатая мажоритарная система (Runoff).
Состоит из двух этапов:1) Для каждой альтернативы подсчитывается количество очков по правилуотносительного большинства. Вектор очков для первого этапа 1 (⃗ ) = ( 1 (1 , ⃗ ), ..., 1 ( , ⃗ )),⃗ ) = ⟨ , ( , ⃗ )⟩. Если ∃ ∈ т.ч. 1 ( ) > /2, то =где 1 ( , ∪ определяется следующим образом ∀ , ℎ ∈ ∖ { } , ℎ ,и процедура останавливается. Если такой альтернативы нет, то процедурапереходит на второй этап.2) Выбираются две альтернативы с наибольшим количеством очков: = ∈ ( 1 ( , ⃗ )), = ∈∖{ } ( 1 ( , ⃗ )).Если возникает ничья, то применяется алфавитное правило устранениямножественности выбора . Далее рассчитывается вектор очков второго⃗ ) = ( 2 ( , ⃗ ), 2 ( , ⃗ )),этапа 2 ( 2 ( , ⃗ ) = ⟨ , ( , ⃗ /{ , })⟩, 2 ( , ⃗ ) = ⟨ , ( , ⃗ /{ , })⟩.62Альтернатива, набравшая большее количество очков, считается лучшей,⃗ ) > 2 ( , ⃗ ), и , если 2 ( , ⃗ ) > 2 ( , ⃗ ).т.е.
, если 2 ( , Обе альтернативы второго этапа считаются лучше, чем все остальные,∀ ∈ ∖ { , } , . Все остальные альтернативы несравнимы, т.е. ∀ , ℎ ∈ ∖ { , } ℎ . Таким образом, результат ФПИ-Score(⃗ ) = ( 1 (⃗ ), 2 (⃗ )).∙ Правило передачи голосов (STV – Single Transferable Vote) – многоступенчатая процедура, которую мы определим рекурсивно.⃗.0) := 1, := , ⃗ := ⃗ ) := ⟨ , ( , ⃗ )⟩.1) ∀ ∈ ( , ⃗ ) > /2, то ∀ℎ , ∈ ∖ { }2) Если ∃ ∈ такая, что ( , ℎ , ℎ , и процедура заканчивается. В противном случае := ∈ ( ( , ⃗ )), ∀ ∈ ∖ { } .⃗ / .
Процедура переходит к шагу 1.3) := + 1, := −1 ∖ { }, ⃗ := ⃗ ) = ( 1 (⃗ ), ..., * (⃗ )), где * – количеРезультат функции ФПИ-Score (ство циклов, совершенных процедурой.∙ Правило Коупленда (Copeland). Вычисляется граф мажоритарного отношения. Затем очки альтернатив рассчитываются следующим образом( , ⃗ ) =∑︁ (⃗ ) .=1Ранжирование = ∪ определяется количеством набранных альтернативами очков: ∀ , ∈ ⃗ ) > ( , ⃗ );а) ⇔ ( , ⃗ ) = ( , ⃗ ).б) ⇔ ( , 632.3Вычислимость и сильная вычислимостьФПИ предоставляет избирателям некоторую информацию о предпочтенияхколлектива и иногда использует саму функцию .
Некоторые типы ФПИ поз-⃗.воляют вычислить результат голосования при Определение 2.4. Если существует функция такая, что = ∘ (композиция функций и ), то правило коллективного выбора называетсявычислимым из ФПИ .Определение 2.5. Если информации (⃗ ) достаточно, чтобы избиратель мог вычислить результат правила при всех возможных вариантах голосования этимизбирателем, ̃︀ ∈ (), то правило называется сильно вычислимым из ФПИ.Ясно, что вычислимо из ФПИ тогда и только тогда, когда не ме(⃗ )⃗ ′ , ⃗ ′′ ∈ нее информативна, чем ФПИ-Winner, ∀⃗ ′ ) = (⃗ ′′ )) (или, (ФПИ-1Winner, если используется правило устранения множественности выбора).Другое полезное наблюдение: если не менее информативна, чем ′ , и сильно вычислимо из ′ , то также сильно вычислимо из .Теперь перейдем к вопросу вычислимости и построению отношения «быть неменее информативным» для шести рассматриваемых правил и проиллюстрируем его на ориентированных графах.⃗ ∈ () , ∀ ∈ ,Для правил подсчета очков ∀⃗⃗(⃗ ) ⊆ ⃗ (⃗ )⊆ ⃗ ⃗ )(⊆ (⃗ )⊆ (⃗ )⊆ ( (⃗ ))⊆ .Следовательно, любое правило подсчета очков вычислимо из всех ФПИ данной последовательности.64Для двухступенчатой мажоритарной системы и для правила передачи голо-⃗ ) недостасов из этой цепи выпадает ФПИ-Positions, так как информации ⃗ (точно для того, чтобы вычислить победителя.Для правила Борда ФПИ-WMG содержит в себе всю необходимую информацию для того, чтобы вычислить победителя и является не менее информатив (⃗ )⃗ ⃗ )(⃗ ∈ () ной, чем ФПИ-Score, т.е.
∀ ∈ ∀⊆ .Лемма 2.1. ФПИ-WMG не менее информативна, чем ФПИ-Score для правилаБорда.Доказательство. ( , ⃗ ) = 1 ( , ⃗ ) · ( − 1) + ... + −1 ( , ⃗ ) · 1 =⎛⎜=⎜⎝⎞∑︁∈ :| |=−1⎛⎞−1∑︁ ∑︁∑︁⎟⎜ ∑︁ ⎟⎜⎟·1=1⎟·(−1)+...+1=| | =⎠⎝⎠∑︁ ∑︁∈ :| |=11=∈ ∈ ∑︁ ∑︁1=∑︁=1|{ ∈ : }| = ∈ ∈ ∈ ∈ :| |=∑︁∈ (⃗ ) ∈Кроме того, для любого правила коллективного выбора выполнено также (⃗ )⃗ ⊆ (⃗ )⊆ .
Однако среди рассматриваемых правил толькоправило Коупленда вычислимо из графа мажоритарного отношения. Цепочкавложений информационных множеств для правила Коупленда следующая⃗⃗(⃗ ) ⊆ (⃗ )⊆ (⃗ )⊆ ⃗ ⃗ )(⊆ 65 (⃗ )⊆ (⃗ )⊆ ( (⃗ ))⊆ .Однако избиратель не всегда сможет вычислить победителя голосования приФПИ-MG, если изменит свои предпочтения на ˜ ≠ , т.е. правило Коуплендане является сильно вычислимым из ФПИ-MG.Отношение информативности изображено на графах (Рисунки 2.1-2.4).Стрелка из в ′ показывает, что не менее информативна, чем ′ .
Понятие сильной вычислимости правила из данной ФПИ будет иметь далее важноезначение. На Рисунках 2.1-2.4 те ФПИ, из которых правило является сильновычислимым, отмечены кружками.Рисунок 2.1. Информативность ФПИдля правила относительногобольшинства и ветоРисунок 2.2. Информативность ФПИдля правила передачи голосов идвухступенчатой мажоритарнойсистемыРисунок 2.3. Информативность ФПИдля правила БордаРисунок 2.4. Информативность ФПИдля правила КоуплендаДвухступенчатая мажоритарная система и правило передачи голосов сильновычислимы только из ФПИ-Profile и ФПИ-Ballot. Для обоих правил, если аль-⃗− ) отличаются от тех, которыетернативы, удаленные на первом этапе в (̃︀ , ⃗ , то невозможно вычислить вектор очков второгоудаляются на первом этапе в ⃗− ), а следовательно, невозможно вычислить и победителя.этапа для (̃︀ , 66Правила подсчета очков сильно вычислимы из ФПИ-Score, что несложно показать следующим образом. Предположим, что избиратель получает⃗ ⃗ )(информацию=околичествеочковдлякаждойальтернативы,((1 , ⃗ ), ..., ( , ⃗ )).
Пусть предпочтения избирателя –1 2 3 ...−1 , тогда альтернатива получает очков от избирателя . Далее избиратель меняет свои предпочтения на ′ ,(1) ′ (2) ′ (3) ...(−1) ′ () .Так как избиратели знают применяемое правило, то новый вектор очков также известен избирателю . Для каждой альтернативы ∈ новый вектор оч-⃗ ) = ( , ⃗ ) − + −1 () . Следовательно, избиратель можетков есть ′ ( , вычислить победителя при любом своем неискреннем ′ ∈ ().2.42.4.1Вероятность манипулированияТеоретические результатыВ данном разделе представлены результаты теоретического анализа индекса 1 , вероятности манипулирования при ФПИ . Основной вопрос: как влияетналичие неполной информации на манипулируемость? Следующая теорема показывает, при каком условии вероятность манипулирования не изменяется посравнению со случаем полной информации.Теорема 2.4.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
