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

им. М.В. Ломоносова

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

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

Теоретико-игровые модели

формирования коалиций и участия в

голосовании

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

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

кандидата физико-математических наук

Москва – 2013

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

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

Официальные оппоненты: доктор физико-математических наук, главный научный сотрудник ВЦ РАН им. А.А. Дородницына, профессор Лотов Александр Владимирович, доктор технических наук, зав. кафедрой высшей математики факультета экономики НИУ ВШЭ, профессор Алескеров Фуад Тагиевич

Ведущая организация: Институт прикладных математических исследований КарНЦ РАН

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

С диссертацией можно ознакомиться в библиотеке факультета ВМК МГУ. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http://cs.msu.su в разделе «Наука» - «Работа диссертационных советов» - «Д 501.001.44»

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

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

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

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

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

Важным вопросом является устойчивость коалиционных структур к различным типам коалиционных отклонений (сильное равновесие 1, P-ядро, квазиустойчивость 2 ).

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

Степанова. В указанных работах остались нераскрытыми вопросы сущеR.J. Aumann. The core of a cooperative game without side payments // Transactions of American Mathematical Society, A. Savvateev. Achieving Stability in Heterogeneous Societies: multi-jurisdictional structures, and redistribution policies // Moscow: EERC, ствования, вычисления и устойчивости равновесий Нэша в случае неравномерности распределения участников на множестве идеальных точек.

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

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

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

Задачи работы • определить структуру множества равновесий Нэша теоретико-игровых моделей эндогенного формирования коалиций в случае неравноАлескеров Ф.Т., Ордешук П. Выборы. Голосование. Партии // М.: Академия, F.T. Aleskerov, V.I. 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— T.R.Palfrey, H.Rosenthal. A strategic calculus of voting // Public Choice, Vol. 41 (1), 1983, pp 7- T.R.Palfrey, H.Rosenthal. Voter Participation and Strategic Uncertainty // The American Political Science Review, Vol. 79 (1), March 1985, pp. 62- Haan M., Kooreman P. How majorities can lose the election. Another voting paradox // Social Choice and Welfare, Springer, Vol. 20, мерного распределения участников по идеальным точкам и исследовать их устойчивость к основным типам коалиционных отклонений;

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

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

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

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

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

Построена новая модель последовательного голосования избирателей.

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

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

Публикации. Основное содержание диссертации опубликовано в работах [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]. Распределение агентов по идеальным точкам описывается функцией плотности f (x), x X, F (x) = f (x) dx - функция распределения агентов. В работе рассматриваются два класса функций плотности f (x) - монотонные и унимодальные с единственным максимумом во внутренней точке X.

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

Размер ri коалиции i пропорционален доле ее сторонников (ri = fi (x) dx), а ее итоговая политика pi определяется как медиана распределения с плотpi ностью fi (x): fi (x) dx = fi (x) dx. Множество Xi = {x X : fi (x) > 0} называется носителем коалиции i I.

Выигрыш агента с идеальной точкой x в случае, если он присоединяется к коалиции i с размером ri и политикой pi, равен U (x, ri, pi ) = = R (ri ) L (|x pi |), где L(·), R(·) – возрастающие по своим аргументам функции. Выигрыш, получаемый агентом в случае неприсоединения ни к одной из коалиций, считается нулевым. Равновесием Нэша является такой набор стратегий агентов, в котором каждый из них присоединяется к той коалиции, в которой его выигрыш максимален:

Регулярным равновесием Нэша называется такое равновесие, в котором политики всех коалиций различны: i, j I : i = j pi = pj. Так как нерегулярные равновесия заведомо неустойчивы к объединению коалиций с одинаковыми политиками, далее рассматриваются только регулярные равновесия. Ю.В. Сосиной 8 доказано, что структура регулярного равновесия описывается следующим утверждением:

Если L (x) – выпукла, то в регулярном равновесии Нэша каждой коалиции i I соответствует единственный интервал Xi X, такой, что x Xi fi (x) = f (x) и x X \ Xi fi (x) = 0, где Xi – замыкание Xi.

Таким образом, множество X в регулярном равновесии разбивается на конечное число непересекающихся интервалов Xi, i I, и множество X0, где Xi с точностью до множества граничных точек совпадает с носителем Сосина Ю.В. Эндогенное формирование политических структур и исследование их устойчивости // Препринт WP7/2004/04, Серия WP7 «Теория и практика общественного выбора», Москва, ГУ ВШЭ, коалиции i, а X0 соответствует множеству игроков, воздержавшихся от присоединения к коалициям.

