Степень манипулируемости процедур агрегирования тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Веселова Юлия Александровна

• Веселова Юлия Александровна
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Веселова Юлия Александровна

Введение

1 Степень манипулируемости: основные понятия, постановка задачи и обзор проблемы

1.1 Проблема манипулирования

1.2 Манипулирование со стороны избирателей

1.2.1 Модель коллективного выбора

1.2.2 Теоремы типа Гиббарда-Саттертуэйта

1.2.3 Манипулирование при неполной информации

1.3 Оценка степени манипулируемости правил коллективного выбора

1.3.1 Вероятностные модели

1.3.2 Вероятность манипулирования в различных моделях

1.4 Вычислительная сложность манипулирования

1.4.1 Конструктивное манипулирование без весов

1.4.2 Голосование с назначением весов и ограничением на множество кандидатов

1.4.3 Деструктивное манипулирование

1.4.4 Манипулирование с неполной информацией

1.5 Заключение по Главе

2 Манипулирование в условиях неполной информации

2.1 Введение

2.2 Математическая модель

2.2.1 Определения и обозначения

2.2.2 Множественный выбор

2.2.3 Функция публичной информации и манипулирование

2.2.4 Функции общественного благосостояния

2.3 Вычислимость и сильная вычислимость

2.4 Вероятность манипулирования

2.4.1 Теоретические результаты

2.4.2 Вычислительные эксперименты

2.5 Успех манипулирования и стимул к манипулированию

2.5.1 Вычислительные эксперименты

2.6 Комплекс программ

2.6.1 Общее описание

2.6.2 Ввод условий задачи и представление результатов

2.7 Заключение по Главе

3 Вероятностные модели: 1С, IAC, IANC

3.1 Введение

3.2 Определения и теоретическая основа

3.2.1 Вероятностные модели

3.2.2 Индексы манипулируемости

3.3 Оценка расстояния между моделями 1С и IANC

3.3.1 Максимальные и минимальные АН-классы

3.3.2 Оценка максимальной разности для малых значений т

3.3.3 Сравнение моделей 1С, IAC, IANC в асимптотике

3.4 Степень манипулируемости правил коллективного выбора в моделях 1С и IANC

3.5 Заключение по Главе

Заключение

Литература

А Правила коллективного выбора

В Исходные коды разработанного программного комплекса

В.1 Вычисление индекса вероятности манипулирования: основная программа

В.2 Вычисление индексов успеха манипулирования и стимула к манипулированию: основная программа

В.З Программы для реализации методов расширения предпочтений

В.3.1 Метод Leximin

В.3.2Метод Leximax

В.З.ЗАлфавитное правило устранения множественности выбора

В.4 Программы расчета правил коллективного выбора

В.4.1 Правило относительного большинства

В.4.2Двухступенчатая мажоритарная система

В.4.3Правило передачи голосов

В.4.4Правило Коупленда

В.5 Вспомогательные программы

В.5.1Программа построения сужения профиля по множеству .... 180 В.5.2Программа построения простого и взвешенного графа мажоритарного отношения

В.б.ЗПрограмма устранения множественности выбора по алфавитному правилу

Введение диссертации (часть автореферата) на тему «Степень манипулируемости процедур агрегирования»

Введение

В теории коллективного выбора известна проблема подверженности правил принятия коллективных решений манипулированию со стороны избирателей: участники голосования могут намеренно сообщить свои неискренние предпочтения с целью добиться более выгодного для них результата. Если правило коллективного выбора допускает возможность манипулирования хотя бы для одного избирателя и хотя бы в одной из множества возможных ситуаций (под ситуацией понимается распределение предпочтений среди всех избирателей, т.е. профиль предпочтений), то правило называется манипулируемым.

Манипулируемость правила коллективного выбора считается отрицательным свойством, так как избиратель, манипулируя, отклоняет результат голосования от «истинного» коллективного выбора в свою пользу. Кроме того, если имеется несколько независимо манипулирующих избирателей, то результат может оказаться для них даже хуже первоначального. В то же время, избежать манипулирования полностью можно, исключив или сильно ограничив возможности у избирателей влиять на результат. Так, примерами неманипулируемых процедур могут служить диктаторское правило или правило случайного выбора альтернативы. Однако вряд ли коллектив устроят такие правила принятия решений.

Первый теоретический результат, с которого началось изучение манипулиру-емости правил голосования с помощью математического моделирования, был

получен независимо в [1,2] и носит название теоремы Гиббарда-Саттертуэйта. Эта теорема утверждает, что любое недиктаторское правило коллективного выбора, результат которого - единственная альтернатива, является манипулируем ым. если имеется хотя бы три возможных исхода. Поэтому возможность манипулирования имеет смысл не исключить, а затруднить или ограничить, и возникает необходимость сравнивать степень манипулируемости разных правил.

В [3-6] степень манипулируемости правила рассматривается как вероятность возникновения такой ситуации, в которой хотя бы одному избирателю будет выгодно исказить свои предпочтения при данном правиле. Расчет такого индекса напрямую зависит от выбранной в исследовании вероятностной модели, определяющей множество элементарных исходов. Наиболее часто используемые в литературе вероятностные модели - модель независимых предпочтений (Impartial Culture Model - модель 1С) [7] и модель независимых анонимных предпочтений (Impartial Anonymous Culture Model - модель IAC) [8]. Важное теоретическое значение имеет также модель независимых анонимных и нейтральных предпочтений, предложенная сравнительно недавно в [9].

Базовая предпосылка большинства исследований - наличие полной информации у каждого из участников голосования о предпочтениях всех остальных избирателей. В [10] и [11] рассмотрена задача манипулирования при неполной информации: избирателям не доступна информация о предпочтениях всех остальных участников голосования, но известны результаты опроса всех избирателей, представленные в некотором агрегированном виде.

Другой подход, впервые рассмотренный в [12], предлагает сравнивать трудоемкость поиска стратегии манипулирования при помощи теории вычислительной сложности. Если для правила выбора существует полиномиальный алго-

ритм поиска стратегии манипулирования, то она считается легко манипулиру-емой, а если поиск такой стратегии принадлежит классу ХР-полных задач -трудно манипулируемой.

Актуальность темы. Вопрос «при каких условиях участники смогут изменить результат голосования, намеренно заявляя процедуре свои неискренние предпочтения?» является ключевым при задании правила выбора на аукционах, голосованиях в больших и малых группах. В связи с интенсивным развитием компьютерных и интернет-технологий область применения задач теории выбора постоянно расширяется. Агрегирование множества индивидуальных предпочтений в том или ином виде возникает в задачах автоматического управления, ранжирования, взаимодействия автономных агентов и др. Процедуры принятия коллективных решений различаются по своим свойствам, что делает их в разной степени применимыми в различных приложениях. Поэтому существует необходимость теоретического и экспериментального исследования процедур с точки зрения соответствия их заданным критериям.

В обоих описанных выше подходах для изучения манипулирования требуется построение математической модели ситуации манипулирования, и результаты исследования во многом зависят от постановки задачи и сделанных предпосылок. В связи с этим актуальными задачами исследования являются:

1) Приближение математической модели к реальным ситуациям принятия коллективных решений и получение новой информации о свойствах применяемых на практике процедур. В рамках этой задачи представляет интерес получение значений степени манипулируемости при неполной информации.

2) Определение того, как зависит степень манипулируемости от сделанных предпосылок, в частности, от типа публичной информации и используемой вероятностной модели.

