Многошаговые игры с коалиционной структурой

Седаков, Артем Александрович

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

Седаков, Артем Александрович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Санкт-Петербург МЕСТО ЗАЩИТЫ

2009 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Многошаговые игры с коалиционной структурой»

Автореферат диссертации на тему "Многошаговые игры с коалиционной структурой"

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

СЕДАКОВ Артем Александрович

МНОГОШАГОВЫЕ ИГРЫ С КОАЛИЦИОННОЙ СТРУКТУРОЙ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

003470690

Санкт-Петербург 2009 г.

003470690

Работа выполнена на кафедре математической теории игр и статистических решений факультета прикладной математики — процессов управления Санкт-Петербургского государственного университета.

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

профессор Петросян Леон Аганесович.

Официальные оппоненты: доктор физико-математических наук,

профессор Мазалов Владимир Викторович:

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

Ведущая организация: Институт проблем механики

им. А. Ю. Ишлинского РАН (г. Москва).

Защита состоится « » ¿¿-(-^(^_2009 г. в ^д^ас. на заседании совета Д.212.232.59 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 199034, г. Санкт-Петербург, В. О., Средний пр., д. 41/43, ■лул.^7/ .

С диссертацией можно ознакомиться в библиотеке СПбГУ им. А. М. Горького по адресу: г. Санкт-Петербург, Университетская наб., д. 7/9.

Автореферат разослан * » _ 2009 г.

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

В. Д. Ногин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Статические коалиционные игры рассматривались в работах Ауманна и Дре-зе (1974), Оуэна (1977), Майерсона (1977), Ауманна и Майерсона (1988), Курца (1988), позднее у Вильбао (1998), Руиза, Валенсиано и Зарзуело (1998), ван ден Бринка и ван дер Лаана (2005). Однако динамические игры выбора коалиционного разбиения самими игроками до сих пор не рассматривались.

Известно, что в позиционных играх с полной информацией всегда существует ситуация абсолютного равновесия по Нэшу в чистых стратегиях. Взяв за основу данный факт и решения из теории динамических кооперативных игр, был опубликован ряд работ, в которых строились решения многошаговых игр с коалиционной структурой, отвечающие тем или иным требованиям. В частности, в совместной работе Л. А. Петросяна и Д. А. Аегаина (2000) изначально «сверху» задавалась кооперативная функция игроков, которая предписывала каждому игроку в какой момент он действ}'ет в интересах коалиции, а в какой индивидуально, и, соответственно, однозначно определялась коалиционная структура. Иной способ задания коалиционного разбиения рассматривался в работах Л. А. Петросяна и С. И. Мамкиной (2003), где предполагалось, что коалиционное разбиение в определенных вершинах может изменяться случайным образом. В качестве решения многошаговой игры с. коалиционной структурой был предложен РЛ/5-вектор.

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

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

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

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

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

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

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

Основные положения, выносимые на защиту:

1. Построение принципов оптимальности в многошаговой игре с простой коалиционной структурой и полной информацией.

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

3. Построение принципов оптимальности в многошаговой игре с простой коалиционной и неполной информацией, применение их к динамической модели рыночной дуополии Курно.

4. Построение принципов оптимальности в многошаговой сетевой игре с полной информацией.

5. Формулировка теоремы о существовании единственного решения для многошаговой сетевой игры с полной информацией и ее конструктивное доказательство.

ции «Устойчивость и процессы управления» (Санкт-Петербург, 2005), на семинаре российско-финской летней школы «Динамические игры и многокритериальная оптимизация» (Петрозаводск, 2006), на Между народной конференции Game Theory and Management GTM07 (Санкт-Петербург, 2007), на Международной конференции The Second International Conference on Game Theory and Applications (Qingdao, China, 2007), на Международной конференции The Fourth Spain Italy Netherlands Meeting on Game Theory SIXG4 (Wroclaw, Poland, 2008), а также на семинарах кафедры математической теории игр и статистических решений факультета прикладной математики процессов управления и семинарах Центра теории игр Санкт-Петербургского государственного университета.

Публикации работы. Материалы исследований опубликованы в [1-11].

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

В течение игрового процесса игроки, изъявившие желание кооперироваться, объединяются в одну коалицию с момента объявления ими такого желания. Если в некоторой вершине древовидного графа игрок ¡. принимает решение кооперироваться, то коалицию будут составлять игроки, принявшие такое же решение на предыдущих шагах игры, вместе с г. В данной постановке рассматривается случай, когда игрок, раз попавший в коалицию, не может ее покинуть до окончания игры. После окончания игры выигрыш коалиции полагается равным сумме выигрышей участвующих в ней игроков. Однако каждый из игроков коалиционного разбиения получает выигрыш в соответствии с РМЗ-ъектором (Петросян, Мамкина, 2003), вычисленным для данного коалиционного разбиения.

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

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

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

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

Определение 1 Многошаговой игрой п лиц с простой коалиционной структурой

и с полной информацией называется древовидный граф А", на котором:

• задано разбиение множества вершин X на п+1 множество Рь Рг, ■ • •, Рт -Рп+ь где Р„ I € N есть множество личных позиций игрока г, причем если х является вершиной либо четного ранга, либо нулевого и I 6 Д, то С Р„

= 2. Множество Р„+1 = {.г : Гх = 0} есть множество окончательных вершин, каждая из которых имеет четный ранг;

• в каждой вершине х 6 X задано простое коалиционное разбиение А(х) = {5(;г),/¡...., г|.\'\5(Г)|} множества игроков IV, в котором в коалицию 5(х) входят игроки, выбравшие в своих личных позициях нулевого и четного рангов первую альтернативу вдоль пути, ведущего в эту вершину;

• на множестве окончательных вершин Рп+1 заданы выигрыши игроков — вещественные неотрицательные функции !г\{х), Лг(х),..., /(„(ж), х е Рп+ь При этом если рассмотреть подмножество Р„+!(•) множества окончательных вер-тин Р„+1, вершины которого могут реализоваться при выборе игроками произвольных альтернатив в вершинах четного и нулевого рангов и при фиксированных альтернативах в вершинах нечетного ранга, то на множестве Рп+!(■) выигрыши игроков совпадают. Другими словами, для любого игрока I е N и для любых у е Рп+1(-), г € Рп+1(-), Р„+1(-) С Р„+1 имеет место

Ш = Ы(г).

Определение 2 Под множеством стратегий индивидуального поведения А'(щ(-)) игрока г, стесненным стратегией «;(-) будем понимать подмножество множества стратегий этого игрока, отличающихся от только выборами в вершинах у е У;. Если </,(•) предписывает выбрать первую альтернативу в некоторой вершине г 6 Рг четного или нулевого ранга, то полагаем Л"(ггД-)) = 0.

Для каждого набора стратегий й(-) = (й^-), • ■ ■, '"«(•)) в игРе на древовидном графе К определим функции выигрыша игроков следующим образом. Предположим, что в ситуации й(-) реализуется простое коалиционное разбиение Д = $

5)}, > 2 и путь {О, XI,..., х;}. Тогда функции выигрыша игроков определяются по следующему правилу:

Я;ДО;«(-)) =Л;», »у* 5, 8

