Диссертация (1137313), страница 3
Текст из файла (страница 3)
Доклад на тему: «Вычислительная сложность правил коллективного выбора и манипулирования», 9 апреля2015 г.13. XVII Апрельская международная научная конференция «Модернизацияэкономики и общества», Россия, Москва. Доклад на тему: «Манипулирование при неполной информации», 20 апреля 2016 г.14.
Научный семинар «Экспертные оценки и анализ данных», ИПУ РАН, Россия, Москва. Доклад на тему: «Манипулирование при неполной информации», 25 мая 2016 г.1215. Семинар «Математическая экономика» ЦЭМИ РАН, Россия, Москва. Доклад на тему: «Манипулирование при неполной информации», 28 февраля2017 г.16. XVIII Апрельская международная научная конференция «Модернизацияэкономики и общества», НИУ ВШЭ, Россия, Москва. Доклад на тему: «Коалиционное манипулирование при неполной информации», 12 апреля 2017г.17. Computational Social Choice Seminar, Institute of Logic, Language andComputation of University of Amsterdam, Нидерланды, Амстердам.
Докладна тему: «Manipulation under Incomplete Information», 16 мая 2017 г.Результаты исследования использовались в следующих проектах:1. «Математическое моделирование и конструирование механизмов в социальной, экономической и политической сферах с использованием методов теории принятия решений, теории игр и интеллектуального анализа данных»,МЛАВР НИУ ВШЭ, 2012 г.2. «Исследование новых методов и подходов в области математического моделирования и дизайна механизмов в социальной, экономической и политической сферах», МЛАВР НИУ ВШЭ, 2013 г.3.
«Теоретическое и численное исследование современных математических моделей в социально-экономической, политической и финансовой сферах»,МЛАВР НИУ ВШЭ, 2014 г.4. «Анализ данных и принятие решений в социально-экономических и политических системах», МЛАВР НИУ ВШЭ, 2015 г.5. «Разработка и исследование новых математических моделей в социальноэкономической и политической сферах», МЛАВР НИУ ВШЭ, 2016 г.13Личный вклад. Все результаты получены автором лично.Публикации. Основные результаты по теме диссертации изложены в 9 печатных изданиях, 3 из которых изданы в журналах, рекомендованных ВАК:1.
Veselova, Y. A. The difference between manipulability indices in the IC andIANC 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? // NRUHigher School of Economics. Series EC «Economics». –2016. –No. 152/EC/2016.–1,2 п.л.6. Веселова, Ю. А. Вычислительная сложность правил коллективного выбораи манипулирования // XVI Апрельская международная научная конференция по проблемам развития экономики и общества: сб.
науч. работ. –Кн. 3.–М. : Издательский дом НИУ ВШЭ, 2016. –С. 79-88. – 0,5 п.л.7. Веселова, Ю. А. Вычислительная сложность манипулирования в задаче голосования // Фундаментальная информатика, информационные техноло14гии и системы управления: реалии и перспективы: сб. науч. работ. Красноярск : Сибирский федеральный университет, 2014. – 0,6 п.л.8.
Веселова, Ю. А. Сложность порядковых правил коллективного выбора //XIV Апрельская международная научная конференция по проблемам развития экономики и общества: сб. науч. работ. –Кн. 4. –М. : Издательскийдом НИУ ВШЭ, 2014. –С. 431-438. – 0,3 п.л.9. Veselova, Y. A.
The difference between manipulability indexes in IC and IANCmodels // NRU Higher School of Economics. Series EC «Economics». –2012.–No. 17/EC/2012. – 0,6 п.л.Объем и структура работы. Диссертация состоит из введения, трех глав,заключения и двух приложений. Полный объем диссертации составляет 182страницы с 26 рисунками и 3 таблицами.
Список литературы содержит 69 наименований.15Глава 1Степень манипулируемости: основныепонятия, постановка задачи и обзорпроблемы1.1Проблема манипулированияПринятие коллективных решений – неотъемлемая часть жизни общества.Для агрегирования множества индивидуальных предпочтений применяютсяразличные процедуры голосования.
Однако у каждого метода есть свои недостатки. В частности, процедура может быть подвержена манипулированию состороны избирателей, т.е. избиратели, действуя стратегически, могут добиться более выгодного для них результата голосования, намеренно исказив своипредпочтения.Пример 1.1. Рассмотрим такой пример манипулирования: пусть два избирателя считают наилучшим кандидата , еще два избирателя – кандидата иодин избиратель – кандидата .
Применяется процедура относительного большинства, и при таких предпочтениях выигрывают кандидаты и . Однако дляпоследнего избирателя кандидат лучше кандидата ( на первом месте, на16втором и на третьем), и он голосует за кандидата , а не за , чтобы выигралтолько кандидат .О том, что в некоторых процедурах голосования участникам выгоднее действовать стратегически и сообщать свои неискренние предпочтения, знали ещев древности. Кроме того, правила коллективного выбора подвержены и манипулированию со стороны организатора голосования.
В этом случае различаютнамеренное изменение процедуры голосования и изменение множества участвующих в выборах кандидатов или избирателей (манипулирование повесткойдня), имеющие целью достижение более выгодного для организатора результатаголосования.Первый известный пример манипулирования при голосовании был описан вписьмах Плиния Младшего [13, 14], где имело место манипулирование именно со стороны организатора посредством изменения и правила голосования, имножества представленных к рассмотрению альтернатив.Конструирование такого правила выбора, которое даст заранее определенный (необходимый организатору) результат – задача дизайна механизмов (см.,например, [15]).
Изменение множества кандидатов или избирателей при неизменном правиле выбора – задача контроля голосования [16, 17].1.21.2.1Манипулирование со стороны избирателейМодель коллективного выбораВведем необходимые для дальнейшего изложения определения и обозначения. Имеется множество избирателей, = {1, 2, ..., }, каждый из которыхимеет предпочтения на множестве альтернатив , имеющем мощность . Альтернативы (кандидаты) будут обозначаться строчными буквами , , , , , , или 1 , 2 , 3 , ..., .17Определение 1.1. Бинарное отношение является слабым порядком, еслионо удовлетворяет следующим свойствам: 1) ацикличности: ¬∃ ≥ 1 такого,что 1 2 , 2 3 , ..., −1 , 1 ; 2) транзитивности: ∀, , ∈ , , ⇒ ;Определение 1.2.
Бинарное отношение является линейным порядком, еслионо явлется слабым порядком и удовлетворяет свойству связности: ∀, ∈ либо , либо .Предпочтения каждого избирателя представлены в виде линейного порядка на множестве альтернатив. Это означает, что каждой альтернативе присвоено некоторое место от 1 до (на первом месте – наилучшая алтернатива,на последнем – наихудшая), и нет альтернатив, стоящих на одном и том жеместе в предпочтениях. Через () обозначим множество всех линейных порядков на , а через ∈ () – предпочтения избирателя .
Если , этоозначает, что альтернатива более предпочтительна, чем альтернатива для⃗ , элементаизбирателя . Профилем предпочтений будем называть вектор ⃗ = (1 , 2 , ..., ). Этими которого являются предпочтения избирателей, предпочтения в дальнейшем будут также называться искренними предпочтениями. () – множество всех профилей предпочтений (для избирателей и альтернатив).
⃗− – профиль предпочтений всех избирателей кроме -го, т.е.⃗− = (1 , ..., −1 , +1 , ..., ).Принятие коллективного решения может заключаться в выборе некоторогоподмножества альтернатив, «победителей», или упорядочении альтенатив. Любой алгоритм, позволяющий получить коллективное решение на основе множества индивидуальных предпочтений мы будем называть процедурой агрегирования. В данной работе будут обсуждаться следующие виды процедур агре-18гирования: функции общественного благосостояния и правила коллективноговыбора.Функция общественного благосостояния ранжирует альтернативы, приэтом все альтернативы упорядочены, и на одном и том же месте могут располагаться две и более альтернативы (слабый порядок), : () → (), где () – множество всех слабых порядков на . Результат функции предста⃗ ) = = ∪ , где – отношение предпочтения, а – отношениевим в виде (безразличия.Правило коллективного выбора : () → 2 ∖ {∅} на выходе дает непустое подмножество альтернатив, множество победителей голосования, занима-⃗ ) = , т.е.
(⃗ ) = { ∈ :ющих первую строчку в ранжировании (¬∃ .. }.Правило (функция ) называется диктаторским (-ой), если существует⃗ ∈ () (⃗ ) = { ∈ : ¬∃ .. * } ( (⃗ ) =такой избиратель * , что ∀* ).Далее в примерах и утверждениях использованы определения различныхпроцедур агрегирования, которые мы не приводим в основном тексте.
Определения и описания всех рассмотренных в диссертационной работе правил представлены в Приложении А.Определение 1.3. Избиратель имеет стимул манипулировать в профиле⃗ при правиле , если ∃˜ такие, что (˜ , ⃗− ) (⃗( )). В этом случае⃗ называется манипулируемым.профиль 19Пример 1.2. Рассмотрим следующий профиль предпочтений⎛⎜⎜⎜⎜⃗ =⎜⎜⎜⎝⎞⎟⎟⎟⎟⎟.⎟⎟⎠Результат выбора по правилу Борда – альтернатива .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