Целью данной работы является исследование степени манипулируемости процедур агрегирования в условиях неполной информации, а также в различных вероятностных моделях.

Для достижения поставленной цели были решены следующие задачи:

1. Сделан обзор литературы по методам оценки степени манипулируемости процедур агрегирования: теоретическим результатам, вычислению вероятности манипулирования и вычислительной сложности манипулирования результатом голосования.

2. Сформулирована задача определения вероятности индивидуального манипулирования при неполной информации. Показано, при каких условиях вероятности манипулирования при полной и неполной информации равны.

3. Показано, что вероятность манипулирования нельзя рассматривать как основной индекс манипулируемости в случае неполной информации. Для этого случая предложены к рассмотрению индекс успеха манипулирования и индекс стимула к манипулированию.

4. Проведено теоретическое исследование предложенных индексов для различных функций публичной информации, исследовано асимптотическое поведение индексов для правила относительного большинства.

5. Разработан комплекс программ для точного вычисления индексов манипулируемости и проведена серия вычислительных экспериментов для 6 правил коллективного выбора, 8 типов функции публичной информации и 3 методов расширения предпочтений.

6. Проведено сравнение вероятностных моделей, используемых для статистического анализа свойств правил коллективного принятия решений. Исследована максимальная разность вероятностных показателей в моделях 1С,

I АС и IAN С. Вычислены индексы манипул ируемости для четырех правил в модели IANC для числа избирателей от 3 до 30.

Научная новизна:

1. Впервые получены теоретические результаты о вероятности манипулирования в случае, когда избирателям доступна не вся информация о предпочтениях других участников голосования.

2. Предложены к рассмотрению новые индексы манипулируемости для случая с неполной информацией.

3. Впервые исследовано влияние степени информативности функции публичной информации на манипулируемость правил.

4. Получены новые данные о том, при каких типах публичной информации и для каких правил степень манипулируемости равна или почти равна нулю.

5. Впервые рассмотрена задача определения максимально возможной разности индексов в вероятностных моделях.

6. Впервые получены оценки максимальной разности вероятностей в таких часто используемых моделях, как 1С и IAC, а также IAC и IANC, 1С и IANC.

7. Впервые получены значения вероятности манипулирования в модели IANC.

Теоретическая значимость. В диссертационной работе впервые исследована степень манипулируемости в случае неполной информации, предложены три индекса манипулируемости, показано, почему индекс вероятности манипулирования нельзя рассматривать как основной. Изучено влияние степени неполноты информации на манипулируемость. Показано, что несмотря на то, что правила в подавляющем большинстве случаев подвержены манипулированию

и вероятность манипулирования растет, эффект от манипулирования уменьшается с уменьшением информативности функции публичной информации.

При статистическом анализе свойств правил коллективного выбора необходимо сначала определить вероятностную модель, в разных исследованиях используются различные модели. Однако вопрос, насколько могут отличаться индексы, вычисленные в различных моделях, ранее не рассматривался. Данное диссертационное исследование также впервые дает ответ на этот вопрос для наиболее популярных вероятностных моделей. Кроме того, проводится сравнение известных моделей с новой моделью, построенной на основе аксиом анонимности и нейтральности. Исследование последней также имеет теоретическую значимость, так как аксиомы анонимности и нейтральности являются основными в теории коллективного выбора.

Практическая значимость. Важность результатов анализа манипулируе-мости правил заключается в том, что в нем впервые использована предпосылка о наличии неполной информации у избирателей о предпочтениях остальных участников. Показано, при каких типах публичной информации правила подвержены манипулированию в малой степени и в каких случаях защищены от манипулирования. Эти результаты могут быть использованы на практике для ответа на вопрос, какую информацию по результатам опроса можно предоставить избирателям, чтобы ограничить или исключить манипулирование.

Достоверность и обоснованность полученных результатов обеспечивается строгостью доказательств теорем и проверкой результатов вычислительных экспериментов.

Методы исследования. Методы современной прикладной алгебры, математической логики, теории вероятностей, теории выбора и принятия решений,

комбинаторики, метод статистических испытаний. В вычислительных экспериментах применялось компьютерноое моделирование.

Апробация работы. Основные результаты работы докладывались на:

1. Association of Southern European Economic Theorists 2011 Annual Meeting, Португалия, Эвора. Доклад на тему: «The difference of manipulability indexes in 1С and IANC model», 28 октября 2011.

2. 11th Meeting of the Society for Social Choice and Welfare (SCW 2012), Индия, Нью-Дели. Доклад на тему: «The difference of manipulability indexes in 1С and IANC model», 18 августа 2012.

3. Научный семинар «Экспертные оценки и анализ данных», ИПУ РАН, Россия, Москва. Доклад на тему: «Анонимность и нейтральность в моделировании предпочтений», 14 ноября 2012 г.

4. Международный симпозиум «Кластеры, ранжирования, деревья: методы и приложения», Россия, Москва. Доклад на тему: «The manipulability index in the IANC model», 12 декабря 2012 г.

5. Второй Российский экономический конгресс, Россия, Москва. Доклад на тему: «Сопоставление правила порогового агрегирования и ранговых процедур», 21 февраля 2013 г.

6. XIV Апрельская международная научная конференция «Модернизация экономики и общества», Россия, Москва. Доклад на тему: «Сравнение порядковых правил коллективного выбора», 5 апреля 2013 г.

7. XXVI EURO - INFORMS 26th European Conference on Operational Research, Италия, Рим. Доклад на тему: «Noncompensatory scoring rules and threshold aggregation», 3 июля 2013 г.

8. XV Апрельская международная научная конференция «Модернизация экономики и общества», Россия, Москва. Доклад на тему: «Моделирование коллективных предпочтений: 1С, IAC и IANC», 3 апреля 2014 г.

9. 12th Meeting of the Society for Social Choice and Welfare (SCW 2014), США, Бостон. Доклад на тему: «Сравнение вероятностных моделей: 1С, IAC и IANC», 20 июня 2014.

10. Конференция Теория активных систем-2014 (ТАС-2014), Россия, Москва. Доклад на тему: «Вычислительная сложность манипулирования: обзор проблемы», 18 ноября 2014 г.

И. Конференция «Фундаментальная информатика, информационные технологии и системы управления: реалии и перспективы (FIITM-2014)», Россия, Красноярск. Доклад на тему: «Вычислительная сложность манипулирования результатом голосования», 26 ноября 2014 г.

12. XVI Апрельская международная научная конференция «Модернизация экономики и общества», Россия, Москва. Доклад на тему: «Вычислительная сложность правил коллективного выбора и манипулирования», 9 апреля 2015 г.

13. XVII Апрельская международная научная конференция «Модернизация экономики и общества», Россия, Москва. Доклад на тему: «Манипулирование при неполной информации», 20 апреля 2016 г.

14. Научный семинар «Экспертные оценки и анализ данных», ИПУ РАН, Россия, Москва. Доклад на тему: «Манипулирование при неполной информации», 25 мая 2016 г.

15. Семинар «Математическая экономика» ЦЭМИ РАН, Россия, Москва. Доклад на тему: «Манипулирование при неполной информации», 28 февраля 2017 г.

16. XVIII Апрельская международная научная конференция «Модернизация экономики и общества», НИУ ВШЭ, Россия, Москва. Доклад на тему: «Коалиционное манипулирование при неполной информации», 12 апреля 2017 р

