Алгоритмы точной и приближённой оценки степени манипулируемости процедур агрегирования тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Иванов Александр Александрович

• Иванов Александр Александрович
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Иванов Александр Александрович

Введение

Глава 1. Обзор литературы и основные определения

1.1. Основные понятия и определения задачи коллективного выбора

1.2. Проблема манипулируемости

1.3. Методы оценки степени манипулируемости процедур агрегирования

Глава 2. Основные модели в оценке манипулируемости процедур агрегирования

2.1. Процедуры агрегирования и их вычислительная сложность

2.2. Модель множественного выбора и методы построения расширенных предпочтений

2.3. Вероятностные модели профилей: Impartial Culture (IC) и Impartial Anonymous Culture (IAC)

2.4. Модели индивидуального и коалиционного манипулирования

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

Глава 3. Методы точной оценки степени манипулируемости процедур агрегирования для случая 3 альтернатив

3.1. Алгоритмы точного расчёта индексов манипулируемости для случая 3 альтернатив

3.2. Результаты для позиционных процедур агрегирования для случая 3 альтернатив

3.3. Результаты для мажоритарных, турнирных и k-устойчивых процедур агрегирования для случая 3 альтернатив

3.4. Результаты для q-Паретовских процедур агрегирования для случая 3 альтернатив

3.5. Сравнение наименее манипулируемых процедур агрегирования для случая 3 альтернатив

3.6. Случай большого числа участников

3.7. Дополнительный метод формирования коалиций

Глава 4. Методы приближённой оценки степени манипулируемости процедур агрегирования для случаев 4 и 5 альтернатив

4.1. Алгоритмы приближённого расчёта индексов манипулируемости для случаев 4 и 5 альтернатив

4.2. Результаты для позиционных процедур агрегирования для случаев 4 и 5 альтернатив

4.3. Результаты для мажоритарных, турнирных и k-устойчивых процедур агрегирования для случаев 4 и 5 альтернатив

4.4. Результаты для q-Паретовских процедур агрегирования для случаев 4 и 5 альтернатив

4.5. Сравнение наименее манипулируемых процедур агрегирования для случаев 4 и 5 альтернатив

Заключение

Литература

Приложения

Приложение 1. Процедуры агрегирования, не рассматриваемые в работе

Приложение 2. Расширенные предпочтения для случаев 4 и 5 альтернатив

Введение диссертации (часть автореферата) на тему «Алгоритмы точной и приближённой оценки степени манипулируемости процедур агрегирования»

Введение

Ещё во времена Римской империи появились упоминания («Письма Плиния Младшего», 1983) того, что при использовании самой простой и известной процедуры выбора - Правила Относительного большинства - может происходить манипулирование, то есть искажение предпочтений участниками, для достижения более выгодного для себя результата процедуры агрегирования. Ещё больше таких ситуаций описано в наше время, например, на основе эмпирических данных показаны примеры возможного неискреннего заполнения предпочтений в процедурах принятия решений в ФИФА (КагаЬекуап, 2016), манипулирования во время выборов в Японии (Kawai, Watanabe, 2013) и манипулирования при выборе школ в США фесег£ 2023).

Предположим, что имеет место следующая ситуация: в процедуре агрегирования принимают участие 13 участников и 4 альтернативы. Альтернативы будем обозначать маленькими латинскими буквами, например, "а", "Ь" и т.д. Предположим, что у 6 участников предпочтения а > Ь > с > й, у 5 участников и у 2 участников с > Ь > й > а (Таблица 1).

Таблица 1. Пример ситуации (профиля) с 13 участниками и 4 альтернативами

Количество участников 6 5 2

1-я лучшая а Ь с

2-я лучшая Ь а Ь

3-я лучшая с а а

4-я лучшая а с а

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

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

знает о том, что у лучшей для них альтернативы с нет шансов на победу, то третья группа участников может записать в бюллетень вместо искренних предпочтений с > b > d > а, например, неискренние предпочтения b > с > d > а, иначе говоря, проголосовать не за с, а за Ь. Тогда альтернатива b получит 7 голосов и обгонит альтернативу а, то есть результатом процедуры агрегирования будет [Ь], и третья группа участников вместо наихудшей альтернативы в своих предпочтениях получит в результате процедуры агрегирования вторую лучшую. Это пример манипулирования.

Ключевой фундаментальный результат в области манипулирования -теорема Гиббарда-Саттертуэйта - гласит, что не существует процедуры агрегирования для случая трёх или более альтернатив, которая была бы одновременно неманипулируемой и недиктаторской (Gibbard, 1973), (Satterthwaite, 1975). Позднее теорема Гиббарда-Саттертуэйта была распространена и на случай множественного выбора, когда возможны ничьи между двумя или более альтернативами (Duggan, Schwartz, 2000).

После этого в литературе стал исследоваться вопрос: если не существует неманипулируемой процедуры агрегирования, то возможно ли проанализировать известные процедуры агрегирования и определить степень их манипулируемости (Chamberlin, 1985), (Smith, 1999), (Aleskerov, Kurbanov, 1999), (Slinko, 2002a,b), (Favardin, Lepelley, 2006), (Diss, Tsvelikhovskiy, 2021), (Durand, 2023)?

Для количественной оценки степени манипулируемости процедур агрегирования было предложено несколько индексов: индекс Нитцана-Келли (Nitzan, 1985) и (Kelly, 1993), который равен доле манипулируемых профилей. Затем в (Aleskerov, Kurbanov, 1999) были предложены индексы свободы и эффективности манипулирования.

