Теоретико-игровые модели формирования коалиций и участия в голосовании тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Московский государственный университет им. М.В. Ломоносова

На /іравах рукописи

005532874

Вартанов Сергей Александрович

Теоретико-игровые модели формирования коалиций и участия в голосовании

01.01.09 - дискретная математика и математическия кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

1 г сен т

Москва - 2013

005532874

Работа выполнена на кафедре исследования операций факультета вычислительной математики и кибернетики Московского государственного университета им. М.В.Ломоносова.

Научный руководитель:

доктор физико-математических наук, профессор Васин Александр Алексеевич

Официальные оппоненты:

доктор физико-математических наук, главный научный сотрудник ВЦ РАН им. A.A. Дородницына,

профессор Лотов Александр Владимирович,

доктор технических наук, зав. кафедрой высшей математики факультета экономики НИУ ВШЭ,

профессор Алескеров Фуад Тагиевич

Ведущая организация:

Институт прикладных математических исследований КарНЦ РАН

Защита состоится «4» октября 2013 г. в II00 часов на заседании диссертационного совета Д 501.001.44 в Московском государственном университете имени М. В. Ломоносова, расположенном по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМК, аудитория 685. С диссертацией можно ознакомиться в библиотеке факультета ВМК МГУ. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http://cs.msu.su в разделе «Наука» - «Работа диссертационных советов» - «Д 501.001.44»

Автореферат разослан «30 » августа 2013 г.

Ученый секретарь диссертационного совета В.А. Костенко

Общая характеристика работы

Актуальность темы

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

Для описания первого этапа используются модели эндогенного формирования коалиций. Подобные модели предполагают, что участники выборного процесса (агенты) характеризуются идеальными точками, описывающими их предпочтения на некотором множестве. Из этого же множества участники каждой из коалиций выбирают политику своей коалиции (чаще всего это медиана распределения её сторонников). Чем ближе идеальная точка агента к политике коалиции и чем больше её размер, тем больше выигрыш агента. В литературе, посвященной исследованию формирования коалиций, рассматриваются равновесные по Нэшу наборы стратегий и соответствующие им распределения агентов по коалициям (совокупность таких распределений для всех коалиций задает коалиционную структуру). Важным вопросом является устойчивость коалиционных структур к различным типам коалиционных отклонений (сильное равновесие Р-ядро, квазиустойчивость 2).

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

1 R.J. Aumann. The core of a cooperative game without side payments // Transactions of American Mathematical Society, 1961

2 A. Savvateev. Achieving Stability in Heterogeneous Societies: multi-jurisdictional structures, and redistribution policies // Moscow: EERC, 2005

ствования, вычисления и устойчивости равновесий Нэша в случае неравномерности распределения участников на множестве идеальных точек.

Как только коалиционная структура сформирована, определяется и множество альтернатив, из которых будут выбирать участники выборного процесса. На практике многие такие выборы могут быть сведены к голосованию при наличии двух альтернатив. Несмотря на то, что существует достаточно большое количество процедур голосования 3 4, наиболее распространенным является голосование по правилу простого большинства. Модели такого голосования рассматривались в работах таких авторов, как T.Palfrey, H.Rosenthal 5 6, М. Haan, P. Kooreman 7. В этих работах было показано отсутствие равновесий Нэша в чистых стратегиях при неравных количествах сторонников альтернатив, а также найдены отдельные смешанные равновесия специального вида. Однако изучение множества всех смешанных равновесий Нэша, их количества и свойств в указанных работах не проводилось. В настоящей работе показано, что количество смешанных равновесий в исследуемой модели весьма велико. Это приводит к необходимости рассмотрения вопроса, какие из них наиболее соответствуют реальному поведению при голосовании. Для его решения рассматриваются модели динамики поведения, которые позволяют выделить среди точек равновесия устойчивые и неустойчивые. Актуальным и не исследованным прежде вопросом является устойчивость смешанных равновесий относительно различных динамик поведения (динамика адаптивного поведения, динамика фиктивного разыгрывания). Анализ всех этих вопросов является актуальной научной проблемой.

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

Задачи работы

• определить структуру множества равновесий Нэша теоретико-игровых моделей эндогенного формирования коалиций в случае неравно-

3 Алескеров Ф.Т., Ордешук П. Выборы. Голосование. Партии // М.: Академия, 1995

4 F.T. Aleskerov, V.l. Yakuba, D.S. Karabekyan, R.M. Sanver. On the manipulability of voting rules: the case of 4 and 5 alternatives //Mathematical Social Sciences, 2012. Vol. 64. № 1. pp. 67—73

5 T.R.Palfrey, H.Rosenthal. A strategic calculus of voting// Public Choice, Vol. 41 (1), 1983, pp 7-53

6 T.R.Palfrey, H.Rosenthal. Voter Participation and Strategic Uncertainty // The American Political Science Review, Vol. 79 (1), March 1985, pp. 62-78

7 Haan M., Kooreman P. How majorities can lose the election. Another voting paradox // Social Choice and Welfare, Springer, Vol. 20, 2003

мерного распределения участников по идеальным точкам и исследовать их устойчивость к основным типам коалиционных отклонений;

• для теоретико-игровой модели голосования с двумя альтернативами определить множество смешанных равновесий Нэша в зависимости от параметров модели (численности голосующих, их выигрышей и затрат на участие в голосовании) и исследовать сходимость к найденным смешанным равновесиям динамики адаптивного поведения и динамики фиктивного разыгрывания

Методы исследования.

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

Научная новизна

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

Для модели голосования с двумя альтернативами полностью исследовано множество симметричных смешанных равновесий в зависимости от соотношения затрат и выигрыша от участия в голосовании (относительных издержек). Показано, что при любом их соотношении существуют не более двух таких равновесий. Исследована адаптивная динамика поведения в окрестности подобных равновесий в предположении координированного поведения сторонников каждой из альтернатив.

Для модели голосования с малой численностью участников (два сторонника одной альтернативы, три сторонника другой) полностью исследовано множество всех смешанных равновесий Нэша. Исследована динамика поведения участников голосования в окрестности этих равновесий в отсутствие координации поведении участников.

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

Практическая ценность

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

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

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