Пусть коалиции упорядочены по расположению на множестве X слева направо. Если c - граничная точка, разделяющая носители коалиций i и i + 1, то в равновесии выигрыш агента с идеальной точкой c одинаков в случае его присоединения как к i, так и к i+1. Соответствующее равенство называется уравнением безразличия граничного агента, оно имеет вид Утверждение 1.1. Пусть функция плотности f (x) унимодальна с единственным максимумом в точке M [0, 1]. Тогда в любом равновесии Нэша множество X0 либо пусто, либо представляет собой объединение интервалов вида X0 = 0, c0 c0, 1, где c0, c0 [0, 1].

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

Для упрощения записи далее используются следующие обозначения:

UL (c, r) = R (r) L (c pL (c, r)) - выигрыш граничного агента с идеальной точкой c в лежащей слева от него коалиции, имеющей размер r и политику pL (c, r) = F 1 F (c) 2 ; UR (c, r) = R (r) L (pR (c, r) c) - выигрыш граr ничного агента с идеальной точкой c в лежащей справа от него коалиции, имеющей размер r и политику pR (c, r) = F 1 F (c) + 2. В дальнейшем предполагается, что функции UL (c, r) и UR (c, r) вогнуты по r и по c. Это верно при равномерной плотности распределения f (x) 1. В более общем случае справедливо следующее утверждение.

Утверждение 1.2. Функция UL (c, r) вогнута по r при любом c. Для вогнутости по r функции UR (c, r) достаточно, чтобы x1, x2 [0, 1], таких что x1 x2, выполнялось неравенство:

Для вогнутости по c функций UL (c, r), UR (c, r) достаточно, чтобы x1, x2 [0, 1], таких что x1 x2, выполнялось неравенство:

Для степенной функции L (x) = xk, k 2 и линейной функции f (·) оба условия выполнены. В общем случае необходимым условием выполнения (3) является выполнение неравенства dx ln L (x) dx ln F (x) для любого x [0, 1], то есть L (·) должна быть логарифмически "более выпукла чем F (·). Достаточным условием выполнения (4) является выпуклость функции f 1 (что верно, например, для любой вогнутой функции f (·)).

Пусть в регулярном равновесии присутствуют две соседние коалиции с носителями XL = (a, c), XR = (c, b) и размерами rL и rR, соответственно.

Согласно (2), размеры этих коалиций связаны равенством:

Его можно рассматривать как уравнение относительно rR при фиксированном rL и как уравнение относительно rL при фиксированном rR. Пусть rR (c) = Argmaxr UR (c, r), rL (c) = Argmaxr UL (c, r). Вогнутость по r функции UR (c, r) гарантирует, что уравнение (5) имеет не более двух решений относительно rR, расположенных по разные стороны от точки rR (c). Обозначим их rR (c, rL ), rR (c, rL ). Коалицию размера rR (c, rL ) rR (c) (rR (c, rL ) > rR (c)) с левой границей в точке c будем называть минимальной (максимальной) относительно предыдущей, для неё UR (c, r) 0 ( 0).

Аналогично, вогнутость по r функции UL (c, r) гарантирует, что уравнение (5) имеет не более двух решений относительно rL, расположенных по разmin max ные стороны от точки rL (c): меньшее rL (c, rR ) и большее rL (c, rR ). Коалиция размера rL (c, rR ) rL (c) (rL (c, rR ) > rL (c)) с правой границей в точке c называется минимальной (максимальной) относительно последующей, для неё UL (c, r) 0 ( 0). Таким образом, любому равновесию Нэша, состоящему из n последовательно расположенных коалиций, соответствует двоичный вектор T = (T1, T2,..., Tn ), определяющий тип каждой последующей коалиции относительно предыдущей: Ti = 0, если коалиция i {1,..., n} минимальна относительно предыдущей, и Ti = 1, если она максимальна. Вектор T называется типом равновесия Нэша.

В разделе 1.2 предложен следующий метод расчета всевозможных равновесий Нэша. По заданному размеру r1 первой коалиции размеры ri (r1, T ) всех последующих коалиций в соответствии с типом T определяются однозначно с помощью уравнения (5). Множество допустимых значений r - полуинтервал (0, rR (0)], если T1 = 0, либо полуинтервал (rR (0), 1], если T1 = 1. Рассматривая суммарный размер коалиций: ln (r1 ) = ri (r1, T ) и решая уравнение (r1 ) = 1 на множестве допустимых значений r1, можln но определить все коалиционные структуры, являющимися равновесиями Нэша заданного типа T.