Первый подход к анализу степени манипулируемости процедур агрегирования - это аналитический вывод формул для различных процедур агрегирования. Такие формулы могут быть как точными (Favardin, Lepelley, 2006), так и асимптотическими (Slinko, 2002a,b). Аналитические методы, предполагающие вывод точных или приближённых формул, чаще всего затрагивали только наиболее простые процедуры агрегирования, например,

Правило Относительного большинства (Fristrup, Kleiding, 1989), Одобряющее голосование с q=2, Правило Борда (Slinko, 2002a,b). Причина заключается в высокой сложности вывода формул, которые при этом необходимо выводить не только для каждого индекса, но и для каждого набора предпосылок (разных вероятностных моделей профилей, разных расширенных предпочтений или для алфавитного устранения несравнимости и т.д.). При этом наименее манипулируемыми чаще всего оказываются процедуры, состоящие из нескольких раундов, например, Процедура Нансона (Aleskerov et al., 2011a), для которых вывод аналитических формул является сложнейшей и нерешённой аналитической задачей.

Второй подход - использование компьютерного моделирования. Из-за экспоненциального темпа роста вычислительной сложности полный перебор всех возможных ситуаций (профилей), где у каждого участника процедуры агрегирования могут быть любые предпочтения, возможен в таких задачах только на очень маленьких количествах участников и альтернатив, поэтому чаще всего в литературе используется метод Монте-Карло, в рамках которого происходит генерация определенного набора случайных профилей с последующей оценкой степени манипулируемости (Chamberlin, 1985), (Smith, 1999), (Aleskerov, Kurbanov, 1999), (Aleskerov et al., 2011a,b), (Durand, 2023).

При этом компьютерное моделирование с использованием метода Монте-Карло позволяет получить приближенные оценки индексов манипулируемости для процедур агрегирования (Smith, 1999), (Карабекян, 2012), однако оно все равно имеет очень высокую вычислительную сложность, так как для получения достаточной точности в значении индексов необходимо генерировать большое количество профилей, например, 1 миллион, что вкупе с необходимостью генерации всех возможных попыток манипулирования выливается в очень высокую алгоритмическую сложность (Иванов, 2020). Чаще всего в таких работах рассматривается только случай индивидуального манипулирования, поскольку в случае коалиционного манипулирования добавляется еще один уровень сложности в виде необходимости перебора огромного количества всех возможных коалиций.

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

Объектом исследования является степень манипулируемости процедур агрегирования.

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

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

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

1. Разработаны вычислительные алгоритмы для компьютерного моделирования, позволяющего получить точные оценки степени индивидуальной и коалиционной манипулируемости для 26 процедур агрегирования для вероятностных моделей Impartial Culture и Impartial Anonymous Culture для случая 3 альтернатив;

2. Разработаны вычислительные алгоритмы для компьютерного моделирования, позволяющие получить приближенные оценки степени индивидуальной и коалиционной манипулируемости для 28 процедур агрегирования методом Монте-Карло для вероятностных моделей Impartial Culture и Impartial Anonymous Culture для случаев 4 и 5 альтернатив;

3. Получены результаты для точных оценок индексов индивидуальной и коалиционной манипулируемости для случая 3 альтернатив, выявлены наименее манипулируемые процедуры агрегирования для вероятностных моделей Impartial Culture и Impartial Anonymous Culture для четырёх различных способов построения расширенных предпочтений для случаев от 3 до 100 участников;

4. Получены результаты для приближённых значений индексов индивидуальной и коалиционной манипулируемости для случаев 4 и 5 альтернатив, выявлены наименее манипулируемые процедуры агрегирования для вероятностных моделей Impartial Culture и Impartial Anonymous Culture для четырёх различных способов построения расширенных предпочтений для случаев от 3 до 100 участников.

Теоретическая значимость работы заключается в разработке алгоритмов получения точных значений индексов индивидуальной и коалиционной манипулируемости для 26 процедур агрегирования для случая 3 альтернатив и приближённых значений индексов манипулируемости для случаев 4 и 5 альтернатив, а также в получении результатов и выявлении наименее манипулируемых процедур агрегирования для различных наборов параметров.

Практическая значимость работы заключается в разработке и получении программного комплекса на языке C#, позволяющего производить оценку степени манипулируемости различных процедур агрегирования по нескольким индексам манипулируемости, возможности добавлять при необходимости для расчёта степень манипулируемости не рассматриваемых в работе процедур агрегирования, а также в интерпретации результатов по наименее манипулируемым процедурам агрегирования для различных параметров, что

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

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

Для случая 3 альтернатив были разработаны алгоритмы, позволяющие осуществить полную генерацию всех возможных ситуаций (профилей) для вероятностной модели Impartial Anonymous Culture, затем на основе формул производился пересчёт индексов манипулируемости для каждого профиля для вероятностной модели Impartial Culture, что позволило получить точные значения индексов манипулируемости для случаев от 3 до 100 участников.

Для случаев 4 и 5 альтернатив были разработаны алгоритмы, позволяющие получить приближённые значения индексов манипулируемости для вероятностных моделей Impartial Culture и Impartial Anonymous Culture с помощью метода Монте-Карло путём генерации 1 миллиона случайных профилей для случаев от 3 до 100 участников.