Апробация работы. Основные результаты работы докладывались на научных семинарах факультета ВМиК МГУ им. Ломоносова, на XVIII, XIX, XX Международных научных конференциях студентов, аспирантов и молодых ученых «Ломоносов» (МГУ, Москва, 2010, 2011, 2012), научной конференции «Тихоновские чтения» (МГУ, Москва, 2012), на XIII Апрельской международной конференции по проблемам развития экономики и общества (НИУ ВШЭ, Москва, 2012), на Втором Российском Экономическом Конгрессе (Суздаль, 2013), на XIV Апрельской международной конференции «Модернизация экономики и общества» (НИУ ВШЭ, Москва, 2013), а также на научной конференции «Ломоносовские чтения - 2013» (МГУ, Москва, 2013)

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы, состоящего из 66 наименований. Объем работы 179 страниц.

Краткое содержание работы

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

В главе 1 рассматривается модель эндогенного формирования коалиций. Раздел 1.1 содержит формальное описание игры. Множество идеальных точек агентов представляет собой отрезок X = [0,1]. Распределение агентов по идеальным точкам описывается функцией плотности / (х),

х

х € X, Р (х) = / / (х) йх - функция распределения агентов. В работе расо

сматриваются два класса функций плотности / (х) - монотонные и унимодальные с единственным максимумом во внутренней точке X.

Каждый агент выбирает стратегию из множества 1° — {0,1,..., тп},

представляющего собой конечный набор меток: «Коалиция 1», «Коалиция 2», ..., «Коалиция г», ..., «Коалиция т». Выбирая одну из меток, агент присоединяется к соответствующей коалиции, или же воздерживается, не вступая ни в одну из них (что соответствует метке «О»), Набор стратегий всех агентов задает множество непустых коалиций I и набор функций (х) плотности распределения на множестве X агентов, выбравших коалицию i € 7и{0}. Рассматриваются такие наборы стратегий, что каждой коалиции соответствует интегрируемая функция /,• (х) > 0, а Мх) = Кх)-

¿е7и{0}

1

Размер Г; коалиции г пропорционален доле ее сторонников (г, = / /,• (х) <±е),

о

а ее итоговая политика определяется как медиана распределения с плот-р> 1