Отдельно рассматривается случай равновесий с непустым множеством игроков, воздержавшихся от присоединения к коалициям. Пусть r0 - доля этих игроков, X0 = 0, F 1 (r0 ) - множество их идеальных точек.

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

она максимальна относительно предыдущей, то есть T1 = 1 и r1 (r0 ) = rR (F 1 (r0 ), 0). Каждому возможному равновесию Нэша соответствует вектор T = (1, T2,..., Tn ), определяющий тип каждой последующей коалиции. Следовательно, для поиска равновесий фиксированного типа T с непустым множеством игроков, воздержавшихся от присоединения к коаn лициям, необходимо решить уравнение Утверждение 1.4. 1) В равновесии Нэша размеры rL, rR соседних коалиций связаны неравенством rR (c, rL ) rL rR (c, rL ), где c - их общая граничная точка.

2) Функция rR (c, rL ) при каждом фиксированном значении c унимодальна по rL и достигает максимума r1 (c) в точке rL (c).

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

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

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

В разделе 1.3 исследуются условия устойчивости для равновесий Нэша. Из Утверждения 1.5 следует, что заведомо существуют равновесия, состоящие из большого числа мелких коалиций. Однако малый размер коалиций может обуславливать стремление их участников к объединению. Равновесие называется устойчивым к локальному объединению, если невозможно образование новой коалиции из двух существующих соседних коалиций, так, чтобы всем участникам формирующейся коалиции было выгодно объединение. Иными словами, для любой пары соседних коалиций i и i + 1 с носителями Xi = (ci1, ci ), Xi+1 = (ci, ci+1 ) и политиками pi, pi+1 :

x Xi : U (x, r, p) U (x, ri, pi ) или x Xi+1 : U (x, r, p) U (x, ri+1, pi+1 ), где r = f (x) dx - размер объединенной коалиции, p - её политика:

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

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

где rL - размер левой коалиции, а c (a, rL ) = F 1 (F (a) + rL ). Аналогичное условие справедливо и для случая минимальности левой коалиции:

где rR - размер правой коалиции, а c (b, rR ) = F 1 (F (b) rR ).

Пусть rL (a) (R (b)) - размер левой (правой) коалиции, при котором условие (7) (соответственно, (8)) выполняется как равенство.

Утверждение 1.6. Пусть f (x) унимодальна с максимумом в точке M [0, 1]. Для того чтобы равновесие Нэша было устойчивым к локальному объединению, необходимо и достаточно, чтобы для каждой пары соседних коалиций с носителями XL = (a, c) и XR = (c, b) выполнялось одно из условий:

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

2) если b M, то размер rL левой коалиции превышает пороговое значение rL (a);

3) если a M, то размер rR правой коалиции превышает пороговое значение rR (b);

4) если M (a, b), то либо rR rR (b), либо rL rL (a).

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

Утверждение 1.7. Пусть f (x) монотонно возрастает. Равновесие, состоящее только из минимальных коалиций, устойчиво к локальному Степанов Д.С. Модель эндогенного формирования коалиционных структур: диссертация на соискание степени кандидата физико-математических наук: 01.01.09.-Москва, 2011.- 151 с.

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

В разделе 1.3.2 исследуется устойчивость равновесий к расколу входящих в него коалиций. Равновесие называется устойчивым к расколу, если не существует новой коалиции, являющейся собственным подмножеством одной из существующих коалиций, и обеспечивающей большие выигрыши всем своим членам. Д.С. Степановым 10 доказано, что если плотность распределения f (x) монотонна, L(·) и R(·) дважды дифференцируемы, L(·) выпукла, R(·) вогнута, L (·) возрастает, а R (·) убывает, то любое равновесие Нэша устойчиво к расколу.

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

Теорема 1.1. Пусть плотность распределения f (x) унимодальна и достигает максимума в точке M [0, 1], L(·) и R(·) дважды дифференцируемы, L(·) выпукла, R(·) вогнута, а R (·) убывает. Тогда любое равновесие Нэша устойчиво к расколу.

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

Утверждение 1.8. Коалиция размера r устойчива к расколу тогда и только тогда, когда Если R(·) не является непрерывно дифференцируемой, то справедливо следующее утверждение, где R (x), R+ (x) - производные слева и справа Утверждение 1.9. Пусть R (·) вогнута. Если x 0, 2 R+ (x) либо x 0, 2 R (x) 2, то коалиция размера r устойчива к расколу.