Алгоритмы компьютерного моделирования, включая реализацию процедур агрегирования, схему генерации профилей (полный перебор, расчёт количества профилей в вероятностных моделях и генерация по методу Монте-Карло), проверку профилей на индивидуальную и коалиционную манипулируемость через генерацию всех возможных попыток манипулирования, а также расчёт индексов манипулируемости, были реализованы на языке программирования C#. Научная новизна работы заключается в следующем:

1. Впервые предложены алгоритмы расчета точных, а не приближенных индексов индивидуальной и коалиционной манипулируемости 26 процедур агрегирования для случая 3 альтернатив для моделей Impartial Culture и Impartial Anonymous Culture;

2. Впервые получены и проанализированы точные значения нескольких индексов манипулируемости для 26 процедур агрегирования для случая 3

альтернатив для моделей Impartial Culture и Impartial Anonymous Culture для индивидуального и коалиционного манипулирования;

3. Впервые получены и проанализированы приближённые значения нескольких индексов манипулируемости для 28 процедур агрегирования для случаев 4 и 5 альтернатив для моделей Impartial Culture и Impartial Anonymous Culture для коалиционного манипулирования;

4. Исследованы различия степени индивидуальной и коалиционной манипулируемости 28 процедур агрегирования, выявлены наименее манипулируемые процедуры агрегирования для различных моделей. Основные положения и результаты, выносимые на защиту:

1. Разработаны алгоритмы для получения точных значений индексов индивидуальной и коалиционной манипулируемости для 26 процедур агрегирования для случая 3 альтернатив для случаев от 3 до 100 участников для вероятностных моделей Impartial Culture и Impartial Anonymous Culture для индекса Нитцана-Келли, индексов свободы и эффективности манипулирования и индексов разрешимости;

2. Разработаны алгоритмы для получения приближённых значений индексов индивидуальной и коалиционной манипулируемости для 28 процедур агрегирования для случаев 4 и 5 альтернатив для случаев от 3 до 100 участников для моделей Impartial Culture и Impartial Anonymous Culture для индекса Нитцана-Келли, индексов свободы и эффективности манипулирования и индексов разрешимости;

3. Получены и проанализированы результаты для точных значений индексов индивидуальной и коалиционной манипулируемости для 26 процедур агрегирования для случая 3 альтернатив для случаев от 3 до 100 участников для индекса Нитцана-Келли, индексов свободы и эффективности манипулирования и индексов разрешимости, выявлены наименее манипулируемые процедуры агрегирования для различных моделей и наборов параметров;

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

процедур агрегирования для случаев 4 и 5 альтернатив для случаев от 3 до 100 участников для индекса Нитцана-Келли, индексов свободы и эффективности манипулирования и индексов разрешимости, выявлены наименее манипулируемые процедуры агрегирования для различных моделей и наборов параметров;

5. Получены и проанализированы результаты для приближённых значений индексов индивидуальной и коалиционной манипулируемости для случая 3 альтернатив для случаев от 101 до 1000 участников для индекса Нитцана-Келли, индексов свободы и эффективности манипулирования и индексов разрешимости, выявлены соотношения индексов манипулируемости между парами процедур агрегирования;

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

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

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

1. Международная научная конференция «The 12th Meeting of the Society for Social Choice and Welfare», Бостон, США, 18-21 июня 2014 года. Доклад «Coalitional Manipulability of Majority Relation-Based Social Choice Rules»

2. XVI Апрельская международная научная конференция «Модернизация экономики и общества», Москва, Россия, 7-10 апреля 2015 года. Доклад «Манипулируемость правил коллективного выбора в Impartial Anonymous Culture»

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

4. Международная научная конференция «13th Meeting of the Society for Social Choice and Welfare», Лунд, Швеция, 28 июня - 1 июля 2016 года. Доклад «On the degree of coalitional manipulability of aggregation procedures»

5. XVIII Апрельская международная научная конференция по проблемам развития экономики и общества, Москва, Россия, 11-14 апреля 2017 года. Доклад «Манипулируемость обобщенных скоринговых правил голосования для случая 3 альтернатив»

6. Международная научная конференция «The 14th Meeting of the Society for Social Choice and Welfare», Сеул, Южная Корея, 14-17 июня 2018 года. Доклад «Upper Bound of Manipulability for the Case of 3 Alternatives»

7. XVII Всероссийская школа-конференция молодых ученых «Управление большими системами», Москва, Россия, 6-9 сентября 2021 года. Доклад «Алгоритмы расчёта коалиционной манипулируемости процедур агрегирования»

8. XXIII Ясинская (Апрельская) международная научная конференция по проблемам развития экономики и общества, Москва, Россия, 5-22 апреля 2022 года. Доклад «New Results in Manipulability of Social Choice Rules: Systematization and Visualization»

Также результаты работы были представлены на следующих научных семинарах и школах:

1. Международная научная школа «Interdisciplinary Analysis of Voting Rules», Каен, Франция, 8-12 июля 2014 года. Постерная презентация «Coalitional Manipulability of Majority Relation-Based Social Choice Rules»

2. Научный семинар «Экспертные оценки и анализ данных» ИПУ РАН, 25.02.2015. Доклад «Манипулируемость правил коллективного выбора в Impartial Anonymous Culture»

3. Студенческий семинар профессора Е.Г. Ясина "Теневое Правительство", 30.04.2015. Доклад «Коалиционное манипулирование процедур голосования»