17. Computational Social Choice Seminar, Institute of Logic, Language and Computation of University of Amsterdam, Нидерланды, Амстердам. Доклад на тему: «Manipulation under Incomplète Information», 16 мая 2017 г.

Результаты исследования использовались в следующих проектах:

1. «Математическое моделирование и конструирование механизмов в социальной, экономической и политической сферах с использованием методов теории принятия решений, теории игр и интеллектуального анализа данных», МЛАВР НИУ ВШЭ, 2012 г.

2. «Исследование новых методов и подходов в области математического моделирования и дизайна механизмов в социальной, экономической и политической сферах», МЛАВР НИУ ВШЭ, 2013 г.

3. «Теоретическое и численное исследование современных математических моделей в социально-экономической, политической и финансовой сферах», МЛАВР НИУ ВШЭ, 2014 г.

4. «Анализ данных и принятие решений в социально-экономических и политических системах», МЛАВР НИУ ВШЭ, 2015 г.

5. «Разработка и исследование новых математических моделей в социально-экономической и политической сферах», МЛАВР НИУ ВШЭ, 2016 г.

Личный вклад. Все результаты получены автором лично.

Публикации. Основные результаты по теме диссертации изложены в 9 печатных изданиях, 3 из которых изданы в журналах, рекомендованных ВАК:

1. Veselova, Y. A. The difference between manipulability indices in the 1С and IANC models // Social Choice and Welfare. -2016. -Vol. 46. -No. 3. -P. 609638. - 1 п.л.

2. Веселова, Ю. А. Вычислительная сложность манипулирования: обзор проблемы // Автоматика и телемеханика. -2016. -Т. 77. 3. -С. 7-32. - 1,75 п.л.

3. Veselova, Y. A. The Manipulability Index in the IANC Model // Clusters, Orders, and Trees: Methods and Applications. Berlin : Springer, 2014. -Vol. 92. -P. 391-404. - 0,75 п.л. а также

4. Веселова, Ю. А. Манипулирование при неполной информации // XVII Апрельская международная научная конференция по проблемам развития экономики и общества: сб. науч. работ. -Кн. 1. -М. : Издательский дом НИУ ВШЭ, 2017. -С. 78-90. - 0,5 п.л.

5. Veselova, Y. A. Does Incomplete Information Reduce Manipulability? // NRU Higher School of Economics. Series EC «Economics». -2016. -No. 152/EC/2016. -1,2 п.л.

6. Веселова, Ю. А. Вычислительная сложность правил коллективного выбора и манипулирования // XVI Апрельская международная научная конференция по проблемам развития экономики и общества: сб. науч. работ. -Кн. 3. -М. : Издательский дом НИУ ВШЭ, 2016. -С. 79-88. - 0,5 п.л.

7. Веселова, Ю. А. Вычислительная сложность манипулирования в задаче голосования // Фундаментальная информатика, информационные техноло-

гии и системы управления: реалии и перспективы: сб. науч. работ. Красноярск : Сибирский федеральный университет, 2014. - 0,6 п.л.

8. Веселова, Ю. А. Сложность порядковых правил коллективного выбора // XIV Апрельская международная научная конференция по проблемам развития экономики и общества: сб. науч. работ. -Кн. 4. -М. : Издательский дом НИУ ВШЭ, 2014. -С. 431-438. - 0,3 п.л.

9. Veselova, Y. A. The difference between manipulability indexes in 1С and IANC models // NRU Higher School of Economics. Series EC «Economics». -2012. -No. 17 EC 2012. - 0,6 п.л.

Объем и структура работы. Диссертация состоит из введения, трех глав, заключения и двух приложений. Полный объем диссертации составляет 182 страницы с 26 рисунками и 3 таблицами. Список литературы содержит 69 наименований.

Глава 1

Степень манипулируемости: основные понятия, постановка задачи и обзор проблемы

1.1 Проблема манипулирования

Принятие коллективных решений - неотъемлемая часть жизни общества. Для агрегирования множества индивидуальных предпочтений применяются различные процедуры голосования. Однако у каждого метода есть свои недостатки. В частности, процедура может быть подвержена манипулированию со стороны избирателей, т.е. избиратели, действуя стратегически, могут добиться более выгодного для них результата голосования, намеренно исказив свои предпочтения.

Пример 1.1. Рассмотрим такой пример манипулирования: пусть два избирателя считают наилучшим кандидата а, еще два избирателя - кандидата Ь и один избиратель - кандидата с. Применяется процедура относительного большинства, и при таких предпочтениях выигрывают кандидаты ажЬ. Однако для последнего избирателя кандидат Ь лучше кандидата а (с на первом месте, Ь на

втором и а на третьем), и от голосует за кандидата Ь, а не за с, чтобы выиграл только кандидат Ь.

О том, что в некоторых процедурах голосования участникам выгоднее действовать стратегически и сообщать свои неискренние предпочтения, знали еще в древности. Кроме того, правила коллективного выбора подвержены и манипулированию со стороны организатора голосования. В этом случае различают намеренное изменение процедуры голосования и изменение множества участвующих в выборах кандидатов или избирателей (манипулирование повесткой дня), имеющие целью достижение более выгодного для организатора результата голосования.

Первый известный пример манипулирования при голосовании был описан в письмах Плиния Младшего [13, 14], где имело место манипулирование именно со стороны организатора посредством изменения и правила голосования, и множества представленных к рассмотрению альтернатив.

Конструирование такого правила выбора, которое даст заранее определенный (необходимый организатору) результат - задача дизайна механизмов (см., например, [15]). Изменение множества кандидатов или избирателей при неизменном правиле выбора - задача контроля голосования [16,17].

1.2 Манипулирование со стороны избирателей 1.2.1 Модель коллективного выбора

Введем необходимые для дальнейшего изложения определения и обозначения. Имеется множество п избирателей, N = {1, 2 ,...,п}, каждый из которых имеет предпочтения на множестве альтернатив Д имеющем мощность т. Альтернативы (кандидаты) будут обозначаться строчными буквами а, Ь, с, (1, х, у, х или а\,а2, а3, ...,ат.

Определение 1.1. Бинарное отношение Р является слабым порядком, если оно удовлетворяет следующим свойствам: 1) ацикличности: > 1 такого, что а\Ра2, а2Ра3, ..^а^Р^, а^Р^; 2) транзитивности: Уа, Ь,с Е Д аРЬ, ЬРс ^ аРс;

Определение 1.2. Бинарное отношение Р является линейным порядком, если оно явлется слабым порядком и удовлетворяет свойству связности: Уа, Ь Е А либо аРЬ, либо ЬРа.

Предпочтения каждого избирателя представлены в виде линейного порядка Р па множестве альтернатив. Это означает, что каждой альтернативе присвоено некоторое место от 1 до т (па первом месте - наилучшая алтернатива, на последнем - наихудшая), и нет альтернатив, стоящих на одном и том же месте в предпочтениях. Через Ь(А) обозначим множество всех линейных порядков на Д а через Pi Е Ь(А) - предпочтения избирателя г. Если аРф, это означает, что альтернатива а более предпочтительна, чем альтернатива Ь для избирателя г. Профилем предпочтений будем называть вектор Р, элементами которого являются предпочтения п избирателей, Р = (Р\, Р2,..., Рп). Эти предпочтения в дальнейшем будут также называться искренними предпочтениями. Ь(А)М - множество всех профилей предпочтений (для п избирателей и т альтернатив). Р— - профиль предпочтений всех избирателей кроме г-го, т.е. Р— = (Ръ Pг-Í, Pi+l, Рп)-