Иначе для устойчивости к расколу необходимо и достаточно, чтобы условие (9) выполнялось для x, такого что 3 R (x ), R+ (x ).

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

двумя альтернативами (кандидатами). Избиратели делятся на две группы в зависимости от того, какую из альтернатив они поддерживают. Каждая группа характеризуется своей численностью (в первой группе - N1 участников, во второй -N2, N2 N1 ). Обозначим ci, i = 1, 2, затраты избирателя из группы i на участие в выборах (одинаковые для всех членов группы).

Если побеждает альтернатива i, то её сторонники получают выигрыши ai, а если побеждает другая альтернатива, то столько же теряют. В случае равенства голосов выигрыш любого участника равен нулю. Взаимодействие избирателей описывается в виде игры в нормальной форме с N1 + N2 игроками.

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

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

Пусть pk - вероятность участия в голосовании k-го избирателя первой группы, а ql - вероятность участия в голосовании l-го избирателя второй группы. Пусть p = (pk, k A1 ) и = (ql, l A2 ), где Ai - множество стоq ронников альтернативы i, i = 1, 2. Тогда количества n1 и n2 голосующих сторонников первой и второй альтернатив соответственно - случайные величины, зависящие от p и соответственно, как и nk - количество голоq сующих сторонников первой альтернативы, за исключением сторонника k, nl - количество голосующих сторонников второй альтернативы, за исключением сторонника l. Вероятности участия избирателей из первой и второй групп во вполне смешанном равновесии удовлетворяют системе уравнений:

В разделе 2.2 исследуются симметричные смешанные равновесия, в которых каждый избиратель из второй группы принимает участие в голоT.R.Palfrey, H.Rosenthal. A strategic calculus of voting // Public Choice, Vol. 41 (1), 1983, pp 7- Haan M., Kooreman P. How majorities can lose the election. Another voting paradox // Social Choice and Welfare, Springer, Vol. 20, совании с вероятностью q, а избиратель из первой группы - с вероятностью p. Для таких равновесий система (10) приобретает вид:

где:

Функции 1 (p, q) и 2 (p, q) являются унимодальными по каждой из двух переменных p, q при фиксированном значении другой. Таким образом, уравнение 1 (p, q) = w имеет не более двух решений относительно p при любом значении q, при этом меньшее из них (L (q)) расположено на участке возрастания 1 (p, q), а большее (H (q)) - на участке убывания.

То же справедливо и для решений qL (p), qH (p) уравнения 2 (p, q) = w относительно q при фиксированном p. Все возможные симметричные смешанные равновесия подразделяются на четыре типа в зависимости от того, пересечением каких именно функций pi (q) и qj (p), i, j {L, H} они являются. Равновесие, образованное пересечением pi (q) и qj (p), называется ij-равновесием (равновесием типа ij). Пусть w = min max 1 (p, q), Теорема 2.1. При равных относительных издержках (w1 = w2 = w) существует не более двух смешанных симметричных равновесий со стратегиями участников первой и второй групп p и q соответственно.

Если 0 < w < w, то существует ровно два равновесия (p, qHL ) и (p, qLH ), где p = 1 qHL, p = 1 qLH и p > p, имеющие типы

LH HL LH HL LH

Если w < w f2 qincr, то существует ровно два равновесия (p, qi ), i {HH, LL}, причем p0 (p, p ) и q0 (qHH, qLL ). Эти равновесия имеют типы HH и LL соответственно, и 2 (pi,qi ) = 1 (pi,qi ) = 0.

Если 1 > w > f2 (qincr ), то существует единственное равновесие (p, qHH ) типа HH, для которого также 2 HH HH = 1 HH HH = 0.

Исследованию вопросов существования и количества несимметричных равновесий посвящен раздел 2.3. В разделе 2.3.1 описывается множество частично смешанных равновесий, в которых часть избирателей использует чистые стратегии. Пусть A - множество сторонников кандидата i, испольi зующих чистую стратегию «не голосовать», а использующих стратегию «голосовать» - A+. Каждое частично смешанное равновесие характеризуi ется четырьмя натуральными числами - N1, N1, N2, N2, описывающими мощности множеств A+, A, A+ и A соответственно. Оставшиеся игроки используют смешанные стратегии p N1 (N1 +N1 ), N2 (N2 +N2 ), где n - стандартный n-мерный симплекс. Всякий набор (, ), входящий в частично смешанное равновесие при некоторых N1, N1, N2, N2, удовлетворяет системе равенств Случайные величины ni, описывающие количество голосующих сторонников каждого из кандидатов, представляют собой сумму постоянного числа Ni+ участников, применяющих чистую стратегию голосования, и случайной величины nm - количества голосующих участников из числа применяющих смешанные стратегии, i = 1, 2. Аналогичным свойством обладают и случайные величины nk. Для тех игроков, которые применяют чистые стратегии, должны быть выполнены условия оптимальности выбранных ими стратегий:

Неравенство (13a) описывает оптимальность стратегии «не голосовать» для игроков из A, (13b) - оптимальность стратегии «голосовать» для игроков из A1. Аналогично, (13c) и (13d) описывают оптимальность выбранных стратегий для игроков из A и A+ соответственно. Очевидно, что пара неравенств (13a) и (13d) не может выполняться одновременно, как и пара (13b) и (13c). Таким образом, не существует таких частично смешанных равновесий, что в них одновременно N1 = 0 и N2 = 0 (или одновременно N2 = 0 и N1 = 0).

В разделе 2.3.2 проводится полное исследование множества всех смешанных равновесий для случая малого количества участников голосоваw2,2 = 3 4. Каждая система вида (12) при N1 = 2 и N2 = 3 имеет не более двух решений при любом значении w. Тип каждого равновесия определяется, таким образом, набором N1, N1, N2, N2, i, где индекс i характеризует, какому из решений системы (относительно p) (12) - большему (H), меньшему (L) или единственному (U ) - соответствует данное равновесие.

Утверждение 2.11. В исследуемой модели существует шесть или семь частично смешанных равновесий. В зависимости от того, в какой из интервалов - W1 = (0, w2,3 ), W2 = (w2,3, w2,2 ) или W3 = (w2,2, 1)- попадает значение относительных издержек w, типы равновесий будут различаться. Если w W1, то возможны равновесия типов: (1, 0, 0, 0, H), (2, 0, 0, 0, U ), (0, 0, 0, 1, H), (0, 0, 1, 0, U ), (0, 0, 1, 1, U ), (0, 0, 2, 0, U ), (0, 0, 2, 1, U ).

Если w W2, то их типы: (0, 1, 0, 0, H), (2, 0, 0, 0, U ), (0, 0, 0, 1, L), (0, 0, 1, 0, U ), (0, 0, 1, 1, U ), (0, 0, 2, 0, U ), (0, 0, 2, 1, U ). Если же w W3, то это равновесия типов (0, 1, 0, 0, H), (0, 0, 0, 1, L), (0, 0, 0, 2, U ), (0, 0, 2, 0, U ), (0, 0, 2, 1, U ) и (0, 1, 0, 1, U ).

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

Утверждение 2.12. При w > w2,3 существуют вполне смешанные несимметричные равновесия такие, что q1 = q2 = q3. При этом возможен как случай p1 = p2, так и случай p1 = p2.

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

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

Утверждение 3.1. Пусть численность первой группы - N1, второй группы - N2, w- пороговое значение относительных издержек. Если w < w, то при равновесию типа LH соответствует устойчивый фокус системы (14), а равновесию типа HL - неустойчивый фокус. В противном случае LH-равновесию соответствует устойчивый, а HL-равновесию неустойчивый узел. Если w > w, то равновесию типа HH соответствует устойчивый, а равновесию типа LL - неустойчивый узел системы (14).

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

где: 1i (, ) = P ( i = n2 ) + P ( i + 1 = n2 ) w - разность ожидаемых выигрышей i-го участника первой группы в случае его участия и неучастия в голосовании, 2j (, ) - аналогичная величина для j-го участника второй группы.

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

Траектории, начинающихся из окрестности любого из равновесий, могут вести себя по-разному. Так, например, на рисунке 1 приведен пример двух траекторий решений системы (15) для начальных значений из окрестностей симметричного равновесия (, ) типа HL. Одна из траекторий начинается в точке (, ) + где - собственный вектор, соответствуpq j, j ющий положительному собственному значению якобиана. Эта траектория покидает окрестность симметричного равновесия и со временем образует предельный цикл вокруг равновесия типа (0, 0, 1, 0, U ). Другая траектория, приведенная на рис. 1, также начинается из окрестности (, ) такой, что p1 = p2, q1 = q2 = q3. Эта траектория сходится к исходному равновесию. Траектория, исходящая из окрестности равновесия типа (0, 0, 1, 0, U ), сходится к точке (0, 0, 1, 1, 0), не являющейся равновесием статической модели. Таким образом, в модели адаптивно-подражательного поведения с полностью независимым поведением участников все равновесия неустойчивы. Однако если допустить возможность координации между участниками каждой из групп, то в получающейся симметричной модели ровно одно равновесие является асиптотически устойчивым.