4. Научный семинар МЛАВР (на данный момент - Международный центр анализа и выбора решений НИУ ВШЭ), 02.10.2018. Доклад «Методика оценки манипулируемости правил коллективного выбора для различных случаев»

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

6. Научный семинар «Математическая экономика» ЦЭМИ РАН, 19.05.2020. Доклад «Коэффициенты манипулируемости и алгоритмы их расчета для правил коллективного выбора»

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

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

9. Научный семинар научного руководителя МИЭМ НИУ ВШЭ, 25.04.2024. Доклад «Точные и приближенные алгоритмы оценки манипулируемости процедур агрегирования»

10. Общемосковский семинар «Математические методы анализа решений в экономике, бизнесе и политике», НИУ ВШЭ, 19.03.2025. Доклад «Коалиционное манипулирование процедур агрегирования: алгоритмы и результаты»

11. Общемосковский семинар «Теория управления организационными системами», ИПУ РАН, 04.09.2025. Доклад «Алгоритмы точной и приближённой оценки степени манипулируемости процедур агрегирования»

12. Семинар Кафедры исследования операций Факультета Вычислительной математики и кибернетики МГУ, 10.09.2025. Доклад «Алгоритмы точной и приближённой оценки степени манипулируемости процедур агрегирования»

13. Научно-исследовательский семинар «Вычислительные среды», МИЭМ НИУ ВШЭ, 01.10.2025. Доклад «Алгоритмы точной и приближённой оценки степени манипулируемости процедур агрегирования» Публикации по теме диссертации. Основные результаты исследования

были опубликованы в следующих статьях в журналах из Списка ВАК и/или из Списка журналов НИУ ВШЭ и/или в статьях, индексируемых в Scopus и/или в Web of Science:

1. Иванов А.А. Эффективные вычислительные схемы расчета манипулируемости процедур агрегирования // Информационные технологии и вычислительные системы. 2020. № 2. С. 38-50.

2. Иванов А.А. Алгоритмы расчета точных значений индексов манипулируемости для случая трех альтернатив // Журнал Новой экономической ассоциации. 2022. № 5 (57). С. 14-23.

3. Ivanov A. Manipulability of Aggregation Procedures for the Case of Large Numbers of Voters // Data Analysis and Optimization. Springer Optimization and Its Applications. 2023. Vol. 202. P. 167-180.

4. Aleskerov F.T., Karabekyan D., Ivanov A., Yakuba V.I. On the bounds of weak manipulability of majoritarian aggregation procedures // Procedia Computer Science. 2019. Vol. 162. P. 887-894.

5. Aleskerov F.T., Ivanov A., Karabekyan D., Yakuba V.I. Manipulability of majority relation-based collective decision rules // Smart Innovation, Systems and Technologies. 2018. Vol. 72. P. 82-91.

6. Aleskerov F.T., Karabekyan D., Ivanov A., Yakuba V.I. Manipulability of majoritarian rules by coalitions with the same first-ranked alternative // Procedia Computer Science. 2017. Vol. 122. P. 993-1000.

7. Aleskerov F.T., Ivanov A., Karabekyan D., Yakuba VI. Manipulability of Aggregation Procedures in Impartial Anonymous Culture // Procedia Computer Science. 2015. Vol. 55. P. 1250-1257. Другие публикации по теме диссертации:

1. Aleskerov F. T., Ivanov A., Karabekyan D., Yakuba V. I. On the Individual and Coalitional Manipulability of q-Paretian Social Choice Rules, in: Advances in Collective Decision Making: Interdisciplinary Perspectives for the 21st Century. Springer, 2023. P. 95-111.

2. Иванов А. А., Карабекян Д. С., Якуба В. И. Манипулируемость правил коллективного выбора в Impartial Anonymous Culture // В кн.: XVI Апрельская международная научная конференция по проблемам развития экономики и общества: в 4 кн. / Отв. ред.: Е. Г. Ясин. Кн. 1. М.: Издательский дом НИУ ВШЭ, 2016. С. 488-494.

3. Иванов А. А., Якуба В. И. Быстрый алгоритм оценки манипулируемости правил коллективного выбора // В кн.: XVII Апрельская международная научная конференция по проблемам развития экономики и общества: в 4 кн. / Отв. ред.: Е. Г. Ясин. Кн. 4. М.: Издательский дом НИУ ВШЭ, 2017. С. 495-501.

4. Алескеров Ф. Т., Карабекян Д. С., Иванов А. А., Якуба В. И. О манипулируемости процедуры выбора Хара // В кн.: XIII Всероссийское совещание по проблемам управления ВСПУ-2019: труды. М.: ИПУ РАН, 2019. С. 1-6.

Личный вклад автора. Автором лично разработаны алгоритмы оценки степени коалиционной манипулируемости 28 процедур агрегирования. Для случая 3 альтернатив автором лично разработана схема получения точных значений индексов манипулируемости, для случая 4 и 5 альтернатив автором была разработана схема получения приближённых значений индексов манипулируемости. Автором лично были разработаны алгоритмы и получены результаты для случая большого числа (до 1000) участников.

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

процедур агрегирования, а также оценка верхней и нижней границ манипулируемости были выполнены в соавторстве с Ф.Т. Алескеровым, Д.С. Карабекяном и В.И. Якубой, где автор осуществлял разработку алгоритмов, проведение вычислений, получение результатов, а также принимал участие в анализе полученных результатов.

