Диссертация (1137313), страница 9
Текст из файла (страница 9)
Тогда, предположив, что профили предпочтенийимеют некоторое априорное распределение вероятнотей, можно посчитать вероятность манипулирования для различных правил и найти наименее манипулируемое. Однако исследование этой вероятности зачастую основано на проведении вычислительных экспериментов, и достаточно обширный анализ затрудненв силу ограниченности вычислительных ресурсов. По той же причине в одномисследовании невозможно учесть все разнообразие условий реальных ситуаций принятия решений, и вводятся упрощающие предпосылки. Предположениео наличии полной информации у избирателей – одна из таких предпосылок.Переход к моделированию неполной информации при коллективном принятии51решений представляется, таким образом, важным и перспективным направлением в развитии этой области.Кроме того, в различных исследованиях применяются различные вероятностные модели для проведения экспериментов.
В какой степени полученные показатели зависят от выбранной вероятностной модели? Как отличается новаявероятностная модель, учитывающая свойства анонимности и нейтральности,от уже известных и применяемых в литературе моделей? Ответ на эти вопросыдан в настоящей диссертации.52Глава 2Манипулирование в условиях неполнойинформации2.1ВведениеВ Главе 1 данной диссертации был представлен обзор по теме манипулирования со стороны избирателей.
Базовая предпосылка большинства исследований – наличие полной информации у каждого из участников голосованияо предпочтениях всех остальных избирателей. В данной главе рассматривается проблема индивидуального манипулирования с применением вероятностногоподхода к анализу степени манипулируемости правил ( [3–6, 46]).
В отличие отпредыдущих исследований по данной теме, в используемой модели учитываетсянеполнота информации, доступной избирателям.Использование предпосылки о неполной информации позволяет приблизитьматематическую модель манипулирования при голосовании к реальным ситуациям принятия коллективных решений. Действительно, в обычных голосованиях невозможно, чтобы каждый избиратель знал предпочтения всех остальныхизбирателей от наиболее до наименее предпочтительного кандидата, особенно, если число избирателей больше 10. Информация, на основе которой могутпринимать решение избиратели (без использования вычислительных средств)53должна быть либо достаточно простой, либо представлена в некотором агрегированном виде. Последнее часто встречается в случае опубликования результатов предварительного опроса. Так как опрос не является голосованием, и от егорезультатов напрямую не зависит то, кто будет выбран победителем, то можнопредположить, что на опросе избиратели сообщают свои искренние предпочтения.Если речь идет об автоматическом принятии решений (компьютерными программами) или задачах ранжирования, то обработка информации, представленной полным профилем предпочтений уже не представляет большой трудности.
С другой стороны, в таких задачах время работы программ сводитсяк секундам, и даже здесь обработка всего профиля предпочтений не является эффективной. Кроме того, более трудоемким может быть именно получениеисчерпывающей информации обо всех участниках процесса принятия решений.Опросы в задачах такого рода также явление нечастое. Гораздо более реалистична ситуация, когда известны результаты прошлых голосований, которые имогут быть рассматриваемы как результаты опроса.В математической модели результат опроса представлен с помощью функциипубличной информации (ФПИ) , введенной в [11].
Это может быть, например,список победителей опроса, ранжирование кандидатов и др.В Главе 1 описаны основные результаты работы [11]: какие правила и прикаких ФПИ подвержены маниулированию или защищены от него. Однако, каки в случае с полной информацией, правила подвержены манипулированию вразной степени. Задача, решаемая в данной главе – сравнить степень манипулируемости правил при различных ФПИ.Рассматриваются шесть правил коллективного выбора и восемь типов ФПИ,отличающихся по информативности. Чтобы сравнить манипулируемость пра54вил, вычисляется вероятность того, что хотя бы один избиратель имеет стимул манипулировать при ФПИ (назовем эту вероятность первым индексом).Основной вопрос, на который необходимо ответить в рамках данной главы –как влияет неполнота информации на степень манипулируемости? Можно лиутверждать, что правила голосования в меньшей степени подвержены маниулированию, если применяется менее информативная ФПИ?В работе показано, при каких условиях вероятность возниконовения возможности манипулирования при неполной информации не отличается от случаяполной информации, и как информативность ФПИ влияет на эту вероятностьдля различных правил.
На основе теоретических исследований и вычислительных экспериментов сделан вывод о том, что применение первого индекса в случае неполной информации не дает представления о реальной манипулируемости правил. По этой причине предлагаются к рассмотрению два других индекса: вероятность успеха манипулирования и агрегированный индекс стимула кманипулированию. Теоретические доказательства и вычислительные эксперименты показывают, что данные два индекса являются более показательными,чем первый.2.22.2.1Математическая модельОпределения и обозначенияГруппе из избирателей, = {1, ..., }, требуется принять решение о выборе альтернатив (кандидатов) из множества , состоящего из элементов.Предпочтения избирателя относительно альтернатив заданы в виде линейного порядка ∈ (). В данной главе также используются определения иобозначения, данные ранее (см.
разделы 1.2.1, 1.2.3).55Верхним срезом альтернативы в предпочтениях называется множество = { ∈ : }. Аналогично, нижний срез альтернативы в предпочтениях определяется как = { ∈ : }.⃗ по множеству ⊆ называется профиль ⃗ / =Сужением профиля (1 /, ..., /), где / = ∩ ( × ). Анонимный профиль предпочтений⃗ показывает, сколько в профиле ⃗ содержится предпочтений каждого из !типов: ⃗ = (1 , ..., ! ), где ℎ – количество избирателей, имеющих предпочтения типа ℎ.⃗) =Вектор распределения позиций для альтернативы – вектор (, (1 (, ⃗ ), ..., (, ⃗ )), где (, ⃗ ) обозначает количество избирателей, у которых стоит на -ом месте в предпочтениях.Обозначим через мажоритарное отношение.
Говорят, что альтернатива доминирует альтернативу по мажоритарному отношению, , если (⃗ ) > (⃗ ) .2.2.2Множественный выборТак как результат правила коллективного выбора может состоять из нескольких альтернатив, то методы сравнения подмножеств альтернатив также необходимо включить в модель. Предпочтения избирателя на множестве непустыхподмножеств альтернатив называются расширенными предпочтениями и обозначаются за : означает, что множество более предпочтительнодля избирателя , чем множество . Существует много способов расширитьпредпочтения избирателя на множество подмножеств альтернатив [57].
В данной работе рассматриваются два лексикографических метода расширения предпочтений: Leximin и Leximax [58].56Leximin. Пронумеруем элементы обоих сравниваемых множеств и повозрастанию их предпочтительности для избирателя : = {1 , ..., || }, ∀ ∈{1, ..., || − 1}, +1 и = {1 , ..., | | }, ∀ ∈ {1, ..., | | − 1}, +1 .
Далеесравниваем и по следующему алгоритму:1. Если ∃ℎ ∈ {1, ..., (||, | |)}, т.ч. ∀ ∈ {1, ..., ℎ − 1} = и ℎ ℎ , то .2. Если ∀ ∈ {1, ..., (||, | |)} = , то , если ⊂ , и ,если ⊂ .Leximax. Пронумеруем элементы обоих сравниваемых множеств по убываниюих предпочтительности для избирателя : = {1 , ..., || }, ∀ ∈ {1, ..., ||−1}, +1 и = {1 , ..., | | }, ∀ ∈ {1, ..., | | − 1}, +1 . Аналогично,1. Если ∃ℎ ∈ {1, ..., (||, | |)}, т.ч. ∀ ∈ {1, ..., ℎ − 1} = и ℎ ℎ , то .2.
Если ∀ ∈ {1, ..., (||, | |)} = , то , если ⊂ , и ,если ⊂ .Пример 2.1. Если имеется три альтернативы, {, , }, и предпочтения избирателя , то расширенные предпочтения по методу Leximin имеют вид{} {, } {} {, } {, , } {, } {},по методу Leximax{} {, } {, , } {, } {} {, } {}.Существует другой метод работы с множественным выбором: в случае, еслирезультат состоит из нескольких альтернатив, выбрать только одну из них понекоторому правилу. Мы рассмотрим алфавитное правило устранения множе-ственности выбора : 2 ∖ {∅} → : предположим заранее заданным некото57рый линейный порядок на , ..., и из данного множества альтернативвыбираем ту, которая доминирует по все остальные альтернативы в множестве.
Алфавитное правило также можно описать в терминах расширенныхпредпочтений. Сравниваются два подмножества ⊆ и ⊆ . Пусть обозначает расширенное отношение безразличия. Пусть альтернатива 1 ∈ т.ч. ∀ ∈ ∖ {1 } 1 , и 1 ∈ такова, что ∀ ∈ ∖ {1 } 1 .
Если1 1 , то . Если 1 = 1 , то .2.2.3Функция публичной информации и манипулированиеМы используем математическую модель манипулирования при неполной информации, предложенную в [11]. Предположим, что перед выборами проводится опрос всех избирателей, на котором они сообщают свои искренние предпочтения. Если избирателям становится известен весь профиль предпочтений⃗ , то рассматривается случай с полной информацией. Пусть поизбирателей, ⃗ становится публичной, а некотораякаким-то причинам не вся информация о ⃗ ). Расее часть, определяемая функцией публичной информации (ФПИ) (смотрим следующие типы ФПИ:⃗ ) = ⃗ .1. Профиль предпочтений (ФПИ-Profile): (⃗)2. Анонимный профиль предпочтений (ФПИ-Ballot): (=⃗(⃗ )==⃗ (⃗ )=(1 , ..., ! ).⃗)3.
Вектор распределения позиций (ФПИ-Positions): (((1 , ⃗ ), ..., ( , ⃗ )).4. Количество очков, набранных кандидатами согласно функции (ФПИ-⃗ ) = (⃗ ⃗ ) = ((1 , ⃗ ), ..., ( , ⃗ )).Score): (⃗ ) = (⃗ ).5. Ранжирование кандидатов согласно функции (ФПИ-Rank): (58⃗ ) = (⃗ ).6. Победители по правилу (ФПИ-Winner): (7. Единственный победитель выбираемый по алфавитному правилу в случае⃗ ) = ( (⃗ )).множественного выбора (ФПИ-1Winner): (⃗)8. Взвешенный граф мажоритарного отношения (ФПИ-WMG): (= (⃗ ).⃗ ) = (⃗ ).9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
