Диссертация (1137313)
Текст из файла
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»На правах рукописиВЕСЕЛОВА ЮЛИЯ АЛЕКСАНДРОВНАСТЕПЕНЬ МАНИПУЛИРУЕМОСТИ ПРОЦЕДУР АГРЕГИРОВАНИЯСпециальность 05.13.18 —Математическое моделирование, численные методы и комплексы программДиссертация на соискание учёной степеникандидата физико-математических наукНаучный руководитель:доктор технических наук, с.н.сАлескеров Фуад ТагиевичМосква – 2017СодержаниеВведение .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .51 Степень манипулируемости: основные понятия, постановка задачи и обзор проблемы . . . . . . . . . . . . . . . . . . . . . . . . . 161.1 Проблема манипулирования . . .
. . . . . . . . . . . . . . . . . . . .161.2 Манипулирование со стороны избирателей . . . . . . . . . . . . . . .171.2.1 Модель коллективного выбора . . . . . . . . . . . . . . . . . . .171.2.2 Теоремы типа Гиббарда-Саттертуэйта . . . . . . . . . . . . . .201.2.3 Манипулирование при неполной информации . . . . . . . . . .281.3 Оценка степени манипулируемости правил коллективного выбора .331.3.1 Вероятностные модели . .
. . . . . . . . . . . . . . . . . . . . .341.3.2 Вероятность манипулирования в различных моделях . . . . . .391.4 Вычислительная сложность манипулирования . . . . . . . . . . . . .421.4.1 Конструктивное манипулирование без весов . . . . . . . . . . .431.4.2 Голосование с назначением весов и ограничением на множествокандидатов . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . .461.4.3 Деструктивное манипулирование . . . . . . . . . . . . . . . . .491.4.4 Манипулирование с неполной информацией . . . . . . . . . . .501.5 Заключение по Главе 1 . . . . . . . . . . . . . . . . . . . . . . . . . .502 Манипулирование в условиях неполной информации . . . . . .
532.1 Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2532.2 Математическая модель . . . . . . . . . . . . . . . . . . . . . . . . .552.2.1 Определения и обозначения . . . . . . . . . . . . . . . . . . . .552.2.2 Множественный выбор . . . . . . . . . . . . . . . . .
. . . . . .562.2.3 Функция публичной информации и манипулирование . . . . .582.2.4 Функции общественного благосостояния . . . . . . . . . . . . .612.3 Вычислимость и сильная вычислимость . . . . . . . . . . . . . . . .642.4 Вероятность манипулирования . .
. . . . . . . . . . . . . . . . . . .672.4.1 Теоретические результаты . . . . . . . . . . . . . . . . . . . . .672.4.2 Вычислительные эксперименты . . . . . . . . . . . . . . . . . .752.5 Успех манипулирования и стимул к манипулированию . . . . . . . .842.5.1 Вычислительные эксперименты . . . . . . . . . . . . . . . . . .902.6 Комплекс программ . . . . . . . . . . . . . .
. . . . . . . . . . . . . .932.6.1 Общее описание . . . . . . . . . . . . . . . . . . . . . . . . . . .932.6.2 Ввод условий задачи и представление результатов . . . . . . .952.7 Заключение по Главе 2 . . . . . . . . . . . . . . . . . . . . . . . . . .983 Вероятностные модели: IC, IAC, IANC . . . .
. . . . . . . . . . . 1013.1 Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1013.2 Определения и теоретическая основа . . . . . . . . . . . . . . . . . . 1033.2.1 Вероятностные модели . . . . . . . . . . . . . . . . . . . . . . . 1033.2.2 Индексы манипулируемости . . . . . . . . . .
. . . . . . . . . . 1093.3 Оценка расстояния между моделями IC и IANC. . . . . . . . . . . 1113.3.1 Максимальные и минимальные АН-классы. . . . . . . . . . . 1123.3.2 Оценка максимальной разности для малых значений . . . . 1203.3.3 Сравнение моделей IC, IAC, IANC в асимптотике .
. . . . . . . 1233.4 Степень манипулируемости правил коллективного выбора в моделях IC и IANC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13233.5 Заключение по Главе 3 . . . . . . . . . . . . . . . . . . . . . . . . . . 136Заключение .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141A Правила коллективного выбора . . . . . . . . . . . . . . . . . . . 149B Исходные коды разработанного программного комплекса . . . 154B.1 Вычисление индекса вероятности манипулирования: основная программа . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154B.2 Вычисление индексов успеха манипулирования и стимула к манипулированию: основная программа . . . . . . . . . . . . . . . . . . . 161B.3 Программы для реализации методов расширения предпочтений . . 169B.3.1Метод Leximin . . . . . . . . .
. . . . . . . . . . . . . . . . . . . 169B.3.2Метод Leximax. . . . . . . . . . . . . . . . . . . . . . . . . . . 169B.3.3Алфавитное правило устранения множественности выбора. . 170B.4 Программы расчета правил коллективного выбора . . . . . . . .
. . 171B.4.1Правило относительного большинства . . . . . . . . . . . . . . 171B.4.2Двухступенчатая мажоритарная система . . . . . . . . . . . . . 173B.4.3Правило передачи голосов . . . . . . . . . . . . . . . . . . . . . 176B.4.4Правило Коупленда . . . . . . . .
. . . . . . . . . . . . . . . . . 178B.5 Вспомогательные программы . . . . . . . . . . . . . . . . . . . . . . 180B.5.1Программа построения сужения профиля по множеству . . . . 180B.5.2Программа построения простого и взвешенного графа мажоритарного отношения . . . . . . . . . . . .
. . . . . . . . . . . . 180B.5.3Программа устранения множественности выбора по алфавитному правилу . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1824ВведениеВ теории коллективного выбора известна проблема подверженности правилпринятия коллективных решений манипулированию со стороны избирателей:участники голосования могут намеренно сообщить свои неискренние предпочтения с целью добиться более выгодного для них результата. Если правилоколлективного выбора допускает возможность манипулирования хотя бы дляодного избирателя и хотя бы в одной из множества возможных ситуаций (подситуацией понимается распределение предпочтений среди всех избирателей, т.е.профиль предпочтений), то правило называется манипулируемым.Манипулируемость правила коллективного выбора считается отрицательнымсвойством, так как избиратель, манипулируя, отклоняет результат голосованияот «истинного» коллективного выбора в свою пользу. Кроме того, если имеется несколько независимо манипулирующих избирателей, то результат можетоказаться для них даже хуже первоначального.
В то же время, избежать манипулирования полностью можно, исключив или сильно ограничив возможностиу избирателей влиять на результат. Так, примерами неманипулируемых процедур могут служить диктаторское правило или правило случайного выбораальтернативы. Однако вряд ли коллектив устроят такие правила принятия решений.Первый теоретический результат, с которого началось изучение манипулируемости правил голосования с помощью математического моделирования, был5получен независимо в [1, 2] и носит название теоремы Гиббарда–Саттертуэйта.Эта теорема утверждает, что любое недиктаторское правило коллективного выбора, результат которого – единственная альтернатива, является манипулируемым, если имеется хотя бы три возможных исхода. Поэтому возможность манипулирования имеет смысл не исключить, а затруднить или ограничить, ивозникает необходимость сравнивать степень манипулируемости разных правил.В [3–6] степень манипулируемости правила рассматривается как вероятностьвозникновения такой ситуации, в которой хотя бы одному избирателю будет выгодно исказить свои предпочтения при данном правиле.
Расчет такого индексанапрямую зависит от выбранной в исследовании вероятностной модели, определяющей множество элементарных исходов. Наиболее часто используемые в литературе вероятностные модели – модель независимых предпочтений (ImpartialCulture Model – модель IC) [7] и модель независимых анонимных предпочтений(Impartial Anonymous Culture Model – модель IAC) [8]. Важное теоретическоезначение имеет также модель независимых анонимных и нейтральных предпочтений, предложенная сравнительно недавно в [9].Базовая предпосылка большинства исследований – наличие полной информации у каждого из участников голосования о предпочтениях всех остальных избирателей.
В [10] и [11] рассмотрена задача манипулирования при неполной информации: избирателям не доступна информация о предпочтениях всех остальных участников голосования, но известны результаты опроса всех избирателей,представленные в некотором агрегированном виде.Другой подход, впервые рассмотренный в [12], предлагает сравнивать трудоемкость поиска стратегии манипулирования при помощи теории вычислительной сложности. Если для правила выбора существует полиномиальный алго6ритм поиска стратегии манипулирования, то она считается легко манипулируемой, а если поиск такой стратегии принадлежит классу NP-полных задач –трудно манипулируемой.Актуальность темы.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
