Модели эндогенного формирования коалиционных структур тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

0И4Ы3378

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

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

Степанов Денис Сергеевич

Модели эндогенного формирования коалиционных структур

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

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

1 8 НОЯ 2010

Москва - 2010

004613378

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

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

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

евич

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

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

Левченков Вячеслав Степанович, кандидат физико-математических наук, доцент МФТИ, Белотелов Николай Вадимович

Ведущая организация: Институт проблем управления РАН

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

Автореферат разослан 2010 г.

Ученый секретарь диссертационного совета, профессор

Н.П. Трифонов

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

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

Одно из современных направлений в теории игр связано с исследованием моделей эндогенного формирования коалиций в больших неоднородных множествах игроков. В этих моделях игроки похожи в смысле вида функции выигрыша и множества стратегий, но различаются по некоторому параметру х € X (например, место жительства, идеальная точка), при этом все множество игроков А описывается распределением по указанному параметру. Стратегия игрока — выбор коалиции, то есть подмножества S С А, в рамках которого объединяются для совместных действий. Игроки однородны по функции выигрыша, которая зависит от двух параметров: возрастает по размеру коалиции и убывает по расстоянию между идеальной точкой х и политикой коалиции. Политика коалиции представляет собой точку из X и определяется по заданному правилу в зависимости от состава коалиции. Размер коалиции пропорционален доле игроков, вошедших в нее.

Различные модификации таких моделей используются в экономической географии при изучении вопросов устойчивости разбиения населения по странам (А. Alesina, Е. Spolaore), а также по юрисдикциям (муниципалитетам или регионам) внутри страны (A. Bogomolnaya, M. Le Breton, S. Weber, A. Savvateev, 0. Haimanko). Они находят также применение в политологии при анализе устойчивых разбиений избирателей по политическим партиям (A. Gomberg, F. Marhuenda, I. Ortuno-Ortin, Ю.В.Сосина). В указанных исследованиях авторы рассматривают вопросы существования и коалиционной устойчивости равновесий Нэша и изучают их свойства.

Все упомянутые теоретико-игровые модели и задачи формально отличаются друг от друга только рядом ограничений, накладываемых на игру. Анализ проводится для конкретного вида функций выигрыша — обычно предполагается линейная или квадратичная зависимость от аргументов и одномерное множество значений параметра. В настоящей работе снимается часть указанных ограничений: исследование различных концепций решения игры (равновесие Нэша, коалиционные равновесия) проводится для функций выигрыша обобщенного вида (Глава 1) и множества X произвольной конечной размерности (Глава 2). Таким образом, результаты, полученные в диссертации, могут быть применены к любой из рассматриваемых в литературе модификаций модели.

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты работы докладывались на научных семинарах факультета ВМиК МГУ им. Ломоносова, на XX научной конференции РЭШ (РЭШ, Москва, 2006г.), на V Московской международной конференции по Исследованию операций (ВМиК МГУ, Москва, 2007г.), на международной научной конференции «Государственное управление в XXI веке: традиции и инновации» (ФГУ МГУ, Москва, 2007г.), на XXI научной конференции РЭШ (РЭШ, Москва, 2007г.), на IX Международной научной конференции «Модернизация экономики и глобализация» (ГУ-ВШЭ, Москва, 2008 г.).

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

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

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

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

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

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

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

В главе 1 дано формальное описание игры в базовом случае — случае однотипных (в смысле вида функции выигрыша) игроков и одномерного множества идеальных точек игроков (параметра, характеризующего их интересы). Множество игроков описывается распределением по идеальным точкам на множестве X = [0,1] с плотностью распределения /(•). Задан достаточно большой набор меток: «Коалиция 1», «Коалиция 2»,____Каждый

из игроков выбирает метку и становится членом соответствующей коалиции, или же решает воздержаться и не вступает ни в одну из коалиций (метка «О»). Политика коалиции — точка из того же множества X, положение которой определяется по некоторому фиксированному правилу в зави-