Принятие коллективного решения может заключаться в выборе некоторого подмножества альтернатив, «победителей», или упорядочении альтенатив. Любой алгоритм, позволяющий получить коллективное решение на основе множества индивидуальных предпочтений мы будем называть процедурой агрегирования. В данной работе будут обсуждаться следующие виды процедур агре-

гирования: функции общественного благосостояния и правила коллективного выбора.

Функция общественного благосостояния Р ранжирует альтернативы, при этом все альтернативы упорядочены, и на одном и том же месте могут располагаться две и более альтернативы (слабый порядок), Р : Ь(А)М ^ W(А), где ^ (А) ............. множество всех слабых порядков на А Результат функции Р представим в виде Р(Р) = Я = Ри/, где Р - отношение предпочтения, а / - отношение безразличия.

Правило коллективного выбора Ср : Ь(А)М ^ 2Л \ {0} на выходе дает непустое подмножество альтернатив, множество победителей голосования, занимающих первую строчку в ранжировании Р(Р) = Я, т.е. Ср(Р) = {а е А : -3 Ь .. ЬРа}.

Правило Ср (функция Р) называется диктаторским (-ой), если существует такой избиратель %*, что V Р е Ь(А)М Ср(Р) = {а е А : —3Ь .. ЬР.¿*а} (Р(Р) = Рг* )•

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

Р при правиле Ср, если такие, что Ср(1}г,Р-г)РгСр((Р)). В этом случае РР

Пример 1.2. Рассмотрим следующий профиль предпочтений

^ d d а^

Р =

с с Ъ abc \Ь a dj

Результат выбора по правилу Борда - альтернатива d. Для избирателей 1 и 2 эта альтернатива находится на первом месте, следовательно, они не имеют стимула манипулировать. Для избирателя 3 альтернатива d находится на последнем месте, и он имеет стимул манипулировать, заявляя неискренние предпочтения Р' = (с, a, b, d)7 так как в этом случае победителем голосования станет с. Искренние предпочтения избирателей представлены в профиле Р. В профиле (Р-3, Р') избиратели 1 и 2 имеют искренние предпочтения, а избиратель 3 -искаженные.

Определение 1.4. Если существует профиль предпочтений Р, в котором хотя бы один избиратель имеет стимул манипулировать при правиле Ср, то правило Ср называется манипулируемым. В противном случае правило защищено от манипулирования.

В данной модели предполагается, что каждый избиратель знает предочтения всех остальных и имеет возможность принимать решение о выборе стратегии, зная точно будущий результат своих действий, так как предпочтения остальных избирателей предполагаются неизменными.

1.2.2 Теоремы типа Гиббарда-Саттертуэйта

Манипулируемость правил естественно является нежелательным свойством процедур выбора, так как при искажении избирателями своих предпочтений

результат выбора «смещается» в сторону предпочтений манипулирующего избирателя и может отдаляться от предпочтений остальных. Возможна и такая ситуация: при одновременном независимом манипулировании несколькими избирателями коллективный выбор становится хуже для всех участников. Таким образом, возникают потери в смысле оптимальности коллективного выбора. По этой причине представляло большой интерес нахождение таких правил, которые исключают возможность для избирателей манипулировать.

Первый теоретический результат, с которого началось изучение манипулируе-мости правил голосования с помощью математического моделирования, был получен независимо в [1] и [2] и носит название теоремы Гиббарда-Саттертуэйта. В ней речь идет о частном случае правил коллективного выбора - однозначных правилах, результат которых всегда единственная альтернатива.

Теорема 1.2.1. [1,2] Любое однозначное правило коллективного выбора, если имеется хотя бы три возможных исхода, является либо манипулируемым, либо диктаторским.

Наличие трех возможных исходов является одной из необходимых предпосылок данной теоремы, так как выбор из двух альтернатив по правилу большинства очевидно является неманипулируемым. Другое необходимое условие - неограниченность области определения правила коллективного выбора, т.е. избиратели могут иметь любые предпочтения па множестве А. Большое количество исследований посвящено изучению того, как следует ограничить множество допустимых предпочтений избирателей, чтобы правило было защищено от манипулирования (см., например, [18,19]). В настоящей работе такие модели не рассматриваются.

Однако результат теоремы Гиббарда-Саттертуэйта не означает, что все разумные процедуры при выполнении названных условий подвержены манипули-

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

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

