Автореферат (1137312), страница 3
Текст из файла (страница 3)
Авторы предлагают такую интерпретаци неполной информации: пусть перед голосованием проводится опрос избирателей, на котором они сообщают~P. Затем избирателям сообщаются результатыопроса, представленные в некотором агрегированном виде, π(~P). Рассматривается 8 видов функции публичной информации π (ФПИ) и приводятсясвои искренние предпочтения,результаты о том, какие правила и при каких ФПИ подвержены манипулированию.Следующий шаг в рассмотрении вопроса о манипулируемости – оценкавероятности манипулирования для различных правил.
Этой теме посвященраздел 1.3. Подход, при котором степень манипулируемости правила рассматривается как вероятность возникновения такой ситуации, в которой хотя быодному избирателю будет выгодно исказить свои предпочтения при данномправиле, разрабатывался в работах Д.Келли, Ф.Т.Алескерова, Э.Курбанова,Д.С.Карабекяна, Д.Лепеллье, А.Слинько, Д.Притчарда, М.Уилсона и др.Расчет такого индекса напрямую зависит от выбранной в исследовании вероятностной модели, определяющей множество элементарных исходов. Наиболее часто используемые в литературе вероятностные модели – модельнезависимых предпочтений (Impartial Culture Model – модель IC) описанная Г.Т.Гильбо в 1952 г. и модель независимых анонимных предпочтений(Impartial Anonymous Culture Model – модель IAC) (К.Куга и Х.Нагатани,1974 г.). Важное теоретическое значение имеет также модель независимыханонимных и нейтральных предпочтений, предложенная сравнительно недавно О.Эгеджиолу и А.Гиритлигиль (2013 г.).Раздел 1.4 посвящен вычислительным аспектам манипулирования.Так, правила голосования, для манипулирования которых существует полиномиальный алгоритм поиска стратегии, стали считать легко манипулируемыми.
А те правила, где поиск манипулирующей стратегии принадлежитклассу NP-полных задач – трудно манипулируемыми. Дальнейшее развитиеэтого направления заключалось в определении класса сложности для правилголосования при различной постановке задачи манипулирования: индивидуальное или коалиционное манипулирование, конструктивное или деструктивное и т.д. Оказалось, что эти условия существенно влияют на оценку слож-10ности. Поэтому часто добавление того или иного условия требует решенияотдельной задачи.Определения всех упомянутых в диссертации правил коллективноговыбора приведены в Приложении А.Вторая главапосвященаисследованиюстепениманипулируемостиправил коллективного выбора при неполной информации. Раздел 2.1 – введение ко второй главе, где дана общая мотивация исследования и постановказадачи.
Основная предпосылка, которая используется в описанных в предыдущем разделе работах – наличие у каждого избирателя полной информацииоб истинных предпочтениях всех остальных участников голосования. Поэтому в каждой конкретной ситуации манипулирующий избиратель может точнорассчитать результат манипулирования, предполагая, что голоса остальныхостанутся искренними и неизменными. Если по каким-то причинам не вся информация становится доступна избирателю, то результат манипулированияне всегда возможно посчитать точно.В разделе 2.2 вводятся определения и обозначения математической модели, дается описание правил и методов расширения предпочтений.
Группе изnизбирателей,N = {1, ..., n},требуется принять решение о выборе альтерна-тив (кандидатов) из множестваизбирателяPi ∈ L(A),iгдеотносительно альтернатив заданы в виде линейного порядкаL(A)- множество всех линейных порядков наозначает, что альтернативаальтернативаA, состоящего из m элементов. Предпочтенияb.aA.ЗаписьaPi bi,чемболее предпочтительна для избирателяПрофилем предпочтений называется упорядоченный набор~P = (P1 , ..., Pn ) ∈ L(A)N .
~P−i – профиль предпочтений всех избирателей, кроме i-го, т.е. (P1 , ..., Pi−1 , Pi+1 , ..., Pn ).Расширенными предпочтениями избирателя i называется упорядочение на множестве подмножеств альтенатив, которое обозначается через EPi .Множество X ⊆ A лучше, чем мноежство Y ⊆ A для i, если X EPi Y . Множестваодинаковы по предпочтительности, если X EIi Y .
В работе рассматриваютсяиз предпочтенийnизбирателей,два метода расширения предпочтений, Leximin и Leximax, а также алфавитное правило устранения множественности выбора (определения и примерыданы в разделе 2.2.2)Функция общественного благосостоянияF:L(A)N→ W (A),гдеW (A)Fранжирует альтернативы,– множество всех слабых порядков наA.Пра-вило коллективного выбора определяет множество победителей голосования,CF : L(A)N → 2A ∖ {0}/ , CF (~P) = {a ∈ A : ¬∃b s.t.
bPa}.Под процедурами агре-гирования понимаются как функции общественного благосостояния, так иправила коллективного выбора.11Пусть перед голосованием проводится опрос избирателей, на которомони сообщают свои искренние предпочтения,~P.Затем избирателям сообща-ются результаты опроса, представленные в некотором агрегированном виде,π(~P).Функцияназывается функцией публичной информации (ФПИ). Рас-πсмотрены следующие виды ФПИ:1. Профиль предпочтений (ФПИ-Profile):2. Анонимныйпрофиль(n1 , ..., nm! ), где nhпа h.3. Векторпредпочтенийπ(~P) = ~P.(ФПИ-Ballot):π(~P) = ~p(~P) =– количество избирателей, имеющих предпочтения ти-распределенияпозиций(v(a1 , ~P), ..., v(am , ~P)), где v j (a, ~P)которых a стоит на j -ом месте вπ(~P) = ~v(~P) =(ФПИ-Positions):обозначает количество избирателей, упредпочтениях.4.
Количество очков, набранных кандидатами согласно функцииScore):F(ФПИ-π(~P) = ~S(~P) = (S(a1 , ~P), ..., S(am , ~P)).F5. Ранжирование кандидатов согласно функции(ФПИ-Rank):π(~P) =F(~P).6. Победители по правилуCF(ФПИ-Winner):π(~P) = CF (~P).7. Матрица взвешенного графа мажоритарного отношения (ФПИ-WMG):π(~P) = W MG(~P),гдеW MG(~P)kl = |{i ∈ N : ak Pi al }|.8. Матрица графа мажоритарного отношения (MG):1,π(~P) = MG(~P),гдеW MG(~P)kl > W MG(~P)lk ,MG(~P)kl = −1, если W MG(~P)lk > W MG(~P)kl ,0,иначе.еслиТаким образом, обладая информациейπ(~P)и зная свои собственные предпочтения, избирательо профиле предпочтенийiимеет множество согла-сующихся с этой информацией профилей предпочтений – информационноемножествоπ(~P)Wi.π(~P)Wi′′ ) = π(~= {~P−i∈ L(A)N∖{i} : π(Pi , P~−iP)}.Пусть даны две ФПИπ(~P)Wiπ ′ (~P)⊆ Wi, тоππиπ ′.Если∀~P ∈ L(A)Nи∀i ∈ Nявляется не менее информативной, чем12π ′.выполненоВ случае с неполной информацией избиратель не знает, какой из профилей его информационного множества реализовался в действительности.Поэтому предполагается, что избиратель имеет стимул манипулировать, еслипри некоторой его стратегии результат во всех профилях информационногомножества не станет для него хуже, и существуют профили, где результатстанет лучше.CF и профиль ~P.
Избиратель i имеетei ∈π , если существуют предпочтения PОпределение 2.1. Дана правилостимул к манипулированию при ФПИL(X) такие, что′ ∈ W π(~P) C (P′ ) EP C (~а) ∀~P−iP−iF ei , ~i F P)′ ) EI C (~ei , ~P−iCF (Pi F P);′ ) EP C (~ei , ~P−iCF (Pi F P).Определение 2.2. Правило CF называется подверженным манипулированию при ФПИ π , если ∃i ∈ N и ∃~P ∈ L(A)N , в котором i имеет стимул кманипулированию при ФПИ π .i′ ∈ W π(~P) такой, чтоб) ∃~P−iiилиВ разделе 2.3 подробно рассматривается понятие вычислимости исильной вычислимости правил из ФПИ, а также строится отношение „быть неменее информативным“ на множестве рассматриваемых ФПИ отдельно длякаждого правила коллективного выбора.Определение 2.3.
Если существует функция(композиция функцийHиется вычислимым из ФПИПо определению,πCFπ ),π.Hто правило коллективноговычислимо из ФПИCF = H ∘ πвыбора CF называ-такая, чтоπтогда и только тогда, когдаπ(~P)достаточно, чтобы избира-не менее информативна, чем ФПИ-Winner.Определение 2.4. Если информациительiмог вычислить результат правила при всех возможных вариантах го-лосования этим избирателем,лимым из ФПИei ∈ L(A), то правило называется сильно вычисPπ.В разделе 2.4 представлены результаты теоретического и экспериментального исследования первого индекса манипулируемости –доля профилей предпочтений дляI1 (CF , π, m, n)–n избирателей и m альтернатив, в которыхесть избиратель, имеющий стимул к манипулированию при данном правилеCFи ФПИπ.Основной вопрос исследования: как влияет наличие неполнойинформации на манипулируемость? Следующая теорема показывает, при каком условии вероятность манипулирования не изменяется по сравнению сослучаем полной информации.Теорема 2.4.1.
Если правилоCFсильно вычислимо из ФПИπ,тоI1 (CF , π, m, n) = I1 (CF , Pro f ile, m, n).Рассмотрим случай наименее информативной ФПИ: избирателям доступна информация только о победителях голосования (т.е. ФПИ-Winner или13ФПИ-1Winner, если используется правило устранения множественности выбора). Теорема 2.4.2 показывает, как ведет себя индекс манипулируемости I1для правила относительного большинства при стремящемся к бесконечностичисле избирателей.
С точки зрения практики этот случай также интересен:информацию в виде списка победителей опроса достаточно просто представить избирателям.Теоремаlimn→∞ I1 (Plurality,Winner, m, n) = 1 при методахlimn→∞ I1 (Plurality, 1Winner, m, n) = 1 при алфавитном2.4.2.а)Leximin и Leximax; б)правиле устранения несравнимости.Таким образом, не всегда уменьшение информативности ведет к снижению манипулируемости. Кроме того, приведем пример, когда манипулирование возможно в 100% профилей предпочтений.Теорема 2.4.3. При методе Leximin I1 (Borda, MG, 3, 3)= 1.Наконец, приведем результат о защищенности от манипулированиядля правила Коупленда при ФПИ-Winner.Теорема 2.4.4.
При методе Leximax,I1 (Copeland,Winner, 3, n) = 0длянечетного числа избирателей.Вторая часть раздела 2.4 посвящена результатам экспериментов. Комплекс программ для вычисления индекса был написан в среде MATLAB, исходные коды его элементов приведены в Приложении B. Рассматривалисьметоды расширения предпочтений, Leximin и Leximax, а также случай с применением алфавитного правила устранения множественности выбора, числоальтернатив – 3, число избирателей – от 3 до 15. Пример графика, иллюстрирующего результаты вычислений, представлен на рисунке 1, где по осиабсцисс располагается количество избирателей,n,а по оси ординат – значе-ния I1 (F , π, 3, n).1ProfileRankWinner1Winner0.90.80.70.60.50.40.30.20.1246810121416Рисунок 1. Значения I1 (CF , π, 3, n) для правила относительного большинства приалфавитном правиле устранения несравнимости.14Результаты вычислительных экспериментов∙Манипулируемость не уменьшается, когда мы рассматриваем менее информативные ФПИ.∙Для правила относительного большинства и правила Борда максимальные значения I1 соответствуют ФПИ1Winner,наименее информативнойФПИ, из которой правила вычислимы.∙ I1 (CF , 1Winner, 3, n) очень быстро стремится к 1 с ростом числа избирателей для правила относительного большинства и правила Борда.∙Манипулируемость слабо возрастает с уменьшением информативностиФПИ (на последовательности ФПИ от Profile до Rank) для правила Коупленда.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