симости от состава коалиции (для одномерного случая - это медиана распределения членов коалиции по идеальным точкам). Размер коалиции равен доле игроков, выбравших соответствующую метку. Таким образом, совокупность стратегий игроков определяет множество непустых коалиций I и набор функций <5{(х), показывающих долю игроков с идеальной точкой х, выбравших г £ / = / и {0}. Рассматриваются совокупности, которым соответствуют интегрируемые функции 5х(х), г € I, 5,(х) > 0, = 1. Раз-

ш

мер г; коалиции г € / определяется как г,- = § х£ч(х)}(х)(1х, а стратегия Р; коалиции задается условием ¡Х<р6^х)/(х)йх = $ рб1(х)/(х)<1х. Выигрыш игрока с идеальной точкой х, входящего в коалицию %, зависит от двух факторов: размер коалиции и расстояние от идеальной точки игрока до стратегии коалиции и определяется как V(х, г) = 1/(х,п, Р;) = — £(||Р;-х||), где || • || — евклидова норма на X (то есть |-|), а Я(-),Ь(-) — положительные монотонно возрастающие функции. Выигрыш игрока в случае воздержания от вступления в коалиции и(х, 0, х) = 0. Также предполагается, что £"(■) > 0 и Д"(-) < 0 (в диссертации приводится интерпретация и обоснование данных предположений).

По определению, равновесие Нэша (РН) — такая совокупность стратегий (¿¿(х),г е Г), при которой каждый игрок выбирает коалицию, максимизирующую его выигрыш, то есть:

\ZxVi е I: (5{(х) > 0) г е Аг^ахЩх, гР,)- (1)

Заметим, что атомарная структура (5о(х) = 1, ни один из игроков не вступил в коалицию) — всегда РН.

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

Теорема 1.1. В регулярном равновесии Нэша множество X разбивается на конечное число непересекающихся интервалов Би г € I, и множество 50, где Si представляет собой множество идеальных точек игроков, выбравших коалицию г, а £о — конечное число интервалов идеальных точек игроков, воздержавшихся от вступления в какую-либо коалицию. При этом стратегии игроков, чьи идеальные точки расположены на границе соответствующих интервалов, определяются неоднозначно.

Каждый из интервалов Яг, г € /, однозначным образом (с точностью до множества меры нуль игроков, идеальные точки которых являются граничными точками) соответствует множеству игроков, выбирающих в равновесии данную коалицию г 6 I. В дальнейшем указанные интервалы также будем называть коалициями. Соседними называются коалиции с общей граничной точкой.

Основной результат этого раздела сформулирован в виде теоремы 1.2. Отметим, что если уравнение Щг) - Ь(г/2) = 0 имеет положительное решение, то оно единственно. Обозначим данное решение через г*. Если г* 6 (0,1), то для любого и 6 (0, тахт (Д(г) -Ь(г/2))) существуют два решения Г1(и),г2(и) € (0,1) уравнения и — Щг) - Ь (г/2)

Теорема 1.2. (О РРН) а) Для всякого натурального т разбиение множества X на т коалиций одинакового размера гт = ~ является РРН тогда и только тогда, когда — < г*. В частности, если г* > 1

' т — ' —

или Щг) > Ь(г/2) для любого г > 0, то такая структура является РРН для любого т; если Ь'(0) > 2Д'(0), то единственное РРН — атомарная структура.

b) Если существет такое и е (0, тахг (Щг) - Ь (г/2))), что решения Г! (и). г2(и) уравнения Щг) — Ь (г/2) = и принадлежат интервалу (0,1), и существуют натуральные числа т^тг такие, что т^т^и) + тгГ2(и) = 1, то разбиение X на ггц коалиций размера г\(и) и т2 коалиций размера г2(и) является РРН (коалиции могут располагаться в любом порядке).

c) Для любого натурального т < — любое разбиение X на т коалиций размера г* и I < т + 1 интервалов игроков, воздержавшихся от вступления в коалиции, является РРН.

й) Не существует других РРН, кроме указанных.

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

Обозначим структуру, описанную в пункте а) утверждения, через Кт. Пусть далее гт = ^ — размер коалиции в Кт. Заметим, что

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

них коалиций и обеспечивающей большие выигрыши всем своим членам. Если равновесие Нэша устойчиво одновременно к обоим указанным типам отклонений, то оно локально устойчиво (ЛУ). Наконец, совокупность стратегий называется коалиционным равновесием (КР), если не существует новой коалиции, обеспечивающей большие выигрыши всем своим членам.

В данном разделе получены условия локальной устойчивости и ЯРдля структур Кт, т = 2,3,...

Теорема 1.3. Равновесная по Нэшу коалиционная структура Кт локально устойчива тогда и только тогда, когда выполнено условие