Определение 1.5. Пусть профили Р и Р' таковы, что У € N Уа ,Ь € А если аРф, то т(а)Р'т(&), где т - перестановка па множестве А Функция Р (правило Ср} удовлетворяет свойству нейтралъности, если т(Р(Р)) = Р(Р').

Нейтральность означает, что процедура обрабатывает все альтернативы одинаково и исключает дискриминацию каких-либо альтернатив.

Список литературы диссертационного исследования кандидат наук Веселова Юлия Александровна, 2018 год

Литература

1. Gibbard A. Manipulation of voting schemes: a general result / A. Gibbard // Econometrica: journal of the Econometric Society. - 1973. - Vol. 41. - No. 4. -P. 587-601.

2. Satterthwaite, M.A. Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions / M.A. Satterthwaite // Journal of economic theory. - 1975. - Vol. 10. - No. 2. -P. 187-217.

3. Алескеров Ф.Т., Курбанов Э. О степени манипулируемости правил коллективного выбора //Автоматика и телемеханика. - 1998. - №. 10. - С. 134-146.

4. Алескеров, Ф.Т. Оценка степени манипулируемости известных схем агрегирования в условиях множественного выбора / Ф.Т. Алескеров, Д.С. Кара-бекян, P.M. Санвер, В.И. Якуба // Журнал новой экономической ассоциации. - 2009. - №. 1-2. - С. 37-61.

5. Aleskerov, F. On the Degree of Manipulability of Multi-Valued Social Choice Rules / F. Aleskerov, D. Karabekyan, R.M. Sanver, V. Yakuba // Homo Oeconomicus. - 2011. - Vol. 28. - No. 1/2. - P. 205-216.

6. Pritchard, G. Exact results on manipulability of positional voting rules / G. Pritchard, M.C. Wilson //Social Choice and Welfare. - 2007. - Vol. 29. - No. 3. - P. 487-513.

7. Guilbaud, G.T. Les théories de l'intérêt général et le problème logique de l'agrégation / G.T. Guilbaud // Revue économique. - 2012. - Vol. 63. - No. 4. - P. 659-720.

8. Kuga, K. Voter antagonism and the paradox of voting / К. Kuga, H. Nagatani // Econometrica: Journal of the Econometric Society. - 1974. - Vol. 42. - No. 6. - P. 1045-1067.

9. Egecioglu, O. The Impartial, Anonymous, and Neutral Culture Model: A Probability Model for Sampling Public Preference Structures / O. Egecioglu, A.E. Giritligil // The Journal of Mathematical Sociology. - 2013. - Vol. 37. -No. 4. - P. 203-222.

10. Conitzer, V. Dominating Manipulations in Voting with Partial Information / V. Conitzer, T. Walsh, L. Xia // Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligent - 2011. - Vol. 11. - P. 638-643.

11. Reijngoud, A. Voter response to iterated poll information / A. Reijngoud, U. Endriss // Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems. - 2012. - Vol. 2. - P. 635-644.

12. Bartholdi, J.J. The computational difficulty of manipulating an election / J.J. Bartholdi, C. A. Tovey, M.A. Trick // Social Choice and Welfare. - 1989. - Vol. 6. - No. 3. - P. 227-241.

13. Плиний Младший. Письма Плиния Младшего / Книги 1-Х. Сер. Литературные памятники. - М.: Наука, 1983. - 407 с.

14. Алескеров, Ф.Т. Выборы. Голосование. Партии / Ф.Т. Алескеров, П. Орте-шук. - М.: Академия, 1995. - 208 с.

15. Maskin, Е. Implementation theory / Е. Maskin, T. Sjôstrôm // Handbook of social Choice and Welfare. - 2002. - Vol. 1. - P. 237-288.

16. Bartholdi, J.J. How hard is it to control an election? / J.J. Bartholdi, C.A. Tovey, M.A. Trick //Mathematical and Computer Modelling. - 1992. - Vol. 16. - No. 8-9. - P. 27-40.

17. Faliszewski, P. A richer understanding of the complexity of election systems / P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, J. Rothe // Fundamental problems in computing: Essays in honor of Professor Daniel J. Rosenkrantz. — 2009. - P. 375-406.

18. Blin, J.M. Strategy-proofness and single-peakedness / J.M. Blin, M.A. Satterthwaite // Public Choice. - 1976. - Vol. 26. - No. 1. - C. 51-58.

19. Barbera, S. Strategy-proof voting schemes with continuous preferences / S. Barbera, B. Peleg // Social choice and welfare. - 1990. - Vol. 7. - No. 1. -P. 31-38.

20. Kelly, J.S. Strategy-proofness and social choice functions without singlevaluedness / J.S. Kelly //Econometrica: Journal of the Econometric Society. - 1977. - Vol. 45. - No. 2. - P. 439-446.

21. Gardenfors, P. Manipulation of social choice functions / P. Gardenfors // Journal of Economic Theory. - 1976. - Vol. 13. - No. 2. - P. 217-228.

22. Barbera S. The manipulation of social choice mechanisms that do not leave "too much" to chance / S. Barbera // Econometrica. - 1977. - Vol. 45. - No. 7. - P. 1573-1588.

23. Gibbard, A. Manipulation of schemes that mix voting with chance / A. Gibbard // Econometrica: Journal of the Econometric Society. - 1977. - Vol. 45. - No. 3. - P. 665-681.

24. Zeckhauser, R. Voting systems, honest preferences and Pareto optimality / Zeckhauser, R. //American Political Science Review. - 1973. - Vol. 67. - No. 3.

- P. 934-946.

25. Ching, S. Multi-valued strategy-proof social choice rules / S. Ching, L. Zhou // Social Choice and Welfare. - 2002. - Vol. 19. - No. 3. - P. 569-580.

26. Duggan, J. Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized / J. Duggan, T. Schwartz // Social Choice and Welfare. - 2000. - Vol. 17. - No. 1. - P. 85-93.

27. Rodriguez-Alvarez, C. On the manipulation of social choice correspondences / C. Rodriguez-Alvarez // Social Choice and Welfare. - 2007. - Vol. 29. - No. 2.

- P. 175-199.

28. Sato, S. On strategy-proof social choice correspondences / S. Sato // Social Choice and Welfare. - 2008. - Vol. 31. - No. 2. - P. 331-343.

29. Rodriguez-Alvarez, C. On strategy-proof social choice correspondences: a comment / C. Rodriguez-Alvarez // Social Choice and Welfare. - 2009. - Vol. 32. - No. 1. - P. 29-35.

30. Chopra, S. Knowledge-theoretic properties of strategic voting / S. Chopra, E. Pacuit, R. Parikh // European Workshop on Logics in Artificial Intelligence. -Berlin: Springer, 2004. - P. 18-30.

31. Gehrlein, W.V. On methods for generating random partial orders / W.V. Gehrlein // Operations research letters. - 1986. - Vol. 5. - No. 6. - P. 285291.

32. Gehrlein, W.V. Condorcet's paradox and anonymous preference profiles / W.V. Gehrlein, P.C. Fishburn //Public Choice. - 1976. - Vol. 26. - No. 1. - P. 1-18.

33. Gehrlein, W.V. Voting paradoxes and group coherence: the Condorcet efficiency of voting rules / W. V. Gehrlein, D. Lepelleyl. - Berlin: Springer Science & Business Media, 2010. - 385 p.

34. Feller, W. An introduction to probability theory and its applications: volume I / W. Feller. - New York: John Wiley & Sons, 1968. - Vol. 3. - 528 p.

35. Eggenberger, F. Uber die statistik verketteter Vorgänge / F. Eggenberger, G. Pölya //ZAMM-Journal of Applied Mathematics and Mechanics/Zeitschrift für Angewandte Mathematik und Mechanik. - 1923. - Vol. 3. - No. 4. - P. 279-289.

36. Berg, S. Paradox of voting under an urn model: The effect of homogeneity / S. Berg // Public Choice. - 1985. - Vol. 47. - No. 2. - P. 377-387.

37. Karpov, A. Preference diversity orderings / A. Karpov // Group Decision and Negotiation. - 2016. - Vol. 26. - No. 4. - P. 753-774.

38. Egecioglu, O. Monte-Carlo algorithms for uniform generation of anonymous and neutral preference structures / O. Egecioglu // Monte Carlo Methods and Applications. - 2009. - Vol. 15. - P. 241-255.

39. Egecioglu, O. The Likelihood of Choosing the Borda-winner with Partial Preference Rankings of the Electorate / O. Egecioglu, A.E. Giritligil // Journal of Modern Applied Statistical Methods. - 2011. - Vol. 10. - No. 1. - P. 348-361.

40. Kelly, J.S. Minimal manipulability and local strategy-proofness / J.S. Kelly // Social Choice and Welfare. - 1988. - Vol. 5. - No. 1. - P. 81-85.

41. Kemeny, J.G. Mathematics without numbers / J.G. Kemeny // Daedalus. -1959. - Vol. 88. - No. 4. - P. 577-591.

42. Chamberlin, J.R. An investigation into the relative manipulability of four voting systems / J.R. Chamberlin // Systems Research and Behavioral Science. - 1985. - Vol. 30. - No. 4. - P. 195-203.

43. Kelly, J.S. Almost all social choice rules are highly manipulable, but a few aren't / J.S. Kelly //Social choice and Welfare. - 1993. - Vol. 10. - No. 2. - P. 161-175.

44. Lepelley, D. Voting rules, manipulability and social homogeneity / D. Lepelley, F. Valognes // Public Choice. - 2003. - Vol. 116. - No. 1-2. - P. 165-184.

45. Favardin, P. Some further results on the manipulability of social choice rules / P. Favardin, D. Lepelley // Social Choice and Welfare. - 2006. - Vol. 26. - No. 3. - P. 485-509.

46. Aleskerov, F. On the manipulability of voting rules: the case of 4 and 5 alternatives / F. Aleskerov, D. Karabekyan, M.R. Sanver, V. Yakuba // Mathematical Social Sciences. - 2012. - Vol. 64. - No. 1. - P. 67-73.

47. Aleskerov, F. Manipulability of aggregation procedures in Impartial Anonymous Culture / F. Aleskerov, A. Ivanov, D. Karabekyan, V. Yakuba // Procedia Computer Science. - 2015. - Vol. 55. - P. 1250-1257.

48. Bartholdi, J. Voting schemes for which it can be difficult to tell who won the election / J. Bartholdi, C.A. Tovey, M.A. Trick // Social Choice and welfare. -1989. - Vol. 6. - No. 2. - P. 157-165.

49. Narodytska, N. Manipulation of Nanson's and Baldwin's Rules / N. Narodytska, T. Walsh, L. Xia // Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI). - 2011. - P. 713-718.

50. Conitzer, V. When are elections with few candidates hard to manipulate? / V. Conitzer, T. Sandholm, J. Lang // Journal of the ACM. - 2007. - Vol. 54. - No. 3. - P. 1-33.

51. Davies, J. Complexity of and Algorithms for Borda Manipulation / J. Davies, G. Katsirelos, N. Narodytska, T. Walsh // Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI). - 2011. - Vol. 11. - P. 657-662.

52. Zuckerman, M. Algorithms for the coalitional manipulation problem / M. Zuckerman, A.D. Procaccia, J.S. Rosenschein // Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms. - 2008. - P. 277-286.

53. Bartholdi, J.J. Single transferable vote resists strategic voting / J.J. Bartholdi, J.B. Orlin // Social Choice and Welfare. - 1991. - Vol. 8. - No. 4. - P. 341-354.

54. Faliszewski, P. Copeland voting: Ties matter / P. Faliszewski, E. Hemaspaandra, H. Schnoor // Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems. - 2008. - Vol. 2. - P. 983-990.

55. Xia, L. Complexity of Unweighted Coalitional Manipulation under Some Common Voting Rules / L. Xia, M. Zuckerman, A.D. Procaccia, V. Conitzer, J.S. Rosenschein //IJCAI. - 2009. - Vol. 9. - P. 348-352.

56. Coleman, T. On the complexity of manipulating elections / T. Coleman, V. Teague // Proceedings of the thirteenth Australasian symposium on Theory of computing. - 2007. - Vol. 65. - P. 25-33.

57. Карабекян, Д.С. О расширенных предпочтениях в задаче голосования / Д.С. Карабекян // Экономический журнал Высшей школы экономики. -2009. - Т. 13. - №. 1. - С. 19-34.

58. Pattanaik, Р.К. Strategy and group choice / P.K. Pattanaik, В. Dutta. - North-Holland, 1978. - Vol. 113.

59. Gehrlein, W.V. Constant scoring rules for choosing one among many alternatives / W.V. Gehrlein, P.C. Fishburn // Quality & Quantity. - 1981. - Vol. 15. - No. 2. - P. 203-210.

60. Borda, J. Mémoire sur les elections au scrutiny. Histoire de l'Académie Royale des Sciences pour 1781 / J. Borda. - Paris: 1784. - 479 p.

61. Congar, R. A characterization of the maximin rule in the context of voting / R. Congar, V. Merlin //Theory and Decision. - 2012. - Vol. 72. - No. 1. - P. 131-147.

62. Copeland, A.H. A reasonable social welfare function / A.H. Copeland // Mimeographed notes from a Seminar on Applications of Mathematics to the Social Sciences, University of Michigan. - 1951.

63. Вольский, В.И. Применение различных вариантов правила передачи голосов / В.И. Вольский, А.В. Карпов //Полития. - 2011. - №. 2. - С. 162-174.

64. De Condorcet, N. Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix. - Cambridge University Press, 2014. - 514 p.

65. Dodgson, C. A method of taking votes on more than two issues / С. Dodgson.

- Oxford: Clarendon Press, 1876. - 10 p.

66. Baldwin, J.M. The technique of the Nanson preferential majority system of election / J.M. Baldwin //Proceedings of the Royal Society of Victoria. - 1926.

- Vol. 39. - P. 42-52.

67. Nanson, E.J. Methods of election / E.J. Nanson // Proceedings of the Royal Society of Victoria. - 1882. - Vol. 19. - P. 197-240.

68. Tideman, N. Collective decisions and voting / N. Tideman. - Burlington: Ashgate, 2006. - 335 p.

69. Tideman, N. Independence of clones as a criterion for voting rules / N. Tideman // Social Choice and Welfare. - 1987. - Vol. 4. - No. 3. - P. 185-206.

Приложение А

П сИЗ И Л коллективного выбора

Приведем используемые в определении правил буквенные обозначения. Пусть вектор распределения позиций для альтернативы а - вектор V(а,Р) = (у1 (а,Р), ...,ит(а, Р))7 где (а,Р) обозначает количество избирателей, у которых а стоит на ]-ош месте в предпочтениях, {х, у) - скалярное произведение векторов х и у. г^(а, Р.¿) = |{& € А1аР{ &}| - ранг альтернативы а в предпочтениях Р^ V(а, Ь; Р) = {г € N|aPiЬ} - множество всех избирателей, для которых а предпочтительнее Ь. Если IV(а, Ь; Р)1 > IV(Ь,а;Р)1, то будем говорить, что а доминирует Ь по мажоритарному отношению, и писать аРмЬ. Если IV(а, Ь;Р)| = IV(Ь,а; Р)|, то а и Ь несравнимы по мажоритарному отношению, а 1мЬ.

1. Правило относительного большинства. Выбор по данному правилу определяется как множество альтернатив, являющихся наилучшими для наибольшего числа избирателей, т.е.

с € Сп(Р) а^шах ^ зп, у(а, Р ,

где вр1 = (1,0,..., 0).

- правило коллективного выбора, при котором выбор определяется как мно-

жество альтернатив, которые занимают место не ниже q в предпочтениях для наибольшего числа избирателей (при q = 1 это правило эквивалентно правилу относительного большинства):

с е САрр(Р) & с е arg max ((sApp,v(a, Р)^ ,

где spi = (1^^, 0,..., 0). q

3. Правило вето (обратное правило относительного большинства). Частный случай одобряющего голосования с квотой q = т — 1. Выбирается альтернатива, занявшая наименьшее число последних мест в предпочтениях избирателей.

4. Правило Борда [60]. По данному правилу для каждой альтернативы а вычисляется ранг Борда г (а, Р) как сумма рангов ri(a,Pi) по всем избирателям или с помощью вектора очков sb = (ш — 1,т — 2,..., 1, 0)

с е Св(Р) & с G argmax (^в, v(a, Р.

5. Максиминная процедура (аксиоматическое описание представлено в [61]). Для каждой альтернативы а вычисляется минимальное количество избирателей, которые предпочитают эту альтернативу некоторой другой, а затем выбирается альтернатива, для которой это значение максимально:

С G СМахтгп(Р) & с е arg max min IV (a,b; P )|.

аеА ЬеА

6. Двухступенчатая мажоритарная система (plurality with run-off). Выбирается альтернатива, являющаяся наилучшей больше чем для половины избирателей. Если такой альтернативы нет, то проводится второй тур голосования,

в котором участвуют две альтернативы, набравшие наибольшее количество голосов в первом туре.

7. Правило Коупленда [62]. Выбирается альтернатива, для которой количество побед минус количество поражений по мажоритарному отношению наибольшее, т.е.

CS(а, Р) = \{b е А\аРмb}\ -\{b е А\ЬРма}\, С е CCopeiandi(P) ^ се arg max CS (а, Р).

аеА

8. Правило Коупленда второго порядка. Сначала применяется правило Коупленда, а затем, в случае неоднозначности выбора, выбирается альтернатива а, для которой сумма очков CS(Ь, Р) по всем альтернативам 6, которые альтернатива а доминирует по мажоритарному отношению, максимальна

С е CCopeiand2(P) ^ се arg max CS (а, Р )&с е arg max V" CS (b, P).

аеА аеА z—'

Ъ'.аРм b

9. Правило передачи голосов (процедура Хара). Выбирается альтернатива, имеющая более 50 % первых мест в предпочтениях избирателей. Если таковой нет, то из профиля исключается альтернатива, имеющая наименьшее число первых мест. Процедура повторяется до тех пор, пока не будет выбрана какая-либо альтернатива.1

10. Победитель Кондорсе [64] - альтернатива, недоминируемая по мажоритарному отношению, т.е. а е Ccw(Р) ^ —^Ь е А, ЬРма.

11. Правило Доджсона [65]. Выбирается победитель Кондорсе, если он существует. Если победителя Кондорсе нет, то для каждой альтернативы проверяется, сколько раз нужно произвести замену местами двух соседних альтернатив

1 Существуют и другие вариации этого правила, отличающиеся порядком передачи голосов от исключаемых альтернатив к оставшимся или квотой, необходимой для перехода на следующий этап. Обзор различных вариантов правила передачи голосов представлен в [63].

в предпочтениях избирателей, чтобы она стала победителем Кондорсе. После этого выбирается альтернатива, для которой нужно произвести минимальное количество таких замен.

12. Правило К смени [41]. Введем сначала функцию расстояния по Кемени между линейными порядками Р\м Р2. Пусть {} - матрица бинарного отношения если aiPkа^ то элементы этой матрпцы = 1, ^' = —1. Расстояние между двумя предпочтениями вычисляется как сумма модулей разности элементов матриц и }

= £ — 4 'I

^3 Зi

а^еА о, еА

Результат правила Кемени - линейный порядок, для которого сумма расстояний до предпочтений всех избирателей минимальна, т.е.

Рк = а^ шт У^ ¿(Р, р).

Рс Т ' ^

Р еЬ

Победитель - кандидат, занимающий первое место в найденном упорядочении.

13. Процедура Болдуина (обратная процедура Борда) [66]. Для каждой альтернативы подсчитывается ранг Борда г(а,Р), затем из профиля удаляется альтернатива, имеющая наименьший ранг Борда. Процедура исключения альтернатив продолжается до тех пор, пока не останутся неисключаемые альтернативы, которые и являются множеством выбора в процедуре Болдуина.

14. Правило Нансона [67]. Рассчитываются значения ранга Борда для каждой альтернативы, затем из профиля удаляются все альтернативы, имеющие ранг Борда ниже среднего ранга,

г= ^ Е г(а,Р).

аеА

Процедура повторяется для нового профиля, и все продолжается до тех пор, пока не останутся неисключаемые альтернативы.

15. Турнир с выбыванием (правило последовательных попарных сравнений). Последовательность попарных сравнений определяется с помощью бинарного дерева и распределения кандидатов по концевым вершинам, которые задаются извне и известны избирателям как часть процедуры. В каждой неконцевой вершине дерева ставится кандидат, ставший победителем в паре ее дочерних вершин по мажоритарному отношению.

16. Правило Баклина [68]. Для каждого кандидата a,j вычисляется наименьшее такое значение к, при котором больше половины избирателей ставят кандидата aj среди к наилучших в своих предпочтениях. Кандидат с наименьшим

к

17. Процедура упорядоченных пар (ranked pairs) [69]. Процедура строит коллективное упорядочение Р, линейный порядок. Победитель - кандидат, занявший в Р первое место. Для всех пар кандидатов (aj,ai) Vaj,ai E A,aj = ai, вычисляется значение IV(aj,a¡; Р)|. Обозначим за pairs множество имеющихся

a

pa, для которой значение IV(aj, ai; Р)| максимально; б) для нее устанавливается коллективное предпочтение ajPai, если оно не противоречит условию транзитивности Р; в) из pairs удаляются пары (aj, ai) и (ai, aj). Таким образом, после

A

18. Процедура Блжа Выбирается победитель Кондорсе, если он существует. В противном случае выбирается победитель по правилу Борда.

Приложение В

Исходные коды разработанного программного комплекса

В.1 Вычисление индекса вероятности манипулирования: основная программа

1 nl=3;

2 п2 = 15;

3 nn=nl—п2 + 1;

4 ICXK zeros ( 1 .1111) :

5

6 for n=nl:n2

7 p(: ,1) =[1,2 ,3];

8 p(:,2)=[l,3,2];

9 p (: ,3) = [2 ,1 ,3];

10 p(:,4)=[2,3,l];

11 p (: , 5) = [3 ,1 ,2];

12 p (: ,6) = [3 ,2 ,1 ];

14 А—lio 11 ;

15 C=nchoosek(А,5 ) ;

16 K=nchoosek(5+n , 5 ) ;

17 АКО zeros(К.6);

-

---------24

25 Р zeros(3.п.К);

26 for i =1 :К

27 h = l;

28 for j =1:6

29 for k = l:AEC(i , j )

30 P(: ,h, i)=p(: , j ) ;

31 h hl:

32 end ;

33 end ;

34 end ;

35

36 V zeros(3,3,K);

37 for i =1 :K

38 for i и 1:3

39 for k = l:3

43

41

42

if P(k , 1 , i )=ia V ( i a , к , i ) =v ( i a , к , i ) +1 ; end ;

44

end ;

45

end ;

46 end ;

47 end ;

48

49 ЮС zeros (3 .3 .K) ;

50 MG zeros(3.3.K);

51 for i=l:K

52 [Ж(: , : , i) ,MG( : , i )] = majority (P ( : , i)) ;

53 end ;

54

55 ScorePlur=zeros(1 ,3 ,K) ;

56 RankPlur=zeros ( 1 ,3 ,K) ;

57 WinnerPlur=zeros ( 1 ,3 ,K) ;

58

59 ScoreBorda=zeros ( 1 ,3 ,K) ;

60 RankBorda=zeros ( 1 ,3 ,K) ;

61 WinnerBorda=zeros ( 1 ,3 ,K) ;

62

63 ScoreVeto=zeros ( 1 ,3 ,K) ;

64 RankVeto=zeros ( 1 ,3 ,K) ;

65 WinnerVeto=zeros ( 1 ,3 ,K) ;

67 ScoreRunoff=zeros (2 ,3 ,K) ;

68 RankRunoff=zeros (1 ,3 ,K) ;

69 WinnerRunoff=zeros (1 ,3 ,K) ;

70

71 ScoreStv=zeros(3 ,3,K) ;

72 RankStv=zeros (1 ,3 ,K) ;

73 WinnerStv=zeros (1 ,3 ,K) ;

74

75 ScoreCopeland=zeros (1 ,3 ,K) ;

76 RankCopeland=zeros (1 ,3 ,K) ;

77 WinnerCopeland=zeros (1 ,3 ,K) ;

78

79 for i =1 :K

80 [ WinnerPlur (: ,: , i) , RankPlur (: , i ) ,ScorePlur(: , i) ] =

plurality (P(: ,: ,i) ,n);

81 [ Winner Bor da (: ,: , i) , RankBorda (: ,: , i) ,ScoreBorda(: ,: , i) ] =

borda(P (: ,: ,i) ,n);

82 [ WinnerVeto (: ,: , i ) , RankVeto (: ,: , i) , ScoreVeto (: ,: , i) ] =

veto (P (: ,: , i) ,n);

83 [ Winner Runoff (: ,: , i) , RankRunoff (: ,: , i) , Score Runoff (: ,: , i

)]=runoff(P(: , i)) ;

84 [ WinnerStv (: , i) ,RankStv(: , i) ,ScoreStv(: , i)]=stv(P

85 [ WinnerCopeland (: ,: , i) , RankCopeland (: ,: , i) ,ScoreCopeland

(: ,: , i)] = copeland(P(: ,: , i)) ;

86 end;

87

88 MP zeros(K.1):

89 Check=zeros (K, 1) ;

90 CheckVoter —zeros(K, n);

91 Flag=zeros (K, 1) ;

92 f=0;

93 for i =1 :K

94 if Check(i ,1)==0

95 j =0;

96 while MP(i ,1)==0 Mi j<n

97 j j 1:

98 if CheckVoter (i,j)~=l

99 £=£ ^.

100 pe = [l ,1,1,1,1,1];

101 pb = [0 ,0 ,0 ,0 ,0 ,0]; 102

103 for ii=l:K

104 if isequal (tieBreak (WinnerCopeland (: ,: , i)) ,

tie Break (WinnerCopeland (: ,: , i i )))

105 j c =0;

106 CV=zeros(l,n);

107 while jc<n

109 if P ( : ,j , i)=P(: , je , ii )

110 CheckVoter ( ii ,jc)=l;

111 CV(l,jc)=l; H2 jj=jc;

113 end;

114 end;

115 c=sum(CV( 1 , : ) ) ;

116 if c~=0

117 ManipP=P ( : , : , i i ) ;

118 for jm = l:6

Ш. о ( Л ' \__1

11 pe ^ i ? jul j —i

120 ManipP ( : , j j )=p ( : , jm) ;

121 if lexTie( copel and (ManipP ( : , : ) ) ,P ( :

j ,i))>lexTie(copeland(P(: ,: , ii))

P(:,j,i))

122 pe(l,jm)=0;

123 pb ( 1 , jm) =0;

124 end;

125 if lexTie( copel and (ManipP ( : , : ) ) ,P ( :

j ,i))<lexTie(copeland(P(: ,: , ii))

P(:,j,i))

126 pb ( 1 , jm) =1;

127 end;

128 end;

129 end ;

130 Flag ( ii ,l)=f;

131 end;

132 end ;

133 end ;

134 if sum (pb)~=0

135 for ii=l:K

136 if Flag ( ii ,l)=f

137 MP( ii ,1) =1;

138 Check( ii ,1)=1;

139 end ;

140 end ;

141 end;

142 if j и

143 Check ( i , 1 ) =1;

144 end ;

145 end ;

146 end ;

147 end ;

148 end ;

149

150 ICM=zeros(K,l) ;

151 for i=l:K

152 if MP(i , 1)==1

153 ICM( i ,l)=factorial (n)/(factorial (AEC(i ,l))*factorial(

AEC(i ,2))*factorial (AEC(i ,3))*factorial (AEC(i ,4) )* factorial(AEC(i ,5))*factorial (AEC(i ,6)));

154 end;

155 end;

156 ICNK(n—2)=sum(ICM) /(6) лп ;

157 end;

B.2 Вычисление индексов успеха манипулирования и стимула к манипулированию: основная программа

1 nl=3;

2 п2 = 20;

-

4

5 IO.XK zeros ( 1 .1111 ) :

6 ICS=zeros(1 ,nn);

7 IOMS zeros (1 .1111) :

8

9 for n=nl:n2

10 p ( : ,1) = [ 1 ,2 ,3] ;

11 p(:,2)=[l,3,2];

12 p ( : ,3) = [2 ,1 ,3] ;

13 p(:,4)=[2,3,l];

14 p ( : , 5 ) = [3 ,1 ,2] ;

15 p ( : ,6) = [3 ,2 ,1 ] ;

17 А— lio 11 ;

18 C=nchoosek(А,5 ) ;

19 K=nchoosek(5+n , 5 ) ;

20 АКО zeros(К.G);

-

---------27

28 Р zeros(3.и.К);

29 for i =1 :К

30 h = l;

31 for j=l:6

32 for k = l:AEC(i , j )

33 P(: ,h, i)=p(: , j ) ;

34 Ii li 1 ;

35 end ;

36 end ;

37 end ;

38

39 V zeros(3,3,K);

40 for i =1 :K

41 for i и 1:3

42 for k 1:3

47

44

45

46

if P(k , 1 , i )=ia

V ( i a , к , i ) =v ( i a , к , i ) +1 ; end ; end ;

48

end ;

49 end ;

50 end ;

51

52 ЮС zeros (3 .3 .K) ;

53 MG zeros(3.3.K);

54 for i 1 :K

55 [Ж(: , : , i) ,MG( : , i )] = majority (P ( : , i)) ;

56 end ;

57

58 ScorePlur=zeros(1 ,3 ,K) ;

59 RankPlur=zeros ( 1 ,3 ,K) ;

60 WinnerPlur=zeros ( 1 ,3 ,K) ;

61

62 ScoreBorda=zeros ( 1 ,3 ,K) ;

63 RankBorda=zeros ( 1 ,3 ,K) ;

64 WinnerBorda=zeros ( 1 ,3 ,K) ;

65

66 ScoreVeto=zeros ( 1 ,3 ,K) ;

67 RankVeto=zeros ( 1 ,3 ,K) ;

68 WinnerVeto=zeros ( 1 ,3 ,K) ;

70 ScoreRunoff=zeros (2 ,3 ,K) ;

71 RankRunoff=zeros (1 ,3 ,K) ;

72 WinnerRunoff=zeros (1 ,3 ,K) ;

73

74 ScoreStv zeros(3.3.K):

75 RankStv=zeros (1 ,3 ,K) ;

76 WinnerStv=zeros (1 ,3 ,K) ;

77

78 for i =1 :K

79 [ WinnerPlur (: ,: , i) , RankPlur (: , i ) ,ScorePlur(: , i) ] =

plurality (P(: ,: ,i) ,n);

80 [ Winner Bor da (: ,: , i) , RankBorda (: ,: , i) ,ScoreBorda(: ,: , i) ] =

borda(P (: ,: ,i) ,n);

81 [ WinnerVeto (: ,: , i ) , RankVeto (: ,: , i) , ScoreVeto (: ,: , i) ] =

veto (P (: ,: , i) ,n);

82 [ Winner Runoff (: ,: , i) , RankRunoff (: ,: , i) , Score Runoff (: ,: , i

)]=runoff(P(: , i)) ;

83 [ WinnerStv (: , i) ,RankStv(: , i) ,ScoreStv(: , i)]=stv(P

84 end;

85

86 CheckVoter=zeros (K, n) ;

87 stimulV

—zeros(K, n);

88 stimul=zeros (K, 1) ;

89 manipSuccess=zeros (K, n) ;

90 ManipSuccess=zeros (К, 1 ) ;

91 \"K zeros (К. 1 ) ;

92

93 f=0;

94 for i =1 :K

95 j =0;

96 while j<n

97 j j 1 :

98 EqVoter —zeros(K, n);

99 if CheckVoter ( i , j )==0

100 W=0;

101 WS=0;

102 FlagW zeros (К. 1 ) ;

103 Flagl=zeros(К, 1) ;

104 Flag3=zeros(К, 1) ;

105 for ii=l:K

106 if isequal ( WinnerPlur ( : , : , i ) , WinnerPlur ( : , : ,

ii))

107

jc=0;