Диссертация состоит из введения, четырёх глав, заключения, списка литературы и приложения, содержит 139 страниц, 5 таблиц и 55 рисунков. В первой главе вводятся основные понятия, формулируется проблема манипулирования, дается обзор литературы и описываются существующие в литературе методы оценки степени манипулируемости процедур агрегирования. Вторая глава посвящена описанию основных моделей в задаче оценки степени манипулируемости процедур агрегирования: даются формальные определения процедур агрегирования, а также оценки алгоритмической сложности их вычисления, затем приводится описание модели множественного выбора и методов построения расширенных предпочтений, даётся описание вероятностных моделей профилей, моделей индивидуального и коалиционного манипулирования, наконец, описываются индексы манипулируемости. Третья глава посвящена оценке степени манипулируемости 26 процедур агрегирования для случая 3 альтернатив: описываются модели и алгоритмы получения точных оценок индексов манипулируемости, после чего описываются результаты. В конце главы приводятся отдельные результаты для случаев большого числа участников, а также для дополнительной модели формирования коалиций. Четвертая глава посвящена оценке степени манипулируемости 28 процедур агрегирования для случаев 4 и 5 альтернатив: сначала описывается модель, ее отличие от модели трех альтернатив, после чего описываются алгоритмы и результаты.

Глава 1. Обзор литературы и основные определения

1.1. Основные понятия и определения задачи коллективного выбора

Мы будем использовать нотацию и определения, основанные на работах (Aleskerov et а1., 2011а,Ь) и (Карабекян, 2012). Несмотря на то что в литературе были исследования моделей с неполной информацией, например, в (Соп^ег et а1., 2011) и ^еу^оМ, Endriss, 2012), мы рассматриваем классическую модель манипулирования, то есть модель с полной информацией, когда предпочтения всех участников известны.

Предполагается, что есть множество альтернатив А, состоящее из т элементов. Предполагается, что есть п участников процедуры агрегирования, где у каждого участника есть некоторое предпочтение на множестве альтернатив. Предпочтения ¿-го участника мы будем обозначать как Р^

Предполагается, что предпочтение каждого участника (Рг) является линейным порядком на множестве А, то есть ^ является бинарным отношением хРу на множестве А и при этом обладает свойствами:

1. Антирефлексивности: Ух Е А хРу

2. Транзитивности: Ух, у, г если хРу и уРг, то хРг

3. Связности: Ух, у если х Ф у, то либо хРу, либо уРх

Упорядоченное множество (вектор) предпочтений всех участников

называется профилем и обозначается как Р. Таким образом, профиль состоит из п предпочтений, где каждое предпочтение - это один из т! линейных порядков на множестве альтернатив А.

Процедура агрегирования С(Р) ставит в соответствие профилю Р результат процедуры агрегирования, то есть является отображением из множества профилей в непустое подмножество множества альтернатив.

Результатом процедуры агрегирования может быть как одна альтернатива (х), где х Е А в случае, если у процедуры агрегирования единственный победитель, так и набор альтернатив (хг ...хк},где У1 XI Е А, если получилась ничья между несколькими альтернативами. Поэтому результат процедуры агрегирования - это непустое подмножество множества альтернатив, то есть. если

Список литературы диссертационного исследования кандидат наук Иванов Александр Александрович, 2025 год

Литература

1. Айзерман М. А., Алескеров Ф. Т. Задача Эрроу в теории группового выбора // Автоматика и телемеханика. — 1983. — № 9. — С. 127-151.

2. Иванов А. А. Эффективные вычислительные схемы расчёта манипулируемости процедур агрегирования // Информационные технологии и вычислительные системы. — 2020. — № 2. — С. 38-50.

3. Иванов А.А. Алгоритмы расчета точных значений индексов манипулируемости для случая трех альтернатив // Журнал Новой экономической ассоциации. 2022. № 5 (57). С. 14-23.

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

5. Карабекян Д. С. Манипулирование в задаче коллективного принятия решений: дис. ... канд. экон. наук: 08.00.13. — Москва, 2012. — 171 с.

6. Коргин Н. А. Неманипулируемые механизмы обмена в активных системах.

— Москва: ИПУ РАН, 2003. — 108 с.

7. Петровский А. Б. Теория принятия решений. — Москва: Академия, 2009.

— 384 с.

8. Письма Плиния Младшего. Книги I-X. — Москва: Наука, 1983. — (Литературные памятники).

9. Эрроу К. Дж. Коллективный выбор и индивидуальные ценности. — Москва: Государственный университет «Высшая школа экономики», 2004.

— 204 с.

10. Aleskerov F. Procedures of multicriterial choice // Preprints of the IFAC/IFORS Conference on Control Science and Technology for Development. — 1985. — P. 858-869.

11. Aleskerov F. Relational-functional voting operators. — California Institute of Technology, Social Science Working Paper 818, 1992.

12. Aleskerov F. Arrovian aggregation models. — Dordrecht: Kluwer Academic Publishers, 1999.

13. Aleskerov F., Chistyakov V., Kalyagin V. The threshold aggregation // Economics Letters. — 2010. — Vol. 107. — P. 261-262.

14. Aleskerov F., Chistyakov V. The threshold decision making effectuated by the enumerating preference function // International Journal of Information Technology and Decision Making. — 2013. — Vol. 12, No. 6. — P. 1201-1222.