Доказательство теоремы показывает, что, во-первых, любая равновесная структура Кт устойчива к локальному расколу, и, во-вторых, она неустойчива к локальному объединению тогда и только тогда, когда объединение выгодно граничным агентам новой (потенциальной) коалиции. Далее доказывается, что при выполнении дополнительных ограничений равновесная коалиционная структура является КР тогда и только тогда, когда она локально устойчива.

Теорема 1.4. (О КР) Локально устойчивая структура Кт является КР тогда и только тогда, когда выполнены следующие условия:

где го = max {rm, min {rg, |rm}}, о. Гд - решение уравнения R'(x)+\L'{x/2— rm/2)-±L'(x/2)=0.

Данная теорема указывает условия на функцию выигрыша, при выполнении которых локальной устойчивости оказывается достаточно для КР. Ранее в работе Сосиной (2006) для линейной и квадратичной функции выигрыша было показано, что всякая локально устойчивая структура является КР, то есть два этих понятия эквивалентны. Однако, в общем случае это не так. В частности, в диссертации приведён пример структуры, являющейся локально устойчивой, но не являющейся Л"Р(структура К6 при R{r) = 3г ~ Ц-r2, L(z) = 2). При доказательстве теоремы показано, что для любой локально устойчивой структуры Кт невыгодно образование любых коалиций, размер которых не принадлежит интервалу (rm, 2гт), но в общем случае может быть выгодно образование коалиции с размером из этого диапазона. Выполнение условий (2)-(3) необходимо и достаточно, чтобы коалиции из данного интервала также не могли обеспечить увеличение выигрышей всем их участникам.

R(2rm) - R(rm) < L(rm) - L(rm/2).

L'(rm/2) > R'(rm) и Я(го) ~ R(rm) + £(r„/2 - rm/2) - L(r0/2) < 0,

(2) (3)

В главе 1 рассматривается также возможность обобщения полученных результатов для неравномерного распределения игроков по параметру х е [0,1]. Рассмотрим коалиционную структуру К = (а¡,п, Pi),i = 1,... ,т, где а; - координаты на прямой правой границы коалиции, пн Pi — размер и стратегия коалиции.

Теорема 1.5. (Об условиях безразличия граничных игроков) Структура К является регулярным равновесием Нэша тогда и только тогда, когда отклонение не выгодно граничным агентам коалиций, то есть параметры К удовлетворяют системе:

R(ri+1) - R(n) = L(P{+1 - а,) - L(ai - Р^, R(n) - Ца{ - р{) > 0, г = 1,..., m - 1.

Пусть плотность распределения /(•) — монотонная функция, тогда равновесная структура К локально устойчива тогда и только тогда, когда локальное объединение не выгодно граничным игрокам формирующейся коалиции, то есть справедливы соотношения

Я(г,- + ri+j) - R(ri+l) < L{ai+1 - Р) - L{ai+i - Pi+1), R(ri + ri+1) - R(n) < L(P - at) - L(Pi - a^,

где P = medfi(x),fi(x) =. <x< ai+i},i = 1.....m-1.

В главе 2 рассматривается игра формирования коалиций с множеством значений идеальных точек произвольной размерности: dimJf — п > 1. В разделе 1 главы дано формальное описание игры для многомерного случая в той части, где оно отличается от одномерного случая. В следующем разделе приведено описание и свойства «правила усреднения», в соответствии с которым в многомерном случае определяется стратегия коалиции (стратегия определяется как средняя идеальная точка игроков, входящих в коалицию). Рассмотрены его отличия от одномерного аналога. В разделе 3 исследован вопрос о типах регулярных равновесий Нэша, которые возможны в многомерном случае. Число различных типов равновесий, возможных в многомерном случае, значительно больше, чем в одномерном случае, но, по аналогии с одномерным случаем, справедливо следующее утверждение.

Теорема 2.1. В регулярном равновесии Нэша множество X разбивается на конечное число непересекающихся односвязных областей Su г е I, и множество Sq, где Si представляет собой множество идеальных точек игроков, выбравших коалицию г, a S0 — множество идеальных точек воздержавшихся игроков, представляющее собой дополнение к объединению Si. При этом стратегии игроков, чьи идеальные точки

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

Как и в одномерном случае, указанные области будем называть коалициями. Границей Г(г) коалиции г € I будем называть границу соответствующей области Si, а соседними — коалиции, имеющие общий участок границы.

Утверждение 2.1. В регулярном равновесии граница между соседними коалициями i и j, задается уравнением

Lm - ill) - L{\\Pj - «II) = R(n) - Г(»\ j). (4)

Граница является частью гиперплоскости тогда и только тогда, когда Ti = rj, либо когда функция L(z) имеет вид L(z) = cz2, с > 0.

Раздел 4 посвящен описанию свойств одного достаточно общего подкласса коалиционных структур. Пусть X = [0,1]". Рассмотрим произвольную прямоугольную сетку на'Х и коалиционную структуру, в которой каждая коалиция представляет собой объединение произвольного числа ячеек сетки. Такого рода коалиционные структуры будем называть прямоугольными. Коалиционные структуры, в которых коалиции представляют собой равные n-мерные прямоугольные параллелепипеды, назовем равномерными прямоугольными структурами.

Для равномерных прямоугольных структур введем следующие обозначения. Через Кт1...тп будем обозначать равномерную прямоугольную структуру, где т,- — число коалиций вдоль j-й координаты n-мерного куба X. Поскольку геометрически все коалиции представляют собой равные прямоугольные параллелепипеды, то можно ввести вектор а длин сторон: а = (ai,...,a„), и тогда aj = Без ограничения общности пусть

ii > а.2 > ... > ап. Пусть V = fllLi а; и D = уТГ=1 ai ~ размер коалиции и длина диагонали. Также введем 7; =

Теорема 2.2. В общих предположениях относительно функции L(-) (при L(z) ф cz2) в классе прямоугольных структур равновесными могут быть только равномерные прямоугольные структуры. Такая структура является равновесной тогда и только тогда, когда R(V) — L(D/2) > 0.

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

В разделе 5 исследуется локальная устойчивость прямоугольных структур. Устойчивость к локальному расколу определяется полностью аналогично одномерному случаю. Определение устойчивости к локальному

объединению обобщается следующим образом: равновесие Нэша устойчиво к локальному объединению, если не существует коалиции, представляющей собой n-мерный параллелепипед и являющейся объединением 2", s = 1,... ,п соседних коалиций, имеющих хотя бы одну общую точку, и обеспечивающей большие выигрыши всем своим членам.

Теорема 2.3. Равновесная по Нэшу коалиционная структура ifmi...m„ локально устойчива тогда и только тогда., когда для m = 1,2,...,п, выполнено условие

R (2mV) - R (V) < L ((1 + 3ai) ' D/2) - L (D/2), (5)

°m = 7n-m+l + • • • + 7n-

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

Следствие 1. Пусть

U{x,V,P) = aV-\\P~x\\k, (6)

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

2kV

1, min

(1 + 34)

к/2

m=l,...,n 2m - 1

= Л(й).

Множество А (а) допустимых значений параметра а непусто тогда и только тогда, когда 2т < (1 4- Зсг^)для всех т. При этом:

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

b) Для к = п множество А (а) вырождается в точку, и нетривиальные коалиционные структуры не существуют для а Ф А (а).

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

Следствие 2. Пусть U(x, V, Р) = V - J^Li \\р ~ г1Г> сц>0,к> 0,. Тогда при к < п устойчивых коалиционных структур также не существует.

Поскольку в зависимости от значений rrij,j = 1,..., п, для коалиционной структуры А'т,...П1п существет очень большое число вариантов образования новых коалиций, полностью обобщить результаты для устойчивости равновесий, полученные в одномерном случае, не удается. Тем не менее, в диссертации получено достаточное условие устойчивости к объединению любого числа коалиций.

Теорема 2.4. Если выполнено ограничение

max (R(Cnpn) - L(p)) < R(V) - L(D/2) (7)

о</><|

где Cn = Г(п/2+1)' m0 равновесная коалиционная структура Kmi..mn устойчива к объединению коалиций. Данное условие становится также и необходимым при достаточно малом D.

Для некоторого s из указанного диапазона неравенство (7) соответствует условию, обеспечивающему устойчивость к образованию коалиции, представляющей собой п-мерную сферу радиуса sD/2. Такая коалиция имеет максимальный размер среди коалиций с заданным расстоянием от игрока, которому наименее выгодно образование коалиции, до стратегии коалиции.

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

В главе 3 исследуется игра, в которой игроки различаются как по идеальным точкам, так и по функциям выигрыша. В разделе 1 приведено формальное описание игры. Предполагается, что есть два типа игроков; «старого» (или «основного») — тип Ti и «нового» — тип ТДоля игроков нового типа равна А > 0. При этом рассматривается два случая:

1. Игроки обоих типов равномерно распределены по идеальным точкам на всем множестве X

2. Игроки типа Т2 равномерно распределены по идеальным точкам на некотором сегменте S с X, а игроки типа Т\ - на дополнении X\S. В этом случае Л =

Если игрок с идеальной точкой х типа Ti,l = 1,2, выбирает коалицию г размера Г{ с политикой Р{, то его выигрыш равен {/;(х, п,Р;) =

й;(п) - Ь1(р(Р{, х)), где р(-) — метрика на X, а /?/(•), — некоторые положительные возрастающие функции. Для игрока со стратегией 0 (воздержавшийся), выигрыш равен Щх,0,х) = N,¡(0) - ¿¡(0) = 0. Относительно функций выигрыша предполагается, что игроки нового типа менее чувствительны к росту удаленности: Ь'2{-) < Ь[(-) или более чувствительны к росту размера коалиции: Я^(-) > Н'^-) (либо и то и другое одновременно), то есть игроки нового типа являются большими конформистами.

В разделе 2 изучается вопрос, как влияет на структуру РН и их устойчивость изменение доли А агентов нового типа Гг, если они равномерно распределены на всем множестве X = [0,1] . Исследование этой задачи проводится для функций выигрыша вида

г,Р) = г - щ(Р - х)\1 = 1,2, «1 > а2, (8)

то есть для случая квадратичной зависимости выигрыша от расстояния между идеальной точкой игрока и стратегией коалиции, в которую он входит. В работе Сосиной (2006) показано, что если функция выигрыша игроков имеет вид 11{х,г,Р) = г — а(Р —х)2, то для т > 2 коалиционная структура Кт является КР тогда и только тогда, когда а € [^р,4т]. В исследуемой модели предполагается, что ах 6 [тр, 4т], то есть структура Кт является КР при Л = 0. Выясняется, что произойдет с ростом доли А: нарушится ли устойчивость структуры Кт, какие иные локальные равновесия могут сформироваться в случае потери устойчивости, каких дальнейших изменений равновесной структуры можно ожидать. Ответы на эти вопросы существенно зависят от соотношения т,а 1, и а2.

Утверждение 3.1. Если а2 € тп], /по есть структура Кт является КР для игроков нового типа, то Кт остается КР независимо от доли А.

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

Далее рассматривается случай, когда для игроков нового типа аг < ^ (они являются большими конформистами, чем игроки основного типа). В рамках структуры Кт игроки типа Тг склонны к образованию коалиций большего размера и к ним может примкнуть часть игроков типа Т\. Коалицию, образованную в результате объединения игроков типа Тг из двух соседних коалиций и примкнувших к ним игроков типа Т\, чьи идеальные точки находятся вблизи стратегии новой коалиции, будем называть

коалицией удвоенной длины. Пусть <5 - доля игроков типа Т\ вошедших в совместные коалиции с игроками типа

Утверждение 3.2. Если а2 < то структура Кт устойчива к образованию коалиций удвоенной длины тогда и только тогда, когда доля А игроков нового типа не превосходит порогового значения Хт = 1 - пеРех°де через это значение структура ока-

зывается неустойчивой к образованию таких коалиций с параметром А),52(А)), где:

- 1+П) т

т = за-^ЛЙ) - 4- А, ¿2(Л) | = 52(Хт) 6

(0,1),01 = а,02 = ^,^ = 1-А.

Отметим, что при А < | любое рассматриваемое равновесие Нэша устойчиво к образованию коалиций удвоенной длины. Чем меньше число коалиций т, тем дольше структура Кт остается устойчивой при увеличении доли игроков типа Т2.

При увеличении А свыше порогового значения Ат структура Кт перестает быть КР. Количество коалиций т, в которых будут участвовать игроки типа Тг в измененной структуре, зависит от того, как пройдет объединение соседних коалиций. Если тп четно и все коалиции объединяются попарно, то тп = т/2 . Возможны и другие варианты укрупнения исходных коалиций, при которых их границы сдвигаются по сравнению с исходной структурой.

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

Обозначим коалиционную структуру, в которой игроки типа Т2 разбиваются на т равных коалиций длины 4, на подмножествах идеальных точек длины — к ним примыкают игроки типа Ть а прочие игроки типа Тг образуют равные внутренние коалиции, причем на одну совместную коалицию приходится 2к внутренних коалиций. На рисунке (I) показано, как устроена эта коалиционная структура.

Далее рассматриваются коалиционные структуры вида КЛ и Структура называется локально устойчивой, если она является равновесием Нэша и устойчива к образованию коалиций удвоенной длины и к объединению внутренних коалиций. Согласно предположению, в исходной структуре Кт т > ^ и ^ < т < Устойчивость новой коалиционной структуры зависит от того, в какой интервал относительно параметров а]