Здесь 31цк, 6 5 есть значение вектора Шепли, вычисленного для коалиции 5 по специальным образом построенной характеристической функции в подыгре К(уг), гДе — это первая вершина пути {О, х1:..., х/}, на котором сформировалось коалиционное разбиение Д.

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

Определение 3 Набор стратегий и'(-) — (и^ (■),..., и'(-),..., и*(-)) называется слабым равновесием в игре К (О), если выполняются следующие два условия:

• для любых г е N \ 5 и любых щ € А'(и*(-)) выполняется неравенство

Я,(0;и-(.)||и,(-)ХЯ,(0;и'(-))

• пусть для любого 1 6 ¿V стратегия и* в некоторой вершине х, такой что •Р* = {У 12}> диктует выбор ь*(х) - у (стратегия предписывает игроку г впервые кооперироваться), то всегда выполняется неравенство

для стратегий и*, которые отличаются от и* выбором в х: м,(х) = 2 (стратегия предписывает игроку г не кооперироваться), но полностью совпадают с и* во всех вершинах, предшествующих х.

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

Предположим, что длина игры равна 21 4- 1. Положим 7^(-) = а вершины Хо, Хд и Хо будем считать окончательными ранга 21. Пусть вершина х( имеет ранг 21 —2Ь, £ = 1,Если х( — окончательная вершина, то выигрыши игроков равны I € N. В том случае если не является окончательной, то |.РХ(| = 2, так как является вершиной четного ранга. Пусть у, £ РХ1 есть вершина, соответствующая первой альтернативе (игрок г(х{) выбирает кооперативное поведение),

а г( € РХ1 -■ вершина, соответствующая второй альтернативе (игрок г(х() играет индивидуально). Вершины г/( и г< имеют ранг 21 — 21 + 1. По свойству множеств очередности справедливо, что ¿(х,) = г(у() = г(г4). Пусть 5(х) есть та единственная коалиция, входящая в состав простого коалиционного разбиения в вершине х.

Пусть 5ЛД75(Ш)(У()) есть выплата игроку г € 5(уг) в соответствии с вектором Шепли. Тогда компоненты РЛ/5-вектора имеют вид

Здесь

v'iyt.

7,'Ы =

_ I sWste){vt)), i e S(yt),

-yl(yt),

i £ S(yt).

I'WI r 1

7^) =

T^fa-i). I 6 JV,

n-ie/(z.)

где

I(yt) = ia'S max У* 7,' /(г,) = arg max 7' Ux,^).

Xt.-l€ry ll-lpfr. 4

' i€S(jtt)

li-l€F„

В х, игрок г(х,) выбирает вершину 6 или г4 6 из условия

тах{^(Г[)(у(), 7!(х,)(г<)}-Определим выигрыш любого игрока г € ЛГ в вершине

l\(Ti) =

¡4(j-t), xt e P„+i.

(i)

Теорема 1 Ситуация u*(-) = (wj(-)i ■ - ■ ,u^(-)), где

x(* = argmax{i/pJ(;i/(), 7,'(2()}, ранг x четный, i£S(x), yt, что i/t € ранг x четный, i e S(x),

xt_i = arg max 7,-~1('f), ранг x нечетный, i £ S(x),

X(_i = arg max 7j~'(w)> Ранг x нечетный, i € S(x) jeSM

для любой вершины x, f € [0,i], образ}-ет ситуацию слабого равновесия по Нашу в игре, заданной на древовидном графе К.

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

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

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

Пусть К — (2, Р) — конечный древовидный граф с начальной вершиной го-Определим на древовидном графе К игру В игре принимает участие п игроков. Пусть N = {1,2,...,«} -- конечное множество игроков. В каждой вершине г £ 2 определена одновременная игра в нормальной форме Г(г) вида: Г(г) = {ЛГ, {Х,2},<=^, {Я/^едг), где N = {1,2, ...,п} — конечное множество игроков, XI - конечное множество стратегий игрока г, Н- — функция выигрыша

игрока г, определенная следующим образом: Я? : П X* —> Л.

¿елг

Переход из вершины 2 е 2 в вершину ¡/ е ^ С 2 осуществляется по правилу: у = Ф(г; .... ж*), где (т\,.... есть некоторая ситуация в игре Г(г).

Игра ГА- происходит следующим образом. В вершине го графа К задана одновременная игра Г(г0). Перед выбором стратегий в одновременной игре Г(гц) игроки выбирают одну из двух альтернатив: «кооперироваться» или «не кооперироваться». В одновременной игре Г(го) коалиционное разбиение формируется следующим образом: игроки выбирают альтернативы «кооперироваться» или «не кооперироваться» одновременно и независимо друг от друга; игроки, выбравшие альтернативу «кооперироваться», формируют одну коалицию; игроки, выбравшие альтернативу «не кооперироваться», являются индивидуальными игроками.

Таким образом формируется простое коалиционное, разбиение множества игроков Д(г0) = {5(го), {¿1°},..., {^лг\5(го)|}Ь которое порождает одновременную игр}', непосредственно связанную с Г(го). Эта игра имеет вид:

где {5(г0),{«Г},---Лг^5<го)|}} - множество игроков в игре Г(г0,Д(20)), {Аг5(20), А"2°, ..., А'2^^ ^} множество чистых стратегий игроков, а {Я^), Я,2",..., функции выигрыша каждого игрока. В игре Г(г0, Д(го)) игроки одновременно и независимо друг от друга выбирают свои стратегии. В результате выбора игроками стратегий, формируется ситуация х1а = .....где -г'жч) е АГ5(го). После этого игроки получают выигрыши Я3(г0)(х20) = X) Н?(хга) И Н?(хго), Ь = ч,..., г[лг\3(*о)| соответственно.

Выигрыш Н${га){^га) игрока-коалиции 5(го) распределяется среди ее участников следующим образом. Фиксируем выбранные стратегии игроков, не входящих в коалицию, по характеристической функции игры Г(г0, Д(го)) рассчитываются выплаты игрокам, входящим в простую коалицию в соответствии с вектором Шепли. Теперь каждому игроку в вершине г0 предписан некоторый выигрыш.

Далее игровой процесс переходит в вершину 6 Р20 такую, что = Ф(г0; г20), где хго - реализовавшаяся ситуация в игре Г(20, Д(г0)). Этот и дальнейшие шаги полностью аналогичены рассмотренному.

В § 2.2 приводится определение игры и смешанных стратегий игроков.

Определение 4 Многошаговой игрой п лиц Г к- с простой коалиционной структурой специального класса называется древовидный граф К = (21, на котором:

• в каждой его вершине г € 2 задана игра в нормальной форме Г(г) = (N1 {Х,2},ед', {Я,2},;едг), где N = {1,2,..., п} есть конечное множество игроков, А'2 - конечное множество стратегий игрока > 6 Аг и Я2 : X' —*> Л

«е/у

— функция выигрыша игрока г е Л^;

• в каждой его вершине 2 е 2 перед началом одновременной игры Г(г) игроки формируют коалиционное разбиение путем одновременного выбора либо

альтернативы «кооперироваться», либо «не кооперироваться». Игроки, выбравшие альтернативу «кооперироваться», объединяются в одну коалицию. Таким образом, перед каждой одновременной игрой Г(г), с 6 2 задано простое коалиционное разбиение Д(г) множества игроков

• переход из вершины ; € 2 в вершину у € С 2 осуществляется по правил;' у = Ф(г; х^,..., х'п), где (х^,..., х*) есть некоторая ситуация в игре Г(г);

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

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

В § 2.5 в качестве примера рассматривается конечношаговой модель дуополии Курно.

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

В § 3.1 строится многошаговая сетевая игра. Пусть N = {1,.... п} множество игроков. Построим дерево игры конечный древовидный граф К — (X, Р) с начальной вершиной хд.

Начальный шаг. В начальной вершине х0 древовидного графа К определена сеть Схо. Через дх° обозначим множество ребер сети С1а. Множество узлов Лг совпадает со множеством игроков (узел сети отождествляем с игроком).

Шаг 1. Игрок г(х0) имеет ровно п альтернатив в вершине хд.

• не предпринимать никаких действий, при этом игровой процесс переходит в вершину уп € такую, что у''1 = = </"\

• разорвать связь с одним игроком ] € Лг, ] / ¿(х0), если ребро (г(хд),у) 6 дха;

при этом игровой процесс переходит в вершину у^ € такую, что дХ1 =

дУ» =дх°\(1(ха),Л;

• предложить одному игроку к, к ф ¿(хо) установить связь (г(ж0), к), если ребро (г(х0),к) ф дх°\ при этом игровой процесс переходит в вершину уц, е такую, что дх' = дш = дх° и (г(хо), к).

Таким образом, для вершины Хх 6 = {упЛУч}]ЛУ1к}к} множество ребер д11 однозначно определено. Если Х\ ^ Рп+1, то мы переходим к рассмотрению шага 2 для каждой вершины II € Гха. Этот шаг полностью аналогичен шагу 1, поэтому опуская изложение второго тага игры, рассмотрим некоторый шаг Ь.

Шаг £ (1 Предположим, мы построили древовидный граф до вершин,

которые можно достичь из начальной вершины Хо не более чем за 4 — 1 шагов. Пусть {х0,х1,..., - некоторый путь из х0 построенного древовидного графа в вершину Хц_1, в которую можно попасть из Хд за 4 — 1 шаг. По построению во всех позициях Хо,хь ... ,£¡-1 соответствующие множества ребер дт°, дх',..., дх'~1 однозначно определены. Определим множество дх'.

В вершине х(-\ у игрока г'(х,_1) имеется ровно п альтернатив:

• не предпринимать никаких действий, при этом игровой процесс переходит в вершину у, 1 6 такую, что дх' = ду" = д1'"1;

• разорвать связь с одним игроком ] € Лг, ф г(х(_1), если ребро (г(х(_1), у) € дХ1~х\ при этом игровой процесс переходит в вершину уу е такую, что

</' == а1"1 \ (¿(х,_1 ),з)\

• предложить одному игроку к, к ф г(.т(_1) з'становить связь )Д')> если ребро (¿(х(_1 ).к) д':"'; при этом игровой процесс переходит в вершину т 6 такую, что дТ1 = ду,к = дх,~1 и (¡(ги),к),.

Таким образом, для вершины Хг £ = {упЛУчУзЛУмУк} множество ре-

бер дх' однозначно определено. Если х( $ Рп+ь то мы переходим к рассмотрению очередного шага построения древовидного графа для каждой вершины х(. Построение игры на древовидном графе продолжается аналогичным образом до окончательного шага игры I. При £ = I построение древовидного графа К закончено.

В каждой вершине .г заданы сети С г = (¿V, б (•£")), где ()(х) : дс >—• /? функция полезности, а #,Дх) ее значения полезность игрока < от связи с игроком ].

Для определения индивидуальных выплат игрокам в вершине х строится вспомогательная кооперативная игра п лиц, характеристическая функция которой имеет вид: и(х. Б) = -)€ для любого 5 С N. В качестве дележа

используется вектор Шепли с компонентами 7,(1), г 6 N.

Определение 5 Многошаговой сетевой игрой п лиц с полной информацией называется древовидный граф К, на котором:

• задано разбиение множества вершин X на п + 1 множество Р\, Р2,..., Р„, Р„+1, где Pi, I € N есть множество личных позиций игрока г, множество Рп+1 = {х : = 0} есть множество окончательных вершин;

• в каждой вершине х € X однозначным образом задана сеть Сх = (Л*, в(х)).

В § 3.2 предлагается способ построения ситуации равновесия в конечнотаговой сетевой игре, использую концепцию абсолютного равновесия в конечношаговой игре с полной информацией. Предположении, что длина игры равна I + 1,

Вводится функция Беллмана как выигрыш игрока г в ситуации равновесия по Нэшу в игре за / — { шагов (положим ¡р1^1 = 0). Значения функции Беллмана у> во всех вершинах древовидного графа К определяются стандартным образом (решая уравнение Беллмана от окончательных вершин графа К к начальной при граничном условии). В данном случае для любой окончательной вершины х; е Р„+1 граничное условие выглядит следующим образом: - 7'(х;), 1 € N.

В промежуточной вершине древовидного графа К функция Беллмана удовлетворяет следующему рекуррентному з'равнению:

= ^ )(х<) + = + ЛыМ- (2)

Для игрока j ф /(х() значения функции Беллмана определяются по правил}':

+ (3)

Решая уравнение Беллмана, находим значения ( = 0,...,/, г е N. При Ь = 0 уравнение решено. Вектор (^(хо),..., (хо)) назовем значени&ы многошаговой сетевой игры с полной информацией.

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

Теорема 2 Построенная ситуация и'(-) = (tij(-),... в которой для каждой

вершины х ^ Рп+и стратегия и*(х) игрока i определяется по правилу

= У,

где у находится из соотношения (2), образует ситуацию абсолютного равновесия по Нэшу в многошаговой сетевой игре, заданной на древовидном графе К.

Случай неединственности оптимального пути легко обходится введением понятия индифферентного равновесия по Нэшу (Петросян, Мамкина, 2003). Введем множество I(xt) = arg max

В промежуточной вершине xt древовидного графа К функция ip\ удовлетворяет аналогичному (2) рекуррентному соотношению:

vW*) = "чЛ") + щЬт ■ £ W

Для игрока j -ф i(xt) значения функции определяются по правилу:

= + Е (5)

1 y€/(i,)

Решая уравнение Беллмана, находим значения у?', t = 0,..., l, i 6 N. При t = 0 уравнение решено. Вектор («¿>?(хо),..., </>°(io)) также назовем значением многошаговой сетевой игры с полной информацией.

По аналогии с теоремой 2 справедлива следующая теорема.

Теорема 3 Построенная ситуация и!Е(-) = (и[Е(•),..., и'пЕ(-)), в которой для каждой вершины х £ P„+i, стратегия и{Е(х) игрока i определяется по правилу

и1ЕП = {рЪ)},у е 1(х)У(у) = щщ,

где вершины у находятся с использованием соотношений (4)-(5), образует ситуацию индифферентного равновесия по Нэшу в многошаговой сетевой игре, заданной на древовидном графе К.

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

В § 3.4 приводится определение коалиционного разбиения множества игроков N в сетевой игре Сх = (Ы,()(т)), определенной в вершине .г, и, использую результаты численного примера из § 3.3, прослеживается его динамика.

ПО ТЕМЕ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ СЛЕДУЮЩИЕ

РАБОТЫ:

1. Петросян Л.А., Седаков A.A. Нестационарное поведение в играх с простой коалиционной структурой // Труды XXVI межвузовской научной конференции аспирантов и студентов под редакцией Н. В. Смирнова, В.Н. Старкова. Санкт-Петербург, издательство Санкт-Петербургского университета, 2005, сс. 538-543.

2. Сюрин А. Н., Седаков A.A. Оптимизация коалиционных разбиений в динамических играх с полной информацией // Тезисы докладов Международного семинара «Теория управления и теория обобщенных решений уравнений Гамильтона-Якоби» под редакцией В. С. Пацко. Екатеринбург, издательство Уральского университета, 2005, сс. 157-158.

3. Петросян Л.А., Седаков A.A. Оптимизация простых коалиционных структур в играх с полной информацией // Устойчивость и процессы управления под редакцией Д. А. Овсянникова, Л. А. Петросяна. Санкт-Петербург, СПб-ГУ, 2005, том 1, сс. 586-595.

4. Петросян Л. А., Седаков A.A., Сюрин А. Н. Многошаговые игры с коалиционной структурой Ц Вестник С-Петерб. ун-та., сер. 10, 2006, вып. 4, сс. 97110.

5. Седаков А. А. Стратегическое поведение в динамическом конфликте с частичной кооперацией // Тезисы докладов Международного конгресса «Нелинейный динамический анализ», Санкт-Петербург, 2007, с. 342.

6. Седаков А. А. Одна динамическая игра взаимодействия агентов в сети // Труды XXXIX межвузовской научной конференции аспирантов и студентов под редакцией Н. В. Смирнова, Г. Ш. Тамасяна. Санкт-Петербург, издательство Санкт-Петербургского университета, 2008, 576 е., сс. 489 494.

7. Petrosyan L. A., Sedakov A. A., Syurin A.N. Multistage Games with Coalitional Structure //in Proceedings of the 12th International Symposium on Dynamic Games and Applications, Prance, 2006, p. 172.

8. Sedakov A. A. Weak Equilibrium in Multistage Games with a Simple Coalitional Structure //in Proceedings of the Russian-Finnish Graduate School Seminar Dynamic Games and Multicriteria Optimization, edited by V. V. Mazalov, Karelian Research Centre, RAS, 2006, pp. 34-38.

9. Sedakov A. A. An Approach for Formation of Coalitional Partitions // Collected abstracts of papers presented on the International Conference Game Theory and Management, St Peterburg, Russia, 2007, p. 117.

10. Sedakov A. A. On a Coalitional Dynamic Cournot Duopoly Model // in Proceedings of The Second International Conference on Game Theory and Applications, Qingdao, P.R.China, 2007, pp. 9-12.

11. Petrosyan L. A., Sedakov A. A. Multistage Network Games //Spain Italy Netherlands Meeting on Game Theory, Abstracts, Poland, 2008.

Подписано к печати 24.04.09. Формат 60 х 84 Vie . Бумага офсетная. Гарнитура Times. Печать цифровая. Печ. л. 1,0. Тираж 100 экз. Заказ 4452.

Отпечатано в Отделе оперативной полиграфии химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-4043,428-6919

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

Введение.

Глава 1. Многошаговые игры с простой коалиционной структурой.

§ 1.1 Определение многошаговой игры с простой коалиционной структурой.

§ 1.1.1 Построение древовидного графа в многошаговой игре с простой коалиционной структурой.

§1.1.2 Формальное определение многошаговой игры с простой коалиционной структурой.

§ 1.2 Построение слабого равновесия в многошаговой игре с простой коалиционной структурой.

§1.3 Численный пример многошаговой игры с простой коалиционной структурой.

Глава 2. Специальный класс многошаговых игр с простой коалиционной структурой.

§2.1 Модель многошаговой игры с простой коалиционной структурой специального класса.

§ 2.2 Формальное определение игры.

§ 2.3 Построение ситуации равновесия по Нэшу.

§ 2.4 Численный пример.

§ 2.5 Модель дуополии Курно как пример многошаговой игры с простой коалиционной структурой специального класса.

Глава 3. Многошаговые сетевые игры с полной информацией.

§3.1 Построение многошаговой сетевой игры с полной информацией.

§3.1.1 Построение древовидного графа многошаговой сетевой игры.

§3.1.2 Определение индивидуальных выплат игрокам.

§3.1.3 Формальное определение многошаговой сетевой игры с полной информацией.

§ 3.2 Построение ситуации равновесия по Нэшу в многошаговой сетевой игре.

§ 3.3 Численный пример многошаговой сетевой игры с полной информацией.

§3.4 Коалиционные разбиения в многошаговой сетевой игре.

Введение диссертация по математике, на тему "Многошаговые игры с коалиционной структурой"

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

Статические коалиционные игры рассматривались в работах Ауман-на и Дрезе [31], Оуэна [50], Майерсона [46], Ауманна и Майерсона [32],

Курца [44], позднее у Бильбао, ван ден Бринка и ван дер Лаана. Однако динамические игры выбора коалиционного разбиеиия самими игроками до сих пор не рассматривались.

Известно, что в позиционных играх с полной информацией всегда существует ситуация абсолютного равновесия по Нэшу в чистых стратегиях. Взяв за основу данный факт и решения из теории динамических кооперативных игр, был опубликован ряд работ, в которых строились решения многошаговых игр с коалиционной структурой, отвечающие тем или иным требованиям. В частности, в совместной работе Л. А. Петро-сяна и Д. А. Аешина [15] изначально «сверху» задавалась кооперативная функция игроков, которая предписывала каждому игроку в какой момент он действует в интересах коалиции, а в какой индивидуально, и, соответственно, однозначно определялась коалиционная структура. Иной способ задания коалиционного разбиения рассматривался в работах Л. А. Петросяна и С. И. Мамкиной [19, 51], где предполагалось, что коалиционное разбиение в определенных вершинах может изменяться случайным образом. В качестве решения многошаговой игры с коалиционной структурой был предложен РМБ-вектор.

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

В работе также рассматриваются динамические игры с сетевой структурой. В теории сетевых игр в основном рассматривались статические игры [38, 40, 41, 62], а теоретико-игровые аспекты создания сетевой структуры в динамике до сих пор не исследовались. Предполагается, что сетевая структура также формируется самими игроками — каждый игрок решает в какой момент установить новую связь и с каким игроком, а в какой, наоборот, ликвидировать уже существующую связь. В рассматриваемых моделях исследуется вопрос нахождения оптимального поведения игроков, а при некоторых предположениях и единственного оптимального поведения.

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

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

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

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

3. Построение принципов оптимальности в многошаговой игре с простой коалиционной структурой и неполной информацией, применение их к динамической модели рыночной дуополии Курно.

4. Построение принципов оптимальности в многошаговой сетевой игре с полной информацией.

Апробация работы. Основные результаты были представлены на Международном семинаре «Теория управления и теория обобщенных решений уравнений Гамильтона-Якоби» (Екатеринбург, 2005), на Международной конференции «Устойчивость и процессы управления» (Санкт-Петербург, 2005), на семинаре российско-финской летней школы «Динамические игры и многокритериальная оптимизация» (Петрозаводск, 2006), на Международной конференции Game Theory and Management GTM07 (Санкт-Петербург, 2007), на Международной конференции The Second International Conference on Game Theory and Applications (Qingdao, China, 2007), на Международной конференции The Fourth Spain Italy Netherlands Meeting on Game Theory SING4 (Wroclaw, Poland, 2008), а также на семинарах кафедры математической теории игр и статистических решений факультета прикладной математики - процессов' управления и семинарах Центра теории игр Санкт-Петербургского государственного университета.

По материалам диссертации опубликованы работы [20], [21], [22], [25], [26], [28], [52], [53], [54], [55], [56].

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Седаков, Артем Александрович, Санкт-Петербург

1. Беллман Р. Динамическое программирование. М.: Изд-во иностр. лит-ры, 1960, 400 с.

2. Берж К. Теория графов и ее применения. М.: Изд-во иностр. лит-ры, 1962, 320 с.

3. Берж К. Общая теория игр нескольких лиц. М.: Физматгиз, 1961.

4. Вилкас Э.Й. Оптимальность в играх и решениях. М.: Наука, 1990, 256 с.

5. Вилкас Э. Й. Понятие оптимальности в теории игр. Современные направления теории игр. Вильнюс: Минтис, 1976.

6. Воробьев Н. Н. Коалиционные игры // «Теория вероятности и ее применение», 1967, Т. 12, вып. 2, с. 289-306.

7. Воробьев H.H. Основы теории игр. Бескоалиционные игры. М.: Наука, 1984.

8. Воробьев H.H. Теория игр для экономистов-кибернетиков. М.: Наука, 1985, 272 с.

9. Грауэр JI. В., Петросян JI. А. Многошаговые игры // Прикладная математика и механика, 2004, Т. 68, вып. 4, с. 667-677.

10. Кун Г. У. Позиционные игры и проблемы информации // Позиционные игры под ред. Н. Н. Воробьева, И. Н. Врублевская. М.: Наука, 1967, с. 13-40.

11. Мулен Э. Теория игр. С примерамииз математической экономики. М.: Мир, 1985.

12. Нейман Д., Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970, 709 с.

13. Оуэн Г. Теория игр, М., 1971.

14. Петросян JI. А. Решение неантагонистических игр // Тезисы докладов Всесоюзной конференции «Динамическое управление», Свердловск, 1979, с. 206-210.

15. Петросян J1.A., Аешин Д. А. Значение динамических игр с частичной кооперацией // Труды Ин-та математики и механики УрО РАН, 2000, Т. 6, № 1, с. 160-172.

16. Петросян JI. А., Захаров В. В. Введение в математическую экологию. Л.: Изд. ЛГУ, 1986, 224 с.

17. Петросян Л.А., Зенкевич H.A., Семина Е.А. Теория игр. М.: Высшая школа, 1998, 300 с.

18. Петросян JI. А., Кузютин Д. В. Игры в развернутой форме: оптимальность и устойчивость. СПб.: Изд-во С.-П. университета, 2000, 292 с.

19. Петросян JI.A., Мамкина С. И. Игры с переменным коалиционным разбиением // Вестн. С.-Петерб. ун-та. Сер. 1: Математика, механика, астрономия, 2003, Вып. 3, с. 60-69.

20. Петросян J1. А., Седаков A.A. Оптимизация простых коалиционных структур в играх с полной информацией // Устойчивость и процессы управления под редакцией Д. А. Овсянникова, J1. А. Петросяна. Санкт-Петербург, СПбГУ, 2005, том 1, сс. 586-595.

21. Петросян J1.A., Седаков A.A., Сюрин А.Н. Многошаговые игры с коалиционной структурой // Вестник С-Петерб. ун-та., сер. 10, 2006, вып. 4, сс. 97-110.

22. Петросян JI. А., Томский Г. В. Динамические игры и их приложения. Л.: Изд-во ЛГУ, 1982, 252 с.

23. Печерский С. Л., Яновская Е. Б. Кооперативные игры: решения и аксиомы. СПб.: Изд-во Европ. унив-та в С.-Петербурге, 2004, 459 с.

24. Седаков А. А. Стратегическое поведение в динамическом конфликте с частичной кооперацией // Тезисы докладов Международного конгресса «Нелинейный динамический анализ», Санкт-Петербург, 2007, с. 342.

25. Соболев А. И. Кооперативные игры // Проблемы кибернетики, М.: Наука, 1982, вып. 39, с. 201-222.

26. Adjeroh D., Kandaswamy U. Game-Theoretic Analysis of Network Community Structure, International Journal of Computational Intelligence Res. 2007, Vol.3, No.4, pp. 313-325.

27. Arnold Т., Wooders M. Dynamic club formation with coordination // II Congress of Game Theory Society, Marceille, 2004.

28. Aumann R., Dreze A. Cooperative Games with Coalition Structure. Int J. Game theory, 1974, Vol. 4, pp. 217-237.

29. Aumann R., Myerson R. Endogenous formation of links between players and of coalitions: An application of the Shapley value // Essays in honor of Llyoyd Shapley, Cambridge university press, 1988, pp. 175-191.

30. Bellman R. Dynamic programming. Princeton: Princeton University Press, New Jersey, 1957.

31. Dai Y., Gao H. PGN-vector of One Kind of Partial-cooperative Game in Extensive Form //in Proceedings of The Second International Conference on Game Theory and Applications, Qingdao, P.R.China, 2007, pp. 30-34.

32. Ferguson T. S. Game Theory // http://www.math.ucla.edu/~tom/ GameTheory/Contents.html.

33. Fudenberg D., Tirole J. Game Theory. Mass: MIT Press, 1991.

34. Fukuda. E., Muto S. Dynamic Coalition Formation in the Apex Game. Preprint version, 2004.

35. Goyal S. Vega-Redondo F., Network formation and social coordination // Games and Economic Behavior, 2005, vol. 50, pp. 178-207.

36. Hart S., Kurz M. Endogenous formation of coalitions // Econometrica, 51, 1983, pp. 1047-1064.

37. Jackson M. 0., Watts A. On the formation of interaction networks in social coordination game // Games and Economic Behavior, 1999, vol. 41, pp. 265-291.

38. Jackson M.O. Allocation rules for network games // Games and Economic Behavior, 2005, vol. 51, pp. 128-154.

39. Kuhn H. W. Extensive Games // Proceedings of National Academy of Sciences of the USA, 1950, vol. 36, pp. 570-576.

40. Kuhn H. W. Extensive Games and the Problem of Information // Annals of Mathematics Studies, 1953, no. 28, pp. 193-216.

41. Kurz M. Coalition value, in the Shapley value // Essays in honor of Llyoyd Shapley, Cambridge university press, 1988, pp. 155-173.

42. Maschler M., Peleg B., Shapley L. Geometrical Properties of the Kernel, Nucleolus and Related Solution Concepts // Mathematics of Operation Research, 1979, vol. 4, pp. 303-338.

43. Myerson R. Graphs and cooperation in games // Math, of Oper. Res. 2:225-229.

44. Nash J. Non-cooperative Games // Ann. of Math, 1951, Vol. 54, pp. 286295.

45. Nash J. Equilibrium Points in n-Person Games // Proc. Nat. Acad. Sei. USA, 1950, vol. 36, pp. 48-49.

46. Owen G. Game Theory. Third edition, Academic Press, 1995.

47. Owen G. Political games // Naval Research Logistics Quarterly, 1989, Vol. 18, pp. 345-355.

48. Petrosjan L.A., Mamkina S.I. New Value for Dynamic Games with Perfect Information and Changing Coalitional Structure / / Proceedings of the XI International Symposium on Dynamic Games and Applications, pp. 799-813.

49. Petrosyan L.A., Sedakov A.A. Multistage Network Games // Spain Italy Netherlands Meeting on Game Theory, Abstracts, Poland, 2008.

50. Petrosyan L.A., Sedakov A.A., Syurin A.N. Multistage Games with Coalitional Structure // in Proceedings of the 12th International Symposium on Dynamic Games and Applications, France, 2006, p. 172.

51. Sedakov A. A. An Approach for Formation of Coalitional Partitions // Collected abstracts of papers presented on the International Conference Game Theory and Management, St Peterburg, Russia, 2007, p. 117.

52. Sedakov A. A. On a Coalitional Dynamic Cournot Duopoly Model //in Proceedings of The Second International Conference on Game Theory and Applications, Qingdao, P.R.China, 2007, pp. 9-12.

53. Shapley L. S. A Value for n- person Games //In H.W. Kuhn, A.W. Tucker, eds. Contributions to the theory of games II, Princeton: Princeton Univ. Press, pp. 307-317.

54. Tirole J. The Theory of Industrial Organization, The MIT Press, Cambridge, 1988.

55. Van den Brink R., van der Laan G. Axiomatization of the Normalized Banzhaf Value and the Shapley Value. Social Choice and Welfare, 15. Springer-Verlag, 1998.

56. Vives X. Nash equilibrium with strategic complementarities, Journal of Mathematical Economics, 1990, Vol. 19(3), pp. 305-321.

57. Vives X. Strategic Complementarities in Multi-Stage Games, CEPRDiscussion Papers 5583, C.E.P.R. Discussion Papers, 2006.

58. Watts A. A dynamic model network formation // Games and Economic Behavior, 2001, vol. 34, pp. 331-341.

59. Zhang L., Gao H., Qiao H. The PMS Value of Games in Repeatedly Extensive Form with Changing Coalitional Structures //in Proceedings of The Second International Conference on Game Theory and Applications, Qingdao, P.R.China, 2007, pp. 282-286.