авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

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

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

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

Вартанов Сергей Александрович Теоретико-игровые модели формирования коалиций и участия в голосовании 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 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).





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

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

i : x Xi i ArgmaxjI{0} U (x, rj, pj ). (1) Регулярным равновесием Нэша называется такое равновесие, в кото ром политики всех коалиций различны: 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. Соответствующее равенство называется уравнением безразличия граничного агента, оно имеет вид R (ri ) L (c pi ) = R (ri+1 ) L (pi+1 c). (2) Утверждение 1.1. Пусть функция плотности f (x) унимодальна с единственным максимумом в точке M [0, 1]. Тогда в любом равновесии Нэша множество X0 либо пусто, либо представляет собой объединение ( )( ) интервалов вида X0 = 0, c0 c0, 1, где c0, c0 [0, 1].

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

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

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. В дальнейшем r предполагается, что функции 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, выполнялось неравенство:

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

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

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

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

(5) UL (c, rL ) = UR (c, rR ) Его можно рассматривать как уравнение относительно 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) min max min max (rR (c, rL ) rR (c)) с левой границей в точке c будем называть минималь ной (максимальной) относительно предыдущей, для неё UR (c, r) 0 ( 0).

r Аналогично, вогнутость по 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)) с правой границей min max в точке c называется минимальной (максимальной) относительно после дующей, для неё UL (c, r) 0 ( 0). Таким образом, любому равновесию r Нэша, состоящему из 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], если n T T1 = 1. Рассматривая суммарный размер коалиций: ln (r1 ) = ri (r1, T ) и i= T решая уравнение (r1 ) = 1 на множестве допустимых значений r1, мож ln но определить все коалиционные структуры, являющимися равновесиями Нэша заданного типа T.

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

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

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

лициям, необходимо решить уравнение i= Утверждение 1.4. 1) В равновесии Нэша размеры rL, rR соседних коалиций связаны неравенством rR (c, rL ) rL rR (c, rL ), где c - их min max общая граничная точка.

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

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

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

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

min В разделе 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 ), ci+ где r = f (x) dx - размер объединенной коалиции, p - её политика:

ci ci+ p f (x) dx = f (x) dx.

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

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

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

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

Пусть rL (a) (R (b)) - размер левой (правой) коалиции, при котором r условие (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) 3x r R (x) R (r), x 0, (9).

2 2 Если R(·) не является непрерывно дифференцируемой, то справедливо следующее утверждение, где R (x), R+ (x) - производные слева и справа в точке x. ( r) Утверждение 1.9. Пусть R (·) вогнута. Если x 0, 2 R+ (x) ( r) либо 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 = ci 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. Вероятности участия избирателей из первой и второй групп во вполне смешанном равновесии удовлетворяют системе уравнений:

{ (k ) ( ) P (n1 + 1 = n2) + P (nk = n2) = w1, k A (10) P nl + 1 = n1 + P nl = n1 = w2, l A2, 2 В разделе 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) = w (11), 2 (p, q) = w где:

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

p То же справедливо и для решений 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), q p 2 (1,q) f2 (q) = max 2 (p, q), а - единственный корень уравнения qincr = 0, q p p0 = arg max 1 (p, 1 p), q0 = 1 p0.

p Теорема 2.1. При равных относительных издержках (w1 = w2 = w) существует не более двух смешанных симметричных равновесий со стратегиями участников первой и второй групп p и q соответствен но.

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

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

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

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

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

+ В разделе 2.3.2 проводится полное исследование множества всех сме шанных равновесий для случая малого количества участников голосова / / 3 3 (1 + 3)2, w2,2 = 3 4. Каждая ния: N1 = 2, N2 = 3. Пусть w2,3 = система вида (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 рассматривается модель адаптивного поведе ния, описывающую динамику смешанных стратегий избирателей в предпо ложении их координированного поведения. Уравнения динамики для этой модели имеют вид:

{ p (t) = p (1 p) (1 (p, q) w) (14) q (t) = q (1 q) (2 (p, q) w) Cимметричные смешанные равновесия являются неподвижными точ ками системы дифференциальных уравнений (14). Для исследования их устойчивости используется линейное приближение.

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

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

{ pi (t) = pi (1 pi ) 1i (, ), i = 1, 2;

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

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

Траектории, начинающихся из окрестности любого из равновесий, мо гут вести себя по-разному. Так, например, на рисунке 1 приведен пример двух траекторий решений системы (15) для начальных значений из окрест ностей симметричного равновесия (, ) типа HL. Одна из траекторий pq начинается в точке (, ) + где - собственный вектор, соответству pq j, j ющий положительному собственному значению якобиана. Эта траектория покидает окрестность симметричного равновесия и со временем образует предельный цикл вокруг равновесия типа (0, 0, 1, 0, U ). Другая траектория, приведенная на рис. 1, также начинается из окрестности (, ) такой, pq что 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-тым получил право v проголосовать избиратель из первой группы, и 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 (k) + N2 N2 (k) = N1 n1 (k) + 1 (16) В случае равных численностей сторонников обеих альтернатив ситуа ция, соответствующая СПР, совпадает с равновесием Нэша в чистых стра тегиях модели с одновременным голосованием. Однако при разной числен ности в СПР модифицированной игры, в отличие от смешанного равновесия исходной, не возникает парадокса: всегда побеждает кандидат с большим числом сторонников. При этом для победы кандидата, как правило, не требуется участия всех его сторонников. Пусть все возможные порядки голосования равновероятны, тогда среднее число n2 (N1, N2 ) голосующих участников группы 2 имеет вид, приведенный на рисунке 2.

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

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

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

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

{ q min w1, w2, 1 N1 1 w1, 1 N1 1 w2, если N2 = N1 1.

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

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

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

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

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

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

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

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

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

- С. 3-20.

[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- Содержание диссертации и основные положения, выносимые на защиту, от ражают персональный вклад автора в опубликованные работы. Подготовка к публикации полученных результатов проводилась совместно с соавтора ми, причем вклад диссертанта был определяющим. Все представленные в диссертации результаты получены лично автором.



 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

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