тп:[г::: Игроса Т, Игрока Тг

т согоесгаыхсоалнпяй

Рис. 1. Коалиционная структура

и «2, попадает число т.

Утверждение 3.3. Для всякого т € т) при А 6 (Ат,Ай) структура Кт является локально устойчивой.

Таким образом, при переходе А через пороговое значение Ат устойчивой оказывается любая структура Кш с т > Если ^р] п ф 0, то процесс укрупнения коалиций с ростом А может завершиться формированием структуры Кт для т из этого множества. Однако в случае За2 < ах с ростом А возникает ситуация, когда ни одна структура не является локально устойчивой. В этом случае выделим три характерных интервала: М1 = ^), М2 = ^), М3 = , Заметим, что М1иМ2иМ2— ^р-]- На интервале [0, равновесий Нэша вида КА и не существует, так как оба типа игроков склонны к расколу.

Утверждение 3.4. Равновесные по Нэшу структуры вида существуют в том и только том случае, если т £ = М\ и Йг и А

1 а 1

превышает пороговое значение Хтът = 1--^ при этом значения

1

к и 5 определяются из системы:

5 = + (9)

где

Ш = (10)

* = \/(4тА - + (Ш - 8тА + М (11)

(12)

4т А

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

< Ат, то есть при потере устойчивости структурой Кт существуют равновесные структуры с т из этого диапазона. Более того, для

т € [у, любая такая структура устойчива к образованию совместных коалиций удвоенной длины. Получено также необходимое и достаточное условие устойчивости к объединению внутренних коалиций:

(М)

4 тп А

В заключении данного раздела обсуждается, как изменяется коалиционная структура при увеличении доли Л игроков нового типа. Пусть ^ € Из Утверждения 3.3 следует, что т = ^ - число, для которого структура К,-п с совместными однородными коалициями может быть локально устойчива,

- с*1 + За2

соответствующее ей пороговое значение Л = -г.

3(й1 - а2)

При ^ < аг < а\ для любого целого т е и любой доли Л

201 (1-^2) 3(оц - а2)

устойчивыми могут быть только структуры вида При А -» 1 устой-

чивы только структуры с т 6 [^т2]. В случае возникновения такой структуры распределение игроков нового типа по коалициям при дальнейшем увеличении А остается неизменным, при А 1 размер внутренних коалиций игроков старого типа и их выигрыш в этих коалициях стремятся к нулю.

В качестве конкретного примера рассмотрим модель с «1 = 60, а2 = 2 и с исходным количеством коалиций тп = 32. Соответствующие характерные интервалы для т М\ = |), М2 — (§, 15), М3 = (15,45).

Согласно утверждению 3.2, исходная структура ЛГ32 становится неустойчивой при А = А32 = 0.342672. Игрокам выгодно попарное объединение совместных коалиций и структура К1в оказывается устойчивым РН. Она теряет устойчивость при А = А^ = 0.375, при этом структура возникающая в случае формирования коалиций удвоенной длины, является РН

структура является КР. Если же с*2 < то при А >

для 8, к: 5 > 0.643927, к > 1, однако условие устойчивости к объединению внутренних коалиций выполнено лишь для к = 1. Но при этом условие устойчивости к объединению совместных коалиций не выполняется, то есть игрокам выгодно новое попарное объединение совместных коалиций. Аналогичная ситуация возникает при т — 4. Для т = 2 структура оказывается устойчивой при к = 5,..., 13 для соответствующих значений 6. При дальнейшем увеличении доли Л необходимое условие устойчивости к объединению перестает выполняться при 1 - Л = 0.286, что приводит к формированию структуры сш = 1, устойчивой при к = 22,...,60.

При дальнейшем приближении А к 1 некоторые РН, состоящие из одной совместной коалиции и к внутренних, являются устойчивыми. Количество внутренних коалиций растет, их размер и выигрыш образующих их игроков типа 71 стремятся к 0.

В разделе 3 исследован вопрос существования КР в виде структуры Кт, тп = 2,3,... для функций выигрыша общего вида.

Теорема 3.1. Пусть для структуры Кт и для обоих типов игроков выполнены условия локальной устойчивости. Тогда справедливы следующие утверждения, описывающие условия КР для данного случая. 1 (Необходимое и достаточное условие). Структура Кт является КР тогда и только тогда, когда для типа Т\ выполнены условия

Ь[ (гт/2) > Я.[(гт) и (15)

Й!((1 - А)** + 2гтА) - Я\(гт) + 11(х*/2 - гт/2) - Ьх(х*/2) < 0, (16)

где х" = тах {гт, тт {а^, |гт}}, а х*й - решение уравнения (1 - А+ А2гт/х)Д'1((1 - Х)х + 2гтА) + Щ(х/2 - гт/2) - \1[(х/2) = 0, а для типа Т2 — неравенство

Ь'2Ы 2)>ХЩгт). (17)

2 (Достаточное условие 1). Структура Кт является КР, если для типа Т\ выполнено достаточное условие КР для игры с игроками одного типа: неравенства (15) и

К(2гт) + \Ь\ (гт/2) - ¡Ь[(гт) > 0, (18)

а для типа Т2 — неравенство (17).

3 (Достаточное условие 2). Если структура Кт с игроками первого типа является КР, то она остается КР и в случае с игроками двух

различных типов, если для агентов типа Т2 выполнено условие (17) и неравенство

Щ (3rm/2) + iL'2 (rm/4) - iL'2 (3rm/4) < 0. (19)

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

Раздел 4 посвящен исследованию модели при варианте 2 распределения игроков (распределение игроков нового типа на некотором небольшом сегменте).

Утверждение 3.5. Для того, чтобы структура Кт, локально устойчивая для типа Ti (при А = 0), оставалась локально устойчивой при внедрении игроков типа Т2 необходимо и достаточно, чтобы для игроков типа Т2 выполнялось условие неотрицательности выигрыша граничного игрока в Кт:

ДгЫ ~ L2{rm/2) > 0. (20)

Следующее утверждение характеризует коалиционные равновесия модели.

Утверждение 3.6. Структура Кт является КР тогда и только тогда, когда для типа Т\ справедливо соотношение

L\(rm/2) > 2Ri(rm), (21)

а для типа Т2 — условие (20).

Таким образом, только при выполнении более сильного ограничения на выигрыш игроков типа Т\ (см. для сравнения условие (2)) структура Кт остается КР при возникновении данного типа неоднородности.

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

[1] Vasin A., Sosina Y., Stepanov D. Endogenous formation of the coalitional structure in a heterogeneous population I ! NES Working Paper, NES. — 2007. - Vol. #WP2007/072.

[2] Vasin A., Stepanov D. Endogenous formation of political parties // Mathematical and Computer Modeling. — Amsterdam: Elsevier, 2008. — Vol. 48,- Pp. 1519-1526.

[3] Vasin A., Stepanov D. Endogenous Formation of Coalitional Structures in Homogeneously Distributed Population // Труды 7-й Московской международной конференции по исследованию операций (ORM2007). - М.: МАКС Пресс, 2007. - Pp. 211-213.

[4] Vasin A., Stepanov D. Endogenous Formation of Political Parties // Сборник докладов IX Международной научной конференции «Модернизация экономики и глобализация»: в 3 кн. — М.: Изд. дом ГУ ВШЭ, 2008. - Vol. 3. - Pp. 568-577.

[5] Васин А. А., Степанов Д. С. О формировании коалиционной структуры в неоднородной популяции // Сборник докладов международной научной конференции «Государственное управление в XXI веке: традиции и инновации», ФГУ. - 2007. - С. 240 - 245.

[6] Степанов Д. С. Эндогенное формирование коалиционных структур в популяции агентов с различными функциями выигрыша // Математическая теория игр и ее приложения, выпуск 2. — Петрозаводск: Редакция журнала МТИиП, 2010. - С. 79 - 98.

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

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

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 22.10.2010 г. Формат 60x90 1/16. Усл.печ.л. 1,0. Тираж 100 экз. Заказ 470. Тел. 939-3890. Тел./факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.