Диссертация (Степень манипулируемости процедур агрегирования)
Описание файла
Файл "Диссертация" внутри архива находится в папке "Степень манипулируемости процедур агрегирования". PDF-файл из архива "Степень манипулируемости процедур агрегирования", который расположен в категории "". Всё это находится в предмете "физико-математические науки" из Аспирантура и докторантура, которые можно найти в файловом архиве НИУ ВШЭ. Не смотря на прямую связь этого архива с НИУ ВШЭ, его также можно найти и в других разделах. , а ещё этот архив представляет собой кандидатскую диссертацию, поэтому ещё представлен в разделе всех диссертаций на соискание учёной степени кандидата физико-математических наук.
Просмотр PDF-файла онлайн
Текст из PDF
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»На правах рукописиВЕСЕЛОВА ЮЛИЯ АЛЕКСАНДРОВНАСТЕПЕНЬ МАНИПУЛИРУЕМОСТИ ПРОЦЕДУР АГРЕГИРОВАНИЯСпециальность 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-полных задач –трудно манипулируемой.Актуальность темы.