15. Aleskerov F., Karabekyan D., Sanver R., Yakuba V. On manipulability of positional voting rules // SERIEs: Journal of the Spanish Economic Association. — 2011. — Vol. 2 (4). — P. 431-446.

16. Aleskerov F., Karabekyan D., Sanver R., Yakuba V. On the degree of manipulability of multi-valued social choice rules // Homo Oeconomicus. —

2011. — Vol. 28 (1-2). — P. 205-216.

17. Aleskerov F., Karabekyan D., Sanver R., Yakuba V. On the manipulability of voting rules: Case of 4 and 5 alternatives // Mathematical Social Sciences. —

2012. — Vol. 64. — P. 56-65.

18. Aleskerov F., Kurbanov E. Degree of manipulability of social choice procedures // Alkan A. et al. (eds.) Current Trends in Economics. — Berlin Heidelberg, New York: Springer, 1999.

19. Aleskerov F. T., Subochev A. On stable solutions to the ordinal social choice problem // Doklady Mathematics. — 2009. — Vol. 79, No. 3. — P. 437-439.

20. Arrow K. Social Choice and Individual Values. — New Haven, CT: Yale University Press, 1951. — 124 p.

21. Baldwin J. M. The technique of the Nanson preferential majority system of election // Proceedings of the Royal Society of Victoria. — 1926. — N.S. 39. — P. 42-52.

22. Barbera S. The manipulability of social choice mechanisms that do not leave too much to chance // Econometrica. — 1977. — Vol. 45. — P. 1572-1588.

23. Barbera S., Bossert W., Pattanaik P. Ranking Sets of Objects // In: Barbera S., Hammond P. J., Seidl C. (eds.) Handbook of Utility Theory. — Boston: Kluwer Academic Publishers, 2004. — Vol. 2.

24. Barbera S., Dutta B., Sen A. Strategyproof social choice correspondences // Journal of Economic Theory. — 2001. — Vol. 101. — P. 374-394.

25. Berg S., Lepelley D. On probability models in voting theory // Statistica Neerlandica. — 1994. — Vol. 48. — P. 133-146.

26. Black D. The theory of committees and elections. — Cambridge: Cambridge University Press, 1958. — 221 p.

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

28. Blin J. M., Satterthwaite M. A. Individual decisions and group decisions // Journal of Public Economics. — 1978. — Vol. 10. — P. 247-267.

29. Borda J. C. Mémoire sur les élections au scrutiny // Histoire de l'Académie Royale des Sciences pour 1781. — Paris, 1784.

30. Brams S., Fishburn P. Approval voting // American Political Science Review. — 1978. — Vol. 72, No. 3. — P. 831-847.

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

32. Chamberlin J. R., Featherston F. Selecting a voting system // The Journal of Politics. — 1986. — Vol. 48, No. 2. — P. 347-369.

33. Conitzer V., Walsh T., Xia L. Dominating manipulations in voting with partial information // Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. — 2011. — Vol. 11. — P. 638-643.

34. Copeland A. H. A "reasonable" social welfare function // Seminar on Mathematics in Social Sciences. — Ann Arbor: University of Michigan, 1951.

35. Decerf B. A modification aimed at reducing the manipulability and inefficiency of the Boston school choice mechanism // Social Choice and Welfare. — 2023.

— Vol. 60. — P. 75-101. — DOI: 10.1007/s00355-021-01331-0.

36. Diss M., Tsvelikhovskiy B. Manipulable outcomes within the class of scoring voting rules // Mathematical Social Sciences. — 2021. — Vol. 111. — P. 11-18.

— DOI: 10.1016/j.mathsocsci.2021.02.002.

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

38. Durand F. Coalitional manipulation of voting rules: simulations on empirical data // Constitutional Political Economy. — 2023. — Vol. 34. — P. 390-409. — DOI: 10.1007/s10602-022-09376-8.

39. Eggenberger F., Polya G. Über die Statistik verketteter Vorgänge // Zeitschrift für Angewandte Mathematik und Mechanik. — 1923. — Vol. 3, No. 4. — P. 279-289.

40. Favardin P., Lepelley D., Serais J. Borda rule, Copeland method and strategic manipulation // Review of Economic Design. — 2002. — Vol. 7. — P. 213-228. — DOI: 10.1007/s100580200073.

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

42. Ferejohn J. A., Grether D. On a class of rational social decision procedures // Journal of Economic Theory. — 1974. — Vol. 8. — P. 471-482.

43. Fishburn P. Condorcet social choice functions // SIAM Journal on Applied Mathematics. — 1977. — Vol. 33, No. 3. — P. 469-489.

44. Fristrup P., Kleiding H. A note on asymptotical strategy-proofness // Economics Letters. — 1989. — Vol. 31, No. 4. — P. 307-312. — DOI: 10.1016/0165-1765(89)90020-7.

45. Gärdenfors P. Manipulation of social choice functions // Journal of Economic Theory. — 1976. — Vol. 13. — P. 217-228.

46. Garman M. B., Kamien M. I. The paradox of voting: probability calculations // Behavioral Science. — 1968. — Vol. 13. — P. 306-316.

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

48. Gibbard A. Manipulation of voting schemes // Econometrica. — 1973. — Vol. 41. — P. 587-601.

49. Good J. A note on Condorcet set // Public Choice. — 1971. — Vol. 10. — P. 97101.

