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

Введение к работе

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

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

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

В работах Д.Келли, Ф.Т.Алескерова, Э.Курбанова, Д.С.Карабекяна, Д.Лепеллье, А.Слинько, Д.Притчарда, М.Уилсона и др. степень манипулируемости правила рассматривается как вероятность возникновения такой си-

туации, в которой хотя бы одному избирателю будет выгодно исказить свои предпочтения при данном правиле. Расчет такого индекса зависит от выбранной в исследовании вероятностной модели, определяющей множество элементарных исходов. Наиболее часто используемые в литературе вероятностные модели - модель независимых предпочтений (Impartial Culture Model - модель 1С), описанная Г.Т.Гильбо в 1952 г., и модель независимых анонимных предпочтений (Impartial Anonymous Culture Model - модель IAC) (К.Куга и Х.Нагатани, 1974 г.). Важное теоретическое значение имеет также модель независимых анонимных и нейтральных предпочтений, предложенная сравнительно недавно О.Эгеджиолу и А.Гиритлигиль (2013 г.).

Базовая предпосылка большинства исследований - наличие полной информации у каждого из участников голосования о предпочтениях всех остальных избирателей, что представляется достаточно нереалистичным. В работах В.Конитцера и др. (2011 г.), А.Рейнхуд и У.Эндрисса (2012 г.) была рассмотрена задача манипулирования при неполной информации: избирателям недоступна информация о предпочтениях всех остальных участников голосования, но известны результаты опроса всех избирателей, представленные в некотором агрегированном виде, так называемая функция публичной информации.

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

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

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

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

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

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

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

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

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

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

6. Проведено сравнение вероятностных моделей, используемых для статистического анализа свойств правил коллективного принятия решений. Исследована максимальная разность вероятностных показателей в моделях 1С, IAC и IANC. Вычислены индексы манипулируемости для четырех правил в модели 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 г.

11. Конференция «Фундаментальная информатика, информационные технологии и системы управления: реалии и перспективы (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 Incomplete Information», 16 мая 2017 г.

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

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

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