НОСТЬЮ /г (ж): / (х) (¿Х = / /г (X) (1х. МнОЖеСТВО Хг = {х 6 X \ /г (х) > 0} 0 _

называется носителем коалиции г € /.

Выигрыш агента с идеальной точкой х в случае, если он присоединяется к коалиции г с размером г* и политикой ри равен и (х,гг,р,) = = Я(п) - Ь(\х - рг|), где - возрастающие по своим аргументам

функции. Выигрыш, получаемый агентом в случае неприсоединения ни к одной из коалиций, считается нулевым. Равновесием Нэша является такой набор стратегий агентов, в котором каждый из них присоединяется к той коалиции, в которой его выигрыш максимален:

^г-Ухе Х{ г е Агдшах7.е7и{0}[/ (х, . (1)

Регулярным равновесием Нэша называется такое равновесие, в котором политики всех коалиций различны: \/г,Ц е 7 : г ф э => р^ ф ру Так как нерегулярные равновесия заведомо неустойчивы к объединению коалиций с одинаковыми политиками, далее рассматриваются только регулярные равновесия. Ю.В. Сосиной 8 доказано, что структура регулярного равновесия описывается следующим утверждением:

Если Ь (х) - выпукла, то в регулярном равновесии Нэша каждой коалиции г 6 I соответствует единственный интервал Xi С X, такой, что Ух 6 Х( ¡1 (х) = / (х) и Ух 6 X \ Х{}{ (х) = 0, где Х{ - замыкание X,-.

Таким образом, множество X в регулярном равновесии разбивается на конечное число непересекающихся интервалов Х{, г е I, и множество Хо> где Х{ с точностью до множества граничных точек совпадает с носителем

8 Сосина Ю.В. Эндогенное формирование политических структур и исследование их устойчивости // Препринт '\УР7/2004/04, Серия \УР7 «Теория и практика общественного выбора», Москва, ГУ ВШЭ, 2004

коалиции г, а Х0 соответствует множеству игроков, воздержавшихся от присоединения к коалициям.

Пусть коалиции упорядочены по расположению на множестве X слева направо. Если с - граничная точка, разделяющая носители коалиций г и г + 1, то в равновесии выигрыш агента с идеальной точкой с одинаков в случае его присоединения как к г, так и к г+1. Соответствующее равенство называется уравнением безразличия граничного агента, оно имеет вид

Я (п) - Ь (с- я) = Я (гт) - Ь (р{+1 - с) . (2)

Утверждение 1.1. Пусть функция плотности /(х) унимодальна с единственным максимумом в точке М € [0,1]. Тогда в любом равновесии Нэша множество Х0 либо пусто, либо представляет собой объединение интервалов вида Х0 = (0, с£) и (с% 1), где с% с°я е [0,1].

В случае монотонно возрастающей плотности распределения множество Х0 может быть интервалом, который лежит левее всех коалиций (Сд = 1), в случае монотонно убывающей - правее всех коалиций (с\ - 0).

Для упрощения записи далее используются следующие обозначения: \]ь (с,г) - Я(г)-Ь(с-рь (с,г)) - выигрыш граничного агента с идеальной точкой с в лежащей слева от него коалиции, имеющей размер г и политику ?ь (с, г) = Г"1 (Г (с) - |); иа (с, г) = Я (г) - Ь (рд {с, г)-с)- выигрыш граничного агента с идеальной точкой с в лежащей справа от него коалиции, имеющей размер г и политику рд(с,г) = F-1(F(c) + §). В дальнейшем предполагается, что функции иь(с,г) и ия (с, г) вогнуты по г и по с. Это верно при равномерной плотности распределения f (х) = 1. В более общем случае справедливо следующее утверждение.

Утверждение 1.2. Функция иь (с, г) вогнута по г при любом с. Для вогнутости по г функции и^с, г) достаточно, чтобы Ухьх2 € [0,1], таких что XI > х2, выполнялось неравенство:

Ь" (XI - х2) > / (л) (3)

V (Ж1 - хг) ~ / (яг)

Для вогнутости по с функций V£ (с, г), С/д (с, г) достаточно, чтобы \/хи хч б [0,1], таких что хх > х2, выполнялось неравенство:

Ь"(х1-х2) (4)

Ь,{х1-х2)~ /Ы(/(х2)-/(х г))2

Для степенной функции Ь(х) = хк, к > 2 и линейной функции /(•) оба условия выполнены. В общем случае необходимым условием выполнения (3) является выполнение неравенства ^ (1п I,' (х)) > £ (1п (х)) для

любого х е [0,1], то есть Ь{-) должна быть логарифмически "более выпукла чем Р (■). Достаточным условием выполнения (4) является выпуклость функции (что верно, например, для любой вогнутой функции /(•))■ Пусть в регулярном равновесии присутствуют две соседние коалиции с носителями Х^ = (а,с), Хд = (с,Ь) и размерами г/, и гд, соответственно. Согласно (2), размеры этих коалиций связаны равенством:

иь{с,г£) = иа{с,г11) (5)

Его можно рассматривать как уравнение относительно гд при фиксированном гь и как уравнение относительно Г£ при фиксированном гд. Пусть Гд (с) = Агдтахг11д (с, г), (с) = АгдтахгиI (с, г). Вогнутость по г функции С7д (с, г) гарантирует, что уравнение (5) имеет не более двух решений относительно гд, расположенных по разные стороны от точки Гд(с). Обозначим их гдт(с,г/,), Гд01 (с,гь). Коалицию размера г™п (с,г^) < Гд(с) (гдаг (с,гь) > Гд (с)) с левой границей в точке с будем называть минимальной (максимальной) относительно предыдущей, для неё (с, г) > 0 (< 0). Аналогично, вогнутость по г функции {/¿(с,г) гарантирует, что уравнение (5) имеет не более двух решений относительно г^, расположенных по разные стороны от точки (с): меньшее г™" (с,гд) и большее г™х (с,гд). Коалиция размера г™" (с, гд) < г£ (с) (г"шх (с, гд) > г\ (с)) с правой границей в точке с называется минимальной (максимальной) относительно последующей, для неё ^ (с, г) > 0 (< 0). Таким образом, любому равновесию Наша, состоящему из п последовательно расположенных коалиций, соответствует двоичный вектор Т = (ГЬГ2,... ,ТП), определяющий тип каждой последующей коалиции относительно предыдущей: Т1 = 0, если коалиция г е {1,...,тг} минимальна относительно предыдущей, и Т* = 1, если она максимальна. Вектор Т называется типом равновесия Нэша.

В разделе 1.2 предложен следующий метод расчета всевозможных равновесий Нэша. По заданному размеру п первой коалиции размеры г* (гьТ) всех последующих коалиций в соответствии с типом Т определяются однозначно с помощью уравнения (5). Множество допустимых значений п - полуинтервал (0,Гд(0)], если = 0, либо полуинтервал (гд(0),1], если

п

Т\ = 1. Рассматривая суммарный размер коалиций: ^(п) = ]Сг;(г1,Т) и

¿=1

решая уравнение (п) = 1 на множестве допустимых значений г и можно определить все коалиционные структуры, являющимися равновесиями Нэша заданного типа Т.

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

ля этих игроков, Х0 = (0,^_1(г0)) - множество их идеальных точек. В этом случае тип и размер первой коалиции определяются однозначно: она максимальна относительно предыдущей, то есть Т\ = 1 и п(г0) -тТ1^'1 Ы,0). Каждому возможному равновесию Нэша соответствует вектор Т = (1,Т2,...,ТП), определяющий тип каждой последующей коалиции. Следовательно, для поиска равновесий фиксированного типа Т с непустым множеством игроков, воздержавшихся от присоединения к коалициям, необходимо решить уравнение £ г* (г0) Г) = 1 - г0.

Утверждение 1.4. 1) В равновесии Нэша размеры гь, гл соседних коалиций связаны неравенством г#п{с,гь) < гь < г%ах (с, гД где с - их общая граничная точка.

2) Функция г%'п (с, гь) при каждом фиксированном значении с унимодальна по гь и достигает максимума г{ (с) в точке г*ь (с).

3) Функция г^х (с, гь) при каждом фиксированном значении с унимодальна по гь и достигает минимума (с) в точке г"ь (с).

В общем случае (п) не является монотонной функцией. Однако, в равновесии, состоящем только из минимальных коалиций, монотонность функции % (п) имеет место. Пусть 1™п (п) - суммарный размер п минимальных коалиций, в зависимости от размера п первой из них. Справедливо следующее утверждение, касающееся существования равновесий из минимальных коалиций.

Утверждение 1.5. Если 1™п (0)) > 1, то существует единственное равновесие Нэша из п минимальных коалиций. Более того, существует такое п0, что условие 1™п (г*н (0)) > 1 выполнено для всех п > п0.

В разделе 1.3 исследуются условия устойчивости для равновесий Нэша. Из Утверждения 1.5 следует, что заведомо существуют равновесия, состоящие из большого числа мелких коалиций. Однако малый размер коалиций может обуславливать стремление их участников к объединению. Равновесие называется устойчивым к локальному объединению, если невозможно образование новой коалиции из двух существующих соседних коалиций, так, чтобы всем участникам формирующейся коалиции было выгодно объединение. Иными словами, для любой пары соседних коалиций г и г + 1 с носителями Х1 = ь^), Хш = (^,с,-+г) и политиками ри рм: ЗхеХ1: и (х,г,р) < и (х,п,рг) или Эх <Е Х1+1 : и (х,г,р) < С/(х.п+ьрт),

где г = / /(x)dx - размер объединенной коалиции, р - ее политика:

Й-1

/ /(ж)с£с = / /(х)(1х.

Р

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

иК (Сг-1,п + П+1) < 1/ц (а- 1!Г¿) Рь (с, Ц , Г; + Г;+1) < иI (сг+1

Пусть в равновесии присутствует пара соседних коалиций, имеющих носители Хь — (а, с) и Хц = (с, Ь). Если правая коалиция является минимальной, то из условия (6) следует необходимое условие устойчивости:

и к (а, ть + гГ1 (с (а, г£), < <7д (а, гь) (7)

где гь - размер левой коалиции, а с{а,г£) = + гь). Аналогичное

условие справедливо и для случая минимальности левой коалиции:

% (Ь, гц + г™п (с (Ь, гл), гд)) < VI (Ъ, Гц) (8)

где гд - размер правой коалиции, а с(Ь,гд) = F_1(F (Ь) - гд).

Пусть г^ (а) (гд (Ь)) - размер левой (правой) коалиции, при котором условие (7) (соответственно, (8)) выполняется как равенство.

Утверждение 1.6. Пусть ¡{х) унимодальна с максимумом в точке М е [0,1] . Для того чтобы равновесие Нэша было устойчивым к локальному объединению, необходимо и достаточно, чтобы для каждой пары соседних коалиций с носителями Хь = (а, с) и Хц = (с, Ь) выполнялось одно из условий:

1) хотя бы одна из них является максимальной;

2) если Ь < М , то размер гь левой коалиции превышает пороговое значение гь (а);

3) если а > М , то размер гд правой коалиции превышает пороговое значение гд (Ь);

4) если М е (а, Ь) , то либо гд > гд (Ь), либо гь > гь (а).

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

Утверждение 1.7. Пусть /(х) монотонно возрастает. Равновесие, состоящее только из минимальных коалиций, устойчиво к локальному

9 Степанов Д.С. Модель эндогенного формирования коалиционных структур: диссертация на соискание степени кандидата физико-математических наук: 01.01.09.-Москва, 2011,- 151 с.

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

В разделе 1.3.2 исследуется устойчивость равновесий к расколу входящих в него коалиций. Равновесие называется устойчивым к расколу, если не существует новой коалиции, являющейся собственным подмножеством одной из существующих коалиций, и обеспечивающей большие выигрыши всем своим членам. Д.С. Степановым 10 доказано, что если плотность распределения /(х) монотонна, Ь{-) и Я(-) дважды дифференцируемы, Ь{-) выпукла, Д( ) вогнута, !/'(•) возрастает, а Д"( ) убывает, то любое равновесие Нэша устойчиво к расколу.

В работе получено следующее обобщение этого результата.

Теорема 1.1. Пусть плотность распределения /(х) унимодальна и достигает максимума в точке М е [0,1], Ь(-) и Я(-) дважды дифференцируемы, £(■) выпукла, /?(■) вогнута, а #"(•) убывает. Тогда любое

равновесие Нэша устойчиво к расколу.

Далее в работе проводится анализ условий, накладываемых Теоремой 1.1 на функцию Л(-). Следующие утверждения показывают, что вогнутости функции Д(-) недостаточно для устойчивости к расколу. В то же время условие об убывании Д"(-) не является необходимым, и существуют вогнутые функции Д(-), для которых любая равновесная структура устойчива к расколу, но Д"(-) не убывает. Далее предполагается, что распределение игроков равномерно, а Ь(х) линейна (Ь(х) = х).

Утверждение 1.8. Коалиция размера г устойчива к расколу тогда и только тогда, когда

Л(х)-у<Л(г)-^«е(0,0. (9)

Если Д(-) не является непрерывно дифференцируемой, то справедливо следующее утверждение, где (х), я'+ (х) - производные слева и справа

в точке X. з

Утверждение 1.9. Пусть Я (•) вогнута. Если \/х е (0, §) П+ (х) < 5 либо \/х 6 (0, §) (х) > \ , то коалиция размера г устойчива к расколу. Иначе для устойчивости к расколу необходимо и достаточно, чтобы условие (9) выполнялось для х*, такого что § е [Я'_ (х*), Я+ (х*)] . В главе 2 рассматриваются модели участия избирателей в голосовании с

10 Степанов Д.С. Модель эндогенного формирования коалиционных структур: диссертация на соискание степени кандидата физико-математических наук: 01.01.09. - Москва, 2011. - 151 с.

двумя альтернативами (кандидатами). Избиратели делятся на две группы в зависимости от того, какую из альтернатив они поддерживают. Каждая группа характеризуется своей численностью (в первой группе - Ni участников, во второй -N2, N2 > Nx). Обозначим с,-, ¿ = 1,2, затраты избирателя из группы i на участие в выборах (одинаковые для всех членов группы). Если побеждает альтернатива г, то её сторонники получают выигрыши щ, а если побеждает другая альтернатива, то столько же теряют. В случае равенства голосов выигрыш любого участника равен нулю. Взаимодействие избирателей описывается в виде игры в нормальной форме с Ni + N2 игроками.

Равновесием Нэша в рассматриваемой модели является такая ситуация, что никому из избирателей невыгодно индивидуально изменять свое решение об участии в голосовании при фиксированном поведении остальных участников. Если для некоторой группы относительные издержки w{ = f- > 1, то для любого её участника неучастие в голосовании является доминирующей стратегией. Далее гу» G (0,1), г = 1,2.

В исследуемой модели равновесие Нэша в чистых стратегиях существует тогда и только тогда, когда Nx = N2 11 12. В этом случае единственным равновесием является ситуация, при которой все избиратели принимают участие в голосовании. При Nx < N2 равновесий в чистых стратегиях не существует.

Пусть рк - вероятность участия в голосовании fc-го избирателя первой группы, a qi - вероятность участия в голосовании ¿-го избирателя второй группы. Пусть р = (рк,к е Ai) и q = (qi,l G Л2), где А - множество сторонников альтернативы г, г = 1,2. Тогда количества п\ и п2 голосующих сторонников первой и второй альтернатив соответственно - случайные величины, зависящие от р и q соответственно, как и п\ - количество голосующих сторонников первой альтернативы, за исключением сторонника к, п'2 - количество голосующих сторонников второй альтернативы, за исключением сторонника I. Вероятности участия избирателей из первой и второй групп во вполне смешанном равновесии удовлетворяют системе уравнений:

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

11 Т.R.Palfrey, H.Rosenthal. A strategic calculus of voting // Public Choice, Vol. 41 (1), 1983, pp 7-53

12 Haan M„ Kooreman P. How majorities can lose the election. Another voting paradox Ц Social Choice and Welfare, Springer, Vol. 20, 2003

/ P (n\ + 1 = П2) + P (nf = n2) \p (п'2 +1 = ni) + p (ni; = m)

= tiJi, к € Ai — w2,le Аг,

(10)

совании с вероятностью д, а избиратель из первой группы р. Для таких равновесий система (10) приобретает вид:

\ф2 (р,я) = '

где:

Фі (р, = 15 1 - р)^1 (су\1 - + с£У+1( 1 -

к=О

Ф2 (р,,) = £ (і - д)^*"1 (С^А 1 - Р)М1~к + - Р)*-к-1)

к=О

Функции Фі (р,д) и Ф2(р, д) являются унимодальными по каждой из двух переменных р, д при фиксированном значении другой. Таким образом, уравнение Фі(р, д) — ги имеет не более двух решений относительно р при любом значении q, при этом меньшее из них (рі(д)) расположено на участке возрастания Фі(р,<?), а большее (ря(?)) - на участке убывания. То же справедливо и для решений ді(р), <?я(р) уравнения Ф2(р,д) = гс/ относительно д при фиксированном р. Все возможные симметричные смешанные равновесия подразделяются на четыре типа в зависимости от того, пересечением каких именно функций рі(д) и <^(р), г,з Є {Ь, Я} они являются. Равновесие, образованное пересечением р¡(д) и ф(р), называется ^-равновесием (равновесием типа у). Пусть й = пііпшахФі (р, д),

/2(д) = тахФ2(р,д), а д?псг - единственный корень уравнения аФга(1'9) = 0, р

ро = аг<?тахФі (р, 1 - р), <?о = 1 - Ро-р

Теорема 2.1. Яри равных относительных издержках (юі = = ю) существует не более двух смешанных симметричных равновесий со стратегиями участников первой и второй групп р* и д* соответственно.

Если 0 < ги < й> , то существует ровно два равновесия (рн^Чнь) и ІРІю ЧІн)> где р*Н1 = 1 - рін = 1 - <?Ья и р*яс > р1н, имеющие типы НЬ и ЬН соответственно.

Если й < -и: < ¡2 (яіпсг) , то существует ровно два равновесия (р-,д?), і Є {НН,Ы}, причем ро Є (рЬ?.рЫ " 9о Є {Чнюйь) ■ Эти равновесия имеют типы НН и ЬЬ соответственно, и = 8Фі(^'ч>) = 0.

Если I > и> > І2{я'іпсг)' то существует единственное равновесие (р*нн, Янн) типа НН, для которого также = »'(уЫ = 0.

- с вероятностью (11)

Исследованию вопросов существования и количества несимметричных равновесий посвящен раздел 2.3. В разделе 2.3.1 описывается множество частично смешанных равновесий, в которых часть избирателей использует чистые стратегии. Пусть Аг - множество сторонников кандидата г, использующих чистую стратегию «не голосовать», а использующих стратегию «голосовать» - АКаждое частично смешанное равновесие характеризуется четырьмя натуральными числами - (ЛГ^, Л^-описывающими мощности множеств Л+, А[, и А2 соответственно. Оставшиеся игроки используют смешанные стратегии р <5 П^1-^^1), <? е )> где П" - стандартный п-мерный симплекс. Всякий набор (р,д), входящий в частично смешанное равновесие при некоторых удовлетворяет системе равенств

р (й* = п2) + Р (п[ + 1 = п2) = V), г е АД (ЛГ и А^) (12а)

Р (п{ = щ)+Р (п{ + 1 = щ) = ш, з € АД (А2 и А+) (12Ь)

Случайные величины щ, описывающие количество голосующих сторонников каждого из кандидатов, представляют собой сумму постоянного числа Л^ участников, применяющих чистую стратегию голосования, и случайной величины п™ - количества голосующих участников из числа применяющих смешанные стратегии, г = 1,2. Аналогичным свойством обладают и случайные величины пДля тех игроков, которые применяют чистые стратегии, должны быть выполнены условия оптимальности выбранных ими стратегий:

' Р(п1 = п2) +Р(п1 + 1 = п2) <-и) (13а)

Р (щ = п2) + Р (щ - 1 = п2) > V) (13Ь)

' Р(п2 = щ) + Р (п2 + 1 = пг) < ги (13с)

Р(тг2 = + Р{п2- 1 = щ) >ги (13с1)

Неравенство (13а) описывает оптимальность стратегии «не голосовать» для игроков из А1, (13Ь) - оптимальность стратегии «голосовать» для игроков из А+. Аналогично, (13с) и (13с1) описывают оптимальность выбранных стратегий для игроков из А¿Г и А2 соответственно. Очевидно, что пара неравенств (13а) и (13с1) не может выполняться одновременно, как и пара (13Ь) и (13с). Таким образом, не существует таких частично смешанных равновесий, что в них одновременно N1 ф 0 и Щ Ф 0 (или одновременно Щ Ф 0 и Ф 0).

В разделе 2.3.2 проводится полное исследование множества всех смешанных равновесий для случая малого количества участников голосования: М = 2, N2 = 3. Пусть и>2)з = + ч/З)2- ^2,2 = 3/4- Каждая система вида (12) при ЛГх = 2 и ЛГ2 = 3 имеет не более двух решений при любом значении ги. Тип каждого равновесия определяется, таким образом, набором г), где индекс г характеризует, какому из решений системы (относительно р) (12) - большему (Я), меньшему (Ь) или единственному (и) - соответствует данное равновесие.

Утверждение 2.11. В исследуемой модели существует шесть или семь частично смешанных равновесий. В зависимости от того, в какой из интервалов - И^ = (0,ги2,з). = (г£2,3,^2,2) или №3 = (ш2,2,1)- попадает значение относительных издержек ги, типы равновесий будут различаться. Если го е И7!, то возможны равновесия типов: (1,0,0,0, Л), (2,0,0,0, С/), (0,0,0,1, Я), (0,0,1,0, и), (0,0,1,1,17), (0,0,2,0, и), (0,0,2,1, С/). Если ги £ 1У2, то их типы: (0,1,0,0, Я), (2,0,0,0, и), (0,0,0,1, Ь), (0,0,1,0, и) (0,0,1,1,г7), (0,0,2,0, г7), (0,0,2,1, и). Если же ги е то это равновесия типов (0,1,0,0,Я), (0,0,0,1, Ь), (0,0,0,2, и), (0,0,2,0, и), (0,0,2,1, и) и (0,1,0,1 ,и).

Помимо уже исследованных симметричных смешанных равновесий возможно также существование несимметричных равновесий, в которых у двух участников из второй группы совпадают стратегии.

Утверждение 2.12. При ги > ги2,з существуют вполне смешанные несимметричные равновесия такие, что ф = <?з- При этом возможен как случай рг = рг, так и случай рхфръ-

Глава 3 посвящена исследованию устойчивости и свойств смешанных равновесий, а также построению и анализу альтернативного механизма голосования. В разделе 3.2.1 рассматривается модель адаптивного поведения, описывающую динамику смешанных стратегий избирателей в предположении их координированного поведения. Уравнения динамики для этой модели имеют вид:

/Я*) =Р(1-Р)(Ф1(Р.9)-«') (14ч

Симметричные смешанные равновесия являются неподвижными точками системы дифференциальных уравнений (14). Для исследования их устойчивости используется линейное приближение.

Утверждение 3.1. Пусть численность первой группы - ЛГЬ второй группы - и>- пороговое значение относительных издержек. Если ги <

ю, то при

равновесию типа ЬН соответствует устойчивый фокус системы (14), а равновесию типа НЬ - неустойчивый фокус. В противном случае ЬН-равновесию соответствует устойчивый, а НЬ-равновесию -неустойчивый узел. Если м > и), то равновесию типа НН соответствует устойчивый, а равновесию типа ЬЬ - неустойчивый узел системы

В разделе 3.2.2 рассматривается модель адаптивного поведения без координации избирателей для N1 — 2, N2 = 3. Она записывается в виде системы дифференциальных уравнений (здесь рі (і), qj (і) - смешанные стратегии участников первой и второй групп):

где: фц(р,д) = Р{п\ = га2) + Р(п[ + 1 = п2) - ги - разность ожидаемых выигрышей г-го участника первой группы в случае его участия и неучастия в голосовании, - аналогичная величина для j-гo участника второй

группы.

Утверждение 3.2. Всякое смешанное равновесие не является устойчивым по линейному приближению для модели (15).

Траектории, начинающихся из окрестности любого из равновесий, могут вести себя по-разному. Так, например, на рисунке 1 приведен пример двух траекторий решений системы (15) для начальных значений из окрестностей симметричного равновесия (р*,<?") типа НЬ. Одна из траекторий начинается в точке -I- £?', где э - собственный вектор, соответству-

ющий положительному собственному значению якобиана. Эта траектория покидает окрестность симметричного равновесия и со временем образует предельный цикл вокруг равновесия типа (0,0,1,0, и). Другая траектория, приведенная на рис. 1, также начинается из окрестности (р*,д*) такой, что рх = Р2, <?1 = 92 = Яз- Эта траектория сходится к исходному равновесию. Траектория, исходящая из окрестности равновесия типа (0,0,1,0, и), сходится к точке (0,0,1,1,0), не являющейся равновесием статической модели. Таким образом, в модели адаптивно-подражательного поведения с полностью независимым поведением участников все равновесия неустойчивы. Однако если допустить возможность координации между участниками каждой из групп, то в получающейся симметричной модели ровно одно равновесие является асиптотически устойчивым.

(14).

Рі (і) =Рі{ 1 - Рі) Фіі(р,9), г = 1,2; Чі (*) = <?і (1 - 9і) Ф20, = 1,2,3

(15)

Рис. 1. Вид траекторий адаптивного поведения, начинающихся из окрестности симметричного равновесия типа НЬ (сплошная и штрих-пунктирная линии) и равновесия типа (0,0,1,0, и) (пунктирная линия)

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

В разделе 3.3 рассматриваются возможности применения исследованной модели для прогнозирования результатов голосования для различных значений относительных издержек и численностей сторонников каждого из кандидатов, а также оценки вероятности победы каждого из кандидатов и степень влияния каждого из избирателей на исход голосования. Проведенные численные расчеты показывают, что для любых численностей избирателей симметричные равновесия типов НН, ЬЬ и НЬ являются «парадоксальными»: в них вероятность победы альтернативы с меньшей

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

Развитию моделей голосования посвящен раздел 3.4. Рассмотрен механизм последовательного голосования при наличии информации о результатах голосования предшествующих избирателей. Последовательность голосования определяется случайным образом и не зависит от того, к какой группе принадлежит избиратель. Вначале из (Л^ + N2) избирателей выбирают первого голосующего, затем из оставшихся (Ni + iV2 — 1) выбирают второго, и так далее. Порядок голосования избирателей описывается вектором v = («1,г>2,...,г>лг1+дг2), где Vk — 0, если fc-тым получил право проголосовать избиратель из первой группы, и и* = 1, если это право получает избиратель из второй группе. Каждый избиратель может либо проголосовать за свою альтернативу либо не участвовать в выборах. Участие в выборах требует от избирателя группы г издержек с,, в случае победы "своего"кандидата он получает выигрыш щ, а в случае проигрыша - столько же теряет. Предполагается, что в обеих группах относительные издержки избирателей Wi = £ е (0,1),г = 1,2. Предполагается, что fc-тому голосующему известна следующая информация: Ni(k), N2(k) - сколько избирателей каждой группы имело возможность проголосовать перед ним, ni (к), п2 (к) - сколько из них действительно проголосовали. Стратегия избирателя определяет, примет он участие в голосовании или нет, в зависимости от того, как проголосовали предыдущие избиратели. Следующие утверждения определяют поведение избирателей в совершенном подыгровом равновесии (СПР).

Утверждение 3.6. В СПР k-тый игрок (k = l,...,Ni + N2) голосует тогда и только тогда, когда щ {к) + Ni - Ni (к) - (jij (к) + Nj - Nj (к)) е {0; 1}, где i - номер группы, к которой принадлежит этот игрок, a j -номер другой группы.

Как следует из утверждения 3.6, в голосовании принимают участие только те избиратели, чей голос является решающим в предположении, что все голосующие после них избиратели также примут участие в голосовании.

Утверждение 3.7. 1) Если N1 = N2, то в СПР все избиратели голосуют.

2)Если Ny < N2, то в СПР всегда побеждает альтернатива 2. Ни один избиратель из первой группы не принимает участия в голосовании, а в группе 2 голосует не более N\ + l избирателей. При этом голосуют

только те избиратели, для которых

77.2 (АО + N2-N2 (к) = т - щ (fe) + 1

В случае равных численностей сторонников обеих альтернатив ситуация, соответствующая СПР, совпадает с равновесием Нэша в чистых стратегиях модели с одновременным голосованием. Однако при разной численности в СПР модифицированной игры, в отличие от смешанного равновесия исходной, не возникает парадокса: всегда побеждает кандидат с большим числом сторонников. При этом для победы кандидата, как правило, не требуется участия всех его сторонников. Пусть все возможные порядки голосования равновероятны, тогда среднее число п2(МъЫ2) голосующих участников группы 2 имеет вид, приведенный на рисунке 2.

Рис. 2. Ожидаемые численности голосующих при равной вероятности всех порядков голосования в зависимости от количества Ni сторонников первой и N2 второй альтернатив

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

Утверждение 3.8. СПР в игре с q > 0 совпадает с СПР при q = О тогда и только тогда, когда:

q < min {wi,w2,1 - tfüh, 1 - Уодг}, если N2 > Ni> 1; q < min {iüi, VJ2,1 - »г}» если N2 > Ni = 1; q < min {wi, w2,1 - 1 - если N2 = N1 > 1.

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

з.?

3.3

-N, = 14

--N, = 15 — —N, = 16

13

14 15 IS N.

Основные результаты работы, выносимые на защиту

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

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

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

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

Благодарности

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

По теме диссертации опубликованы следующие работы

[1] Вартанов С.А. Модель электорального поведения // Математическая теория игр и ее приложения, том 5, выпуск 1. - Петрозаводск: КарНЦ РАН, 2013 - С. 3-26.

[2] Вартанов С.А. Об устойчивости к расколу равновесий в модели эндогенного формирования коалиций // Математическая теория игр и ее приложения, том 4, выпуск 1. - Петрозаводск: КарНЦ РАН, 2012. - С. 3-20.

[3] Вартанов СЛ., Сосина Ю.В. О структуре равновесий Нэша и их устойчивости к локальному объединению в модели эндогенного формирования коалиций // Математическое моделирование, том 25, №4, 2013. - С. 44-64.

[4] Вартанов СЛ., Васин A.A., Сосина Ю.В. Об устойчивости равновесий в модели эндогенного формирования коалиций // XIII Международная научная конференция по проблемам развития экономики и общества. В четырех книгах. Книга 1. - М.: НИУ ВШЭ, 2012. - С. 203-215.

[5] Вартанов С.А. Свойства равновесий в коалиционных играх с неравномерным распределением агентов // Сборник тезисов XVII международной научной конференции студентов, аспирантов и молодых ученых "Ломоносов-2010"; секция "Вычислительная математика и кибернетика: Москва, МГУ им. М.В.Ломоносова, 12-15 апреля 2010 года".-М.: МАКС Пресс, 2010. - С. 29-30

[6] Вартанов С.А. О локальной устойчивости равновесий в модели эндогенного формирования коалиций // Сборник тезисов XVIII международной научной конференции студентов, аспирантов и молодых ученых "Ломоносов-2011"; секция "Вычислительная математика и кибернетика: Москва, МГУ им. М.В.Ломоносова, 11-15 апреля 2011 года".- М.: МАКС Пресс, 2011. - С. 120-121

[7] Вартанов С.А. О структуре равновесий Нэша и их локальной устойчивости в модели эндогенного формирования коалиций // Сборник тезисов XIX международной научной конференции студентов, аспирантов и молодых ученых "Ломоносов-2012"; секция "Вычислительная

математика и кибернетика: Москва, МГУ им. М.В.Ломоносова, 9-13 апреля 2012 года".- М.: МАКС Пресс, 2012. - С. 43-44

[8] Вартанов СЛ. Исследование равновесий в модели эндогенного формирования коалиций // Сборник тезисов лучших дипломных работ 2010 года,- М.: МАКС Пресс, 2010. - С. 46-47

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

Напечатано с готового оригинал-макета

Подписано в печать 23.07.2013 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 230.

Издательство ООО "МАКС Пресс" Лицензия ИДЫ 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.

Московский государственный университет им. М.В. Ломоносова

На правах рукописи

04201361203

Вартанов Сергей Александрович

Теоретико-игровые модели формирования коалиций и участия в

голосовании

Специальность 01.01.09 (дискретная математика и математическая кибернетика)

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

Научный руководитель: доктор физико-математических наук,

профессор Васин Александр Алексеевич

Москва 2013

Оглавление

Введение 3

Обзор литературы 11

Глава 1. Модели формирования коалиций. 22

1.1. Постановка задачи и формальное описание модели 22

1.2. Множество равновесий Нэша в зависимости от числа коалиций 27

1.3. Устойчивость равновесий Нэша 39

1.3.1. Устойчивость к локальному объединению 39

1.3.2. Устойчивость к расколу 48 Глава 2. Модели участия в голосовании. Множество равновесий в смешанных 57 стратегиях.

2.1. Описание модели, существование равновесий в чистых стратегиях 57

2.2. Симметричные смешанные равновесия 58

2.3. Несимметричные равновесия 97

2.3.1. Частично смешанные равновесия 99

2.3.2. Полное описание множества смешанных равновесий для малой 103 численности участников Глава 3. Модели участия в голосовании. Устойчивость и свойства смешанных 125

равновесий, анализ альтернативного механизма голосования.

3.1. Введение и постановка задачи 125

3.2Локальная устойчивость частично смешанных равновесий 126

3.2.1. Модель адаптивного поведения при координации избирателей 126

3.2.2. Модель адаптивного поведения без координации избирателей 128

3.2.3. Модель фиктивного разыгрывания 139

3.3. Ожидаемые исходы голосования при равновесном поведении 145

3.3.1. Об оценке относительных издержек 145

3.3.2. Ожидаемый исход голосования и выборные парадоксы 146

3.4. Альтернативный механизм голосования 159 Заключение 172 Список литературы 173

Введение

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

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

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

к политике коалиции и чем больше размер этой коалиции, тем больше выигрыш агента. Итоговая политика коалиции чаще всего определяется как идеальная точка медианного её члена, так как медиана получит большее количество голосов членов коалиции при сравнении с любой другой альтернативой. Кроме того, в некоторых случаях такое определение итогового выбора коалиции является эффективным с точки зрения максимизации суммарного выигрыша её участников ([63]).

В литературе, посвященной исследованию формирования коалиций, рассматриваются равновесные по Нэшу наборы стратегий и соответствующие им распределения агентов по коалициям (совокупность таких распределений для всех коалиций задает коалиционную структуру). В частности, исследованию равновесных по Нэшу структур посвящены работы ([8-9], [40-41], [45], [63-64]). Близким понятием является понятие структуры, устойчивой к индивидуальным отклонениям [40-41].

Важным вопросом также является устойчивость коалиционных структур (не обязательно равновесных) к различным типам коалиционных отклонений. В качестве одного из возможных понятий коалиционной устойчивости в литературе рассматривается понятие сильного равновесия, введенного в [5]. Под сильным равновесием понимается ситуация, в которой не существует такого множества участников, что всем им выгодно одновременно изменить свои стратегии. Как правило, однако, рассматриваются более слабые понятия устойчивости (коалиционная устойчивость, Р-ядро, квазиустойчивость [40-41], локальная устойчивость и слабое коалиционное равновесие [63-64], устойчивость к объединению при условии свободы перемещений, stability under free mobility, SFM [9]). Настоящая работа посвящена анализу равновесий Нэша и соответствующих им коалиционных структур, а также их устойчивости к

некоторым видам коалиционных отклонений (расколу и объединению существующих коалиций), рассмотренных в [63-64].

Во многих работах рассматриваются модели формирования коалиций, допускающие возможность побочных платежей (например, [2-3], [17-19], [26], [29]). В то же время существует широкий спектр приложений, в которых предположение о возможности побочных платежей не соответствует сути модели. В основном это модели формирования политических партий, которые часто основываются лишь на самоорганизации его участников без участия каких-либо «центров силы», заинтересованных в компенсации издержек отдельным агентам с целью реализации определенной коалиционной структуры. В настоящей работе рассматривается модель формирования коалиций, не допускающая побочных платежей.

Таким образом, модель, рассматриваемая в главе 1 настоящей работы, обладает следующими отличительными признаками. Это модель эндогенного формирования коалиций в большом неоднородном множестве участников, не допускающая побочных платежей участникам коалиций. Основным объектом исследования являются равновесия Нэша - ситуации, в которых каждый участник присоединяется к той коалиции, в которой имеет максимальный выигрыш. Кроме того, в равновесии некоторые участники могут воздерживаться от присоединения, если это дает им больший выигрыш, чем участие в любой из коалиций. Множество идеальных точек предполагается одномерным (отрезок [0, 1]), при этом в качестве политики каждой коалиции выбирается идеальная точка её медианного члена. Выигрыш каждого ее сторонника описывается функцией общего вида, возрастающей по размеру коалиции и убывающей по расстоянию от идеальной точки сторонника до политики коалиции.

Подобные модели были рассмотрены в работах [45], [57], [63-64]. В данных работах остались нераскрытыми вопросы структуры множества равновесий, а также их устойчивости в случае неравномерности распределения участников на множестве идеальных точек. Под исследованием структуры множества равновесий понимается определение количества коалиций в равновесной структуре, зависимости размера коалиций от плотности распределения агентов, а также разработка алгоритма расчета всевозможных равновесных коалиционных структур. В Главе 1 настоящей диссертации решаются эти задачи, а также исследуется устойчивость равновесий к двум основным типам изменения коалиционной структуры: расколу и объединению существующих коалиций.

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

Существует большое количество процедур голосования. Подробно о них написано в работах [4], [49-50]. Наряду с правилами простого или относительного большинства, можно привести в качестве примеров правила Борда, одобряющего голосования и процедуры голосования Хара и Нэнсона. На практике наиболее распространенным из таких правил является голосование по правилу простого большинства.

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

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

Низкая явка может привести к победе альтернативы с меньшим уровнем поддержки (парадокс голосования, см. [32]). Схожие проблемы можно обнаружить и в других ситуациях, касающихся принятия решений гражданами об участии в каких-либо инициативах, требующих определенных затрат, например, создание общественных благ ([27]). При этом, как показывают некоторые исследования ([47]), введение минимального порога явки не всегда обеспечивает победу наиболее поддерживаемой альтернативе.

Важным вопросом, касающимся исследуемой процедуры голосования, является количество и устойчивость равновесий Нэша, получающихся в соответствующей теоретико-игровой модели. Подобная модель для голосования с двумя альтернативами по правилу простого большинства рассматривалась в работе [25]. Для случая одного сторонника одной альтернативы и N > 1 сторонников другой показано, что чистых равновесий Нэша в модели голосования нет. Более того, количество смешанных равновесий больше одного, при этом в одних равновесиях выше вероятность победы первой альтернативы, а в других - второй. Для общей модели с произвольным

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

В главе 2 настоящей работы показано, что для произвольных значений численности избирателей существует большое количество равновесий, приводящих к различным исходам. Это приводит к необходимости рассмотрения вопроса, какие из них наиболее соответствуют реальному поведению при голосовании. Такого рода вопросы возникают в различных теоретико-игровых моделях. Для их решения обычно рассматривают модели динамики, которые позволяют выделить среди точек равновесия устойчивые и неустойчивые.

Для описания динамики поведения в социальных популяциях используются модели адаптивно-подражательного поведения (МАПП, [46], [5254]). Такие модели описывают ситуации, когда голосование происходит многократно примерно в одних и тех же условиях, что позволяет индивидам выбирать свои стратегии исходя из опыта и результатов предыдущих голосований. В теории игр исследование таких моделей проводится анализа устойчивости равновесий, возникающих в статической модели.

Другой широко используемый класс динамических моделей, также описывающих многократно повторяющееся взаимодействие индивидов в одних и тех же условиях, - это модели, аналогичные процессу фиктивного разыгрывания ([60]). Как показывает работа [21], такие модели обладают лучшими свойствами в смысле сходимости: для некоторого класса неантагонистических игр траектории процесса фиктивного разыгрывания ведут себя так же, как и средние по времени траекторий МАПП. Сходимость к смешанному равновесию имеет место для биматричных игр, с помощью

линейных преобразований сводимых к антагонистическим ([51]). Для более полного исследования свойств равновесий статической модели ниже рассматривается динамика поведения обоих указанных типов.

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

Научная новизна полученных в работе результатов состоит в следующем.

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

2) Для модели голосования с двумя альтернативами полностью исследовано множество симметричных смешанных равновесий в зависимости от соотношения затрат и выигрыша от участия в голосовании. Показано, что при любом их соотношении существуют не более двух таких равновесий. Исследована адаптивная динамика поведения в окрестности подобных равновесий в предположении координированного поведения сторонников каждой из альтернатив.

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

4) Построена новая модель последовательного голосования участников. Показано существование единственного совершенного подыгрового равновесия, исследованы его свойства.

Обзор литературы

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

Моделям формирования коалиционных структур посвящено большое количество научной литературы, в основном опирающейся на методы теории игр. Такие модели находят применение в экономической географии ([2-3]) и политологии ([22-23]; [45]; [56]; [63-64]), а также при исследовании проблемы создания юрисдикций для оптимального размещения общественных благ ([610]; [17-20]; [40-42]; [61-62]).

В моделях формирования коалиций общество представляет собой множество игроков (агентов, индивидов и т.д.). Каждый агент обладает функцией предпочтений, имеющей единственный максимум на некотором множестве идеальных точек. Это множество в зависимости от сферы применения конкретной модели может иметь различные интерпретации: это могут быть географические координаты проживания агентов ([2-3]; [6-10]; [1720]; [40-42]; [61-62]), политические программы ([22-23]; [45]; [56]; [63-64]) и т.д. Унимодальность предпочтений позволяет полностью характеризовать каждого агента его идеальной точкой. Все общество в целом характеризуется распределением агентов на множестве идеальных точек.

Под коалициями в большинстве работ понимаются подмножества

множества игроков и соответствующие множества идеальных точек. Каждой

коалиции согласно некоторому правилу ставится в соответствие точка

(политика, центр) из того же множества, что и иде