Рис. 1. Вид траекторий адаптивного поведения, начинающихся из окрестности симметричного равновесия типа HL (сплошная и штрих-пунктирная линии) и равновесия типа (0, 0, 1, 0, U ) (пунктирная линия) В разделе 3.2.3 изучается динамика фиктивного разыгрывания для исследуемой модели голосования. Проведенное в работе численное исследование показало, что, так же как и в случае динамики адаптивного поведения, ни одно из равновесий не является устойчивым хотя бы локально.

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

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

Проведенные численные расчеты показывают, что для любых численностей избирателей симметричные равновесия типов HH, LL и HL являются «парадоксальными»: в них вероятность победы альтернативы с меньшей поддержкой выше, чем вероятность победы альтернативы с большей поддержкой. В то же время, при малых значениях относительных издержек в равновесии типа LH такого парадокса не возникает.

Развитию моделей голосования посвящен раздел 3.4. Рассмотрен механизм последовательного голосования при наличии информации о результатах голосования предшествующих избирателей. Последовательность голосования определяется случайным образом и не зависит от того, к какой группе принадлежит избиратель. Вначале из (N1 + N2 ) избирателей выбирают первого голосующего, затем из оставшихся (N1 + N2 1) выбирают второго, и так далее. Порядок голосования избирателей описывается вектором = (v1, v2,..., vN1 +N2 ), где vk = 0, если k-тым получил право проголосовать избиратель из первой группы, и vk = 1, если это право получает избиратель из второй группе. Каждый избиратель может либо проголосовать за свою альтернативу либо не участвовать в выборах. Участие в выборах требует от избирателя группы i издержек ci, в случае победы "своего"кандидата он получает выигрыш ai, а в случае проигрыша - столько же теряет. Предполагается, что в обеих группах относительные издержки избирателей wi = aii (0, 1),i = 1, 2. Предполагается, что k-тому голосуc ющему известна следующая информация: N1 (k), N2 (k) - сколько избирателей каждой группы имело возможность проголосовать перед ним, n1 (k), n2 (k) - сколько из них действительно проголосовали. Стратегия избирателя определяет, примет он участие в голосовании или нет, в зависимости от того, как проголосовали предыдущие избиратели. Следующие утверждения определяют поведение избирателей в совершенном подыгровом равновесии (СПР).

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

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

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

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

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

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

q min {w1, w2, 1 w2 }, если N2 > N1}= 1;

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

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

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

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

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

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

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

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

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

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

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

203-215.

[5] Вартанов С.А. Свойства равновесий в коалиционных играх с неравномерным распределением агентов // Сборник тезисов XVII международной научной конференции студентов, аспирантов и молодых ученых "Ломоносов-2010"; секция "Вычислительная математика и кибернетика: Москва, МГУ им. М.В.Ломоносова, 12-15 апреля 2010 года".М.: МАКС Пресс, 2010. - С. 29- [6] Вартанов С.А. О локальной устойчивости равновесий в модели эндогенного формирования коалиций // Сборник тезисов XVIII международной научной конференции студентов, аспирантов и молодых ученых "Ломоносов-2011"; секция "Вычислительная математика и кибернетика: Москва, МГУ им. М.В.Ломоносова, 11-15 апреля 2011 года".- М.: МАКС Пресс, 2011. - С. 120- [7] Вартанов С.А. О структуре равновесий Нэша и их локальной устойчивости в модели эндогенного формирования коалиций // Сборник тезисов XIX международной научной конференции студентов, аспирантов и молодых ученых "Ломоносов-2012"; секция "Вычислительная математика и кибернетика: Москва, МГУ им. М.В.Ломоносова, 9- апреля 2012 года".- М.: МАКС Пресс, 2012. - С. 43- [8] Вартанов С.А. Исследование равновесий в модели эндогенного формирования коалиций // Сборник тезисов лучших дипломных работ 2010 года.- М.: МАКС Пресс, 2010. - С. 46- Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад автора в опубликованные работы. Подготовка к публикации полученных результатов проводилась совместно с соавторами, причем вклад диссертанта был определяющим. Все представленные в диссертации результаты получены лично автором.