50. Grofman B., Feld S. L. If you like the alternative vote (a.k.a. the instant runoff), then you ought to know about the Coombs rule // Electoral Studies. — 2004. — Vol. 23. — P. 641-659.

51. Hare Th. The election of representatives, parliamentary and municipal. — London: Longmans, Green, Reader and Dyer, 1873. — 249 p.

52. Huang H. C., Chua V. C. H. Analytical representation of probabilities under the IAC condition // Social Choice and Welfare. — 2000. — Vol. 17. — P. 143-155.

53. Iwata Y. Strategic nomination and non-manipulable voting procedures // Review of Economic Design. — 2023. — Vol. 27. — P. 867-891. — DOI: 10.1007/s10058-023-00327-9.

54. Kalai E., Muller E. Characterization of domains admitting nondictatorial social welfare functions and nonmanipulable voting procedures // Journal of Economic Theory. — 1977. — Vol. 6. — P. 457-469.

55. Kamwa E., Moyouwou I. Susceptibility to manipulation by sincere truncation: the case of scoring rules and scoring runoff systems // In: Diss M., Merlin V. (eds.) Evaluating Voting Systems with Probability Models. — Cham: Springer, 2021. — (P. in Studies in Choice and Welfare). — DOI: 10.1007/978-3-030-48598-6_12.

56. Karabekyan D. Strategic behavior in exhaustive ballot voting: what can we learn from the FIFA World Cup 2018 and 2022 host elections? — Moscow: NRU Higher School of Economics, Series WP BRP "Economics/EC", No. 130, 2016.

57. Kawai K., Watanabe Y. Inferring strategic voting // American Economic Review. — 2013. — Vol. 103. — P. 624-662.

58. Kelly J. Almost all social choice rules are highly manipulable, but few aren't // Social Choice and Welfare. — 1993. — Vol. 10. — P. 161-175.

59. Kramer G. H. A dynamical model of political equilibrium // Journal of Economic Theory. — 1977. — Vol. 16. — P. 310-333.

60. Lepelley D., Valognes F. Voting rules, manipulability and social homogeneity // Public Choice. — 2003. — Vol. 116. — P. 165-184.

61. Miller N. A new solution set for tournaments and majority voting: further graph-theoretical approaches to the theory of voting // American Journal of Political Science. — 1980. — Vol. 24, No. 1. — P. 68-96.

62. Moreno D., Walker M. Nonmanipulable voting schemes when participants' interests are partially decomposable // Social Choice and Welfare. — 1991. — Vol. 8. — P. 221-233. — DOI: 10.1007/BF00177660.

63. Nanson E. J. Methods of election. — British Government Blue Book Miscellaneous. — 1907. — No. 3.

64. Narodytska N., Walsh T., Xia L. Manipulation of Nanson's and Baldwin's rules // Proceedings of the AAAI Conference on Artificial Intelligence. — 2011. — Vol. 25, No. 1. — P. 713-718. — DOI: 10.1609/aaai.v25i1.7872.

65. Nitzan S. The vulnerability of point-voting schemes to preference variation and strategic manipulation // Public Choice. — 1985. — Vol. 47. — P. 349-370.

66. Nurmi H. Voting procedures — a summary analysis // British Journal of Political Science. — 1983. — Vol. 13. — P. 181-208.

67. Ozyurt S., Sanver R. A general impossibility result on strategy-proof social choice hyperfunctions // Games and Economic Behavior. — 2009. — Vol. 66. — P. 880-892.

68. Peleg B. A note on manipulability of large voting schemes // Theory and Decision. — 1979. — Vol. 11. — P. 401-412. — DOI: 10.1007/BF00139450.

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

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

71. Reilly B. Democracy in divided societies: electoral engineering for conflict management. — Cambridge: Cambridge University Press, 2001. — 256 p.

72. Richelson J. T. Majority rule and collective choice. — California Institute of Technology, Mimeo, 1980.

73. Saari D. G. Susceptibility to manipulation // Public Choice. — 1990. — Vol. 64, No. 1. — P. 21-41.

74. Saari D. G., Merlin V. The Copeland method I: relationships and the dictionary // Mathematical Social Sciences. — 1996. — Vol. 32. — P. 5-38. — DOI: 10.1007/s001990050077.

75. Sato S. On strategy-proof social choice correspondences // Social Choice and Welfare. — 2008. — Vol. 31. — P. 331-343.

76. Satterthwaite M. Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions // Journal of Economic Theory. — 1975. — Vol. 10. — P. 187-217.

77. Schwartz T. Collective choice, separation of issues and vote trading // American Political Science Review. — 1977. — Vol. 71, No. 3. — P. 999-1010.

78. Schwartz T. The logic of collective choice. — New York: Columbia University Press, 1986. — 312 p.

79. Shepsle K., Weingast B. Uncovered sets and sophisticated voting outcomes with implications for agenda institutions. — St. Louis: Center for the Study of American Business, Mimeo, 1982.

80. Simpson P. B. On defining areas of voter choice: Professor Tullock on stable voting // Quarterly Journal of Economics. — 1969. — Vol. 83. — P. 478-490.

81. Slinko A. On asymptotic strategy-proofness of classical social choice rules // Theory and Decision. — 2002. — Vol. 52. — P. 389-398. — DOI: 10.1023/A:1020240214900.

82. Slinko A. On asymptotic strategy-proofness of the plurality and the run-off rules // Social Choice and Welfare. — 2002. — Vol. 19. — P. 313-324.

83. Smith D. A. Manipulability measures of common social choice functions // Social Choice and Welfare. — 1999. — Vol. 16. — P. 639-661.

84. Vasin A. A., Sosina Yu. V., Stepanov D. S. Stability of coalitions in a heterogeneous population // Automation and Remote Control. — 2015. — Vol. 76, No. 6. — P. 1123-1135.

85. Young H. P. Social choice scoring functions // SIAM Journal on Applied Mathematics. — 1975. — Vol. 28. — P. 824-838.

Приложения

Приложение 1. Процедуры агрегирования, не рассматриваемые в работе

В работе рассматриваются процедуры агрегирования, которые для заданного профиля однозначно определяют результат процедуры агрегирования, который является непустым, то есть С(_Р) Е 2А — 0.

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

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

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

Приложение 2. Расширенные предпочтения для случаев 4 и 5 альтернатив

Построим расширенные предпочтения для случая т = 4 альтернатив в предположении, что предпочтения рассматриваемого участника а > b > с > d.

Расширенные предпочтения Лексимин для случая т = 4 (а) > [а, Ь} > {Ь} > [а, с} > [а, Ь, с} > [Ь, с} > (с) > [а, й} > [а, Ь, й} > [Ь, й} >

> [а, с, й} > [а, Ь, с, й} > [Ь, с, й} > [с, й} > [й} Расширенные предпочтения Лексимакс для случая т = 4

[а} > [а, Ь} > [а, Ь, с} > [а, Ь, с, й} > [а, Ь, й} > [а, с} > [а, с, й} > [а, й} > [Ь} >

> [Ь, с} > [Ь, с, й} > [Ь, й} > [с} > [с, й} > Расширенные предпочтения Рискофил для случая т = 4

[а} > [а,Ь} > [а, с} > [а,й} > [а,Ь, с} > [а,Ь,й} > [а,с,й} > [а,Ь,с,й} > [Ь} >

> [Ь, с} > [Ь, й} > [Ь, с, й} > [с} > [с, й} > Расширенные предпочтения Рискофоб для случая т = 4

[а} > [а,Ь} > [Ь} > [а,Ь,с} > [а, с} > [Ь,с} > [с} > [а,Ь,с,ё,} > [а,Ь,й}

> [а, с, й} >> [Ь, с, й} > [а, й} > [Ь, й} > [с, й} >

Построим расширенные предпочтения для случая т = 5 альтернатив в предположении, что предпочтения рассматриваемого участника а>Ь>с>й> е.

Расширенные предпочтения Лексимин для т = 5 [а} > [а, Ь} > [Ь} > [а, с} > [а, Ь, с} > [Ь, с} > [с} > [а, й} > [а, Ь, й} > [Ь, й} >

> [а, с, й} > [а, Ь, с, й} > [Ь, с, й} > [с, й} > > [а, е} > [а, Ь, е} > [Ь, е} >

> [а, с, е} > [а, Ь, с, е} > [Ь, с, е} > [с, е} > [а, й, е} >> [а, Ь, й, е} > [Ь, й, е} >

> [а, с, й, е} > [а, Ь, с, й, е} > [Ь, с, й, е} > [с, й, е} > [й, е} > [е} Расширенные предпочтения Лексимакс для случая т = 5 альтернатив [а} > [а, Ь} > [а, Ь, с} > [а, Ь, с, й} > [а, Ь, с, й, е} > [а, Ь, с, е} > [а, Ь, й}

> [а,Ь,й,е} >

> [а, Ь, е} > [а, с} > [а, с, й} > [а, с, й, е} > [а, с, е} > [а, й} > [а, й, е} > [а, е} >

> [Ь} > [Ь, с} > [Ь, с, й} > [Ь, с, й, е} > [Ь, с, е} > [Ь, й} >> [Ь, й, е} > [Ь, е} >

> [с} > [с, й} > [с, й, е} > [с, е} > [й} > [й, е} > [е} Расширенные предпочтения Рискофил для случая т = 5 альтернатив

[а} > [а,Ь} > [а, с} > [а,й} > [а,е} > [а,Ь,с} > [а,Ь,й} > [а,Ь,е} > [а,с,й} > > [а, с, е} > [а, й, е} > [а, Ь, с, й} > [а, Ь, с, е} > [а, Ь, й, е} > [а, с, й, е} >

> [а, Ь, с, й, е} > [Ь} > [Ь, с} > [Ь, й} > [Ь, е} > [Ь, с, й} > [Ь, с, е} > [Ь, й, е} >

> {Ь, с, й, е} > (с) > {с, й} > {с, е} > {с, й, е} > {й} > {й, е} > {е} Расширенные предпочтения Рискофоб для случая т = 5 альтернатив {а} > {а,Ь} > {Ь} > {а,Ь,с} > {а, с} > {Ь,с} > {с} > {а,Ъ,с,й} > {а,Ъ,й}

> {а, с, й} >

> {Ь, с, й} > {а, й} > {Ь, й} > {с, й} > {й} > {а, Ь, с, й, е} > {а, Ь, с, е} > {а,Ъ,й,е} >

> {а, с, й, е} > {Ь, с, й, е} > {а, Ь, е} > {а, с, е} > {Ь, с, е} >> {а, й, е} > {Ь, й, е} >

> {с, й, е} > {а, е} > {Ь, е} > {с, е} > {й, е} > {е}