Содержание к диссертации
Введение
Глава 1. Многошаговые игры с простой коалиционной структурой 13
1.1 Определение многошаговой игры с простой коалиционной структурой 15
1.1.1 Построение древовидного графа в многошаговой игре с простой коалиционной структурой 16
1.1.2 Формальное определение многошаговой игры с простой коалиционной структурой 22
1.2 Построение слабого равновесия в многошаговой игре с простой коалиционной структурой 26
1.3 Численный пример многошаговой игры с простой коалиционной структурой 32
Глава 2. Специальный класс многошаговых игр с простой коалиционной структурой 35
2.1 Модель многошаговой игры с простой коалиционной структурой специального класса 36
2.2 Формальное определение игры 42
2.3 Построение ситуации равновесия по Нэшу 44
2.4 Численный пример 54
2.5 Модель дуополии Курно как пример многошаговой игры с простой коалиционной структурой специального класса 63
Глава 3. Многошаговые сетевые игры с полной информацией 75
3.1 Построение многошаговой сетевой игры с полной информацией 75
3.1.1 Построение древовидного графа многошаговой сетевой игры 76
3.1.2 Определение индивидуальных выплат игрокам 79
3.1.3 Формальное определение многошаговой сетевой игры с полной информацией 83
3.2 Построение ситуации равновесия по Нэшу в многошаговой сетевой игре 84
3.3 Численный пример многошаговой сетевой игры с полной информацией 88
3.4 Коалиционные разбиения в многошаговой сетевой игре 95
Литература 99
- Построение древовидного графа в многошаговой игре с простой коалиционной структурой
- Построение слабого равновесия в многошаговой игре с простой коалиционной структурой
- Модель дуополии Курно как пример многошаговой игры с простой коалиционной структурой специального класса
- Построение ситуации равновесия по Нэшу в многошаговой сетевой игре
Введение к работе
Актуальность темы. Коалиционные игры являются подклассом неантагонистических игр п лиц. При рассмотрении коалиционной игры предполагается, что игроки разбиваются на коалиции (формируя тем самым коалиционное разбиение), и игроки, входящие в одну коалицию действуют в ее интересах с целью максимизации суммарного коалиционного выигрыша. Этим коалиционные игры отличаются от кооперативных игр, в которых допускается образование любых коалиций, а из-за супераддитивности характеристической функции фактически предполагается, что все игроки объединяются в «большую» коалицию с целью максимизации суммарного выигрыша, и проблема заключается в нахождении дележа этого суммарного выигрыша, который был бы приемлем для всех игроков. В коалиционных же играх ставится двойная задача: определение оптимального поведения коалиций как отдельных игроков, и, как следствие, нахождения выигрышей этих коалиций как результат их оптимального поведения, и, наконец, нахождения приемлемого дележа коалиционного выигрыша между игроками, входящими в коалицию.
Статические коалиционные игры рассматривались в работах Ауман-на и Дрезе [31], Оуэна [50], Майерсона [46], Ауманна и Майерсона [32],
Курца [44], позднее у Бильбао, ван ден Бринка и ван дер Лаана. Однако динамические игры выбора коалиционного разбиения самими игроками до сих пор не рассматривались.
Известно, что в позиционных играх с полной информацией всегда существует ситуация абсолютного равновесия по Нэшу в чистых стратегиях. Взяв за основу данный факт и решения из теории динамических кооперативных игр, был опубликован ряд работ, в которых строились решения многошаговых игр с коалиционной структурой, отвечающие тем или иным требованиям. В частности, в совместной работе Л. А. Петросяна и Д. А. Аешина [15] изначально «сверху» задавалась кооперативная функция игроков, которая предписывала каждому игроку в какой момент он действует в интересах коалиции, а в какой индивидуально, и, соответственно, однозначно определялась коалиционная структура. Иной способ задания коалиционного разбиения рассматривался в работах Л. А. Петросяна и С. И. Мамкиной [19, 51], где предполагалось, что коалиционное разбиение в определенных вершинах может изменяться случайным образом. В качестве решения многошаговой игры с коалиционной структурой был предложен РМ5-вектор.
В диссертационной работе основным предметом изучения являются многошаговые игры с полной информацией. На базе этих игр предлагаются способы формирования коалиционного разбиения и способы построения решений. В работе коалиционная структура формируется самими игроками — каждый игрок решает в какой момент вступать в коалицию, а в какой играть индивидуально, что гораздо более приближено
к реальным задачам.
В работе также рассматриваются динамические игры с сетевой структурой. В теории сетевых игр в основном рассматривались статические игры [38, 40, 41, 62], а теоретико-игровые аспекты создания сетевой структуры в динамике до сих пор не исследовались. Предполагается, что сетевая структура также формируется самими игроками — каждый игрок решает в какой момент установить новую связь и с каким игроком, а в какой, наоборот, ликвидировать уже существующую связь. В рассматриваемых моделях исследуется вопрос нахождения оптимального поведения игроков, а при некоторых предположениях и единственного оптимального поведения.
Таким образом, рассматриваемая тема является актуальной и ее исследование вносит определенный вклад в развитие теории игр.
Целью диссертационной работы является исследование многошаговых игр с простой коалиционной структурой и полной информацией и многошаговых сетевых игр с полной информацией, в которых игроки непосредственно участвуют в формировании либо коалиционного разбиения, либо сетевой структуры взаимодействия. Исследуется возможность обобщения решений статической коалиционной теории на многошаговый случай и как результат — построение в таких играх принципов оптимальности.
Научная новизна работы. В работе впервые исследуются модели многошаговых игр с коалиционной структурой и полной информацией, в которых игроки имеют «рычаги» управления коалиционным разбиением
в течение всего хода игры. Игрок никогда не примет решения вступить в коалицию, если его компонента дележа предполагаемого коалиционного выигрыша будет меньше его индивидуального выигрыша. В работе также рассматривается многошаговая сетевая игра с полной информацией, в которой игроки воздействуют на сетевую структуру взаимодействия участников в течение всего хода игры. Игрок никогда не примет решения установления связи с другим игроком, если он не получит большую полезность от этой связи по сравнению с полезностью без ее установления с этим игроком. Приведены алгоритмы нахождения оптимального поведения игроков в предложенных моделях.
Практическая ценность работы следует из области применения моделей многошаговых коалиционных либо многошаговых сетевых игр с полной информацией. Возможность воздействия игроков па изменение коалиционной структуры либо сетевой структуры взаимодействия достаточно близко приближает нас к задачам «из жизни». Это могут быть как задачи образования политических партий, экономических и военных союзов, так и задачи построения международных торговых отношений и выбора партнеров по бизнесу или определения отношений внутри социальных слоев населения. В работе приводятся численные примеры, демонстрирующие полученные результаты.
Основные результатами, выносимые на защиту.
Построение принципов оптимальности в многошаговой игре с простой коалиционной структурой и полной информацией.
Формулировка теоремы о существовании единственного решения для
многошаговой игры с простой коалиционной структурой и ее конструктивное доказательство.
Построение принципов оптимальности в многошаговой игре с простой коалиционной структурой и неполной информацией, применение их к динамической модели рыночной дуополии Курно.
Построение принципов оптимальности в многошаговой сетевой игре с полной информацией.
Формулировка теоремы о существовании единственного решения для многошаговой сетевой игры с полной информацией и ее конструктивное доказательство.
Апробация работы. Основные результаты были представлены на Международном семинаре «Теория управления и теория обобщенных решений уравнений Гамильтона-Якоби» (Екатеринбург, 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), a также на семинарах кафедры математической теории игр и статистических решений факультета прикладной математики - процессов' управ-
ления и семинарах Центра теории игр Санкт-Петербургского государственного университета.
По материалам диссертации опубликованы работы [20], [21], [22], [25], [26], [28], [52], [53], [54], [55], [56].
Структура и объем работы. Диссертация состоит из введения, трех глав, разбитых на параграфы (которые, в свою очередь, разбиты на подпараграфы) и списка используемой литературы.
Первая глава посвящена многошаговым играм с простой коалиционной структурой и полной информацией. Выбор кооперативного или индивидуального поведения является элементом стратегии каждого игрока.
В 1.1 дается определение простого коалиционного разбиения множества игроков, и предлагается способ построения многошаговой игры п лиц с простой коалиционной структурой на основе позиционной игры п лиц с полной информацией. Далее, формально определяется многошаговая игра п лиц с простой коалиционной структурой и полной информацией, и вводится понятие слабого равновесия. В этом же параграфе дается описание игрового процесса.
В 1.2 предлагается алгоритм, с помощью которого устанавливается факт существования единственного слабого равновесия в многошаговой игре с простой коалиционной структурой и полной информацией. В качестве дележа используется вектор Шепли.
Численный пример построения слабого равновесия приводится в 1.3.
Во второй главе рассматривается специальный класс многошаго-
вых игр с простой коалиционной структурой, а именно, такие игры, на каждом шаге которых происходит одновременная игра. Выбор кооперативного или индивидуального поведения также как и в главе 1 является элементом стратегии каждого игрока, при этом этот выбор осуществляется всеми игроками одновременно и независимо друг от друга. Игроки, изъявившие желание играть кооперативно, образуют одну коалицию. Кроме этого в многошаговой игре задано правило Ф перехода из одного состояния игры в другое, зависящее от текущего состояния и ситуации в одновременной игре.
В 2.1 строится модель многошаговой игры с простой коалиционной структурой специального класса, дается пошаговое описание игрового процесса: формирование простого коалиционного разбиения, разыгрывание одновременных игр с учетом сформировавшегося коалиционного разбиения, определение выигрышей игроков (с учетом распределения выигрыша коалиции среди ее участников), правило перехода на следующий шаг игры.
Формальное определение многошаговой игры с простой коалиционной структурой специального класса дается в 2.2.
В 2.3 предлагается алгоритм нахождения оптимальных стратегий игроков в многошаговой игре с простой коалиционной структурой специального класса и определения значения игры. В качестве дележа используется вектор Шепли.
В 2.4 приводится численный пример, в котором согласно предлагаемому алгоритму находятся оптимальные стратегии игроков и значение
игры.
В качестве примера в 2.5 рассматривается многошаговая модель конкуренции фирм по Курно. Здесь па каждом шаге одновременная игра представляет собой дуополию Курно. В такой постановке также находятся оптимальные стратегии игроков и значение игры.
Третья глава посвящена многошаговым сетевым играм с полной информацией. В данной главе предметом взаимодействия игроков является сеть, узлами которой они являются. Если в сети существует ребро (i,j), соединяющие двух игроков, то оно имеет полезность 9ij — «ценность» игрока г, получаемую от связи с игроком j — положительную или отрицательную. В начале игры задается начальная сеть — структура взаимодействия игроков. В процессе игры игроки могут либо изменять структуру сети: разрывая связь с некоторым игроком или устанавливая новую, либо не предпринимать никаких действий. Игроки принимают решения согласно очередности ходов.
В 3.1 предлагается алгоритм построения древовидного графа многошаговой сетевой игры, однозначным образом задающий в каждой его вершине сеть. Здесь также предлагается способ определения выплат игрокам на основе вектора Шепли с учетом структуры взаимодействия игроков. Далее даются формальное определение многошаговой сетевой игры с полной информацией и определение равновесия по Нэшу в многошаговой сетевой игре.
В 3.2 устанавливается факт неединственности ситуации равновесия по Нэшу в многошаговой сетевой игре, а также предлагается алгоритм
построения единственной ситуации индифферентного равновесия по Нашу.
Численный пример построения единственного равновесия по Нэшу в многошаговой сетевой игре приводится в 3.3.
В 3.4 дается определение коалиционного разбиения в многошаговой сетевой игре с полной информацией, которое иллюстрируется на решении численного примера из 3.3.
В диссертационной работе использована тройная нумерация формул. Первая цифра означает номер главы, вторая — номер параграфа в главе, третья — номер формулы в параграфе. Для теорем, лемм, определений, следствий, замечаний используется сквозная нумерация. Параграфы и рисунки пронумерованы для каждой главы отдельно. Литература приведена в алфавитном порядке.
Построение древовидного графа в многошаговой игре с простой коалиционной структурой
В работе [15] рассматривался класс многошаговых игр с частичной кооперацией и полной информацией на конечном древовидном графе. Частичная кооперация игроков заключалась в задании кооперативных функций игроков в каждой неокончательной вершине древовидного графа, принимающей только два значения. Если в некоторой вершине значение кооперативной функции игрока было равно нулю, то это означало, что игрок в текущей вершине действует индивидуально. В случае если значение кооперативной функции этого игрока вершине было равно единице, то это означало, что игрок в текущей вершине действует в интересах содержащей его коалиции — игроков, у которых значения кооперативной функции были равны единице в ближайшей к данной вершине личной позиции (вдоль пути из начальной вершины древовидного графа).
В настоящей главе рассматривается несколько иной подход формирования коалиционного разбиения в многошаговой игре с полной информацией. Игрок в каждой вершине своего множества очередности перед совершением выбора альтернативы принимает решение «кооперироваться» или «не кооперироваться». Если игрок однажды принял решение кооперироваться, то он сохраняет его до конца игры. В нашем случае этот выбор входит в стратегию игрока. Игроки, принявшие решение кооперироваться, образуют одну коалицию. Таким образом, в каждой вершине возникает так называемое «простое» коалиционное разбиение, состоящее из коалиции S и индивидуальных игроков. После окончания игры выигрыш коалиции полагается равным сумме выигрышей участвующих в ней игроков. Однако каждый из игроков коалиционного разбиения получает выигрыш в соответствии с РМ5-вектором [19], [51], вычисленным для данного коалиционного разбиения. Предлагается метод оптимизации простого коалиционного разбиения.
В дальнейшем будем придерживаться следующих обозначений. Пусть х — некоторая вершина древовидного графа. Будем говорить, что вершина х имеет ранг к (к = 0,1,2,...), если ее можно достичь из начальной вершины графа ровно за к шагов. Под Fx будем понимать множество вершин древовидного графа, непосредственно следующих за вершиной х. Игрока, принимающего решение в вершине х, обозначим через г(х). Альтернативами в вершине х назовем номера дуг {(х,у) : у Є Fx} древовидного графа, при этом нумерация начинается с дуги, которая следует за единственной дугой, входящей в х (при нумерации считаем, что вершина х обходится по часовой стрелке, а в начальной вершине древовидного графа нумерация начинается с произвольной дуги). Пусть N = {1, 2,..., n} — множество игроков.
Определение 1. Коалиционным разбиением множества игроков называется набор множеств A = { Sj}jli таких, что Sj П Я = 0, j к, a USj = АГ. Элементы разбиения Sj будем называть коалициями. Простым коалиционным разбиением множества N назовем разбиение, содержащее не более одной коалиции с числом игроков, превышающем единицу. Коалиционное разбиение в вершине х обозначим через А(х).
Рассмотрим вариант образования простого коалиционного разбиения в играх с полной информацией. Пусть задана позиционная игра с полной информацией на конечном древовидном графе К с множеством игроков N. Отличие этой игры от обычной позиционной с полной информацией состоит в следующем. Перед тем как игрок делает ход, он объявляет остальным игрокам: либо он будет кооперироваться, либо будет играть индивидуально. Предполагается, что в отличие от [15] принятие решения кооперироваться либо играть индивидуально входит в стратегию игрока. В течение игрового процесса игроки, изъявившие желание кооперироваться, объединяются в одну коалицию с момента объявления ими такого желания. Если в некоторой вершине древовидного графа К игрок г принимает решение кооперироваться, то коалицию будут составлять игроки, принявшие такое же решение на предыдущих шагах игры, вместе с г. В данной постановке будем рассматривать случай, когда игрок, раз попавший в коалицию, не может ее покинуть до окончания игры.
Если игрок перед выбором альтернативы объявляет играть кооперативно, по к этому моменту никакая коалиция еще не сформирована, он действует индивидуально до тех пор, пока не появится другой игрок, желающий кооперироваться. Игрок действует исходя из интересов коалиции лишь в том случае, когда он входит в ее состав.
Построение слабого равновесия в многошаговой игре с простой коалиционной структурой
Дадим формальное определение игры с полной информацией на древовидном графе К. Определение 2. Многошаговой игрой п лиц с простой коалиционной структурой и с полной информацией называется древовидный граф К, на котором: задано разбиение множества вершин X на п + 1 множество Pi, Рг, ,Рп)Рп+і, где РІ, і Є N есть множество личных позиций игрока г, причем если х является вершиной либо четного ранга, либо нулевого и х Є Pi, то Fx С Pi, \FX\ = 2. Множество Pn+i = {х : Fx = 0} есть множество окончательных вершин, каждая из которых имеет четный ранг; в каждой вершине х Є X задано простое коалиционное разбиение А (ж) = {S(x), ii,..., i\N\s(x)\} множества игроков N, в котором в коалицию S(x) входят игроки, выбравшие в своих личных позициях нулевого и четного рангов первую альтернативу вдоль пути, ведущего в эту вершину; на множестве окончательных вершин Рп+\ заданы выигрыши игроков — вещественные неотрицательные функции hi(x), /12(3:),..., hn(x), х Є Рп+1- При этом если рассмотреть подмнооюество Рп+і(-) мноснсества окончательных вершин Pn+i, вершины которого могут реализоваться при выборе игроками произвольных альтернатив в вершинах четного и нулевого рангов и при фиксированных альтернативах в вершинах нечетного ранга, то на множестве Pn+i(-) выигрыши игроков совпадают. Другими словами, для любого игрока і Є N и для любых у Є Pn+i(-), z Є Рп+і(-), Рп+і(-) С Pn+\ имеет место hi(y) = Ы(г).
Определение 3. Стратегией щ(-) игрока і Є N назовем отображение, которое каждой вершине х Є Pi ставит в соответствие вершину у Є Fx либо вероятностное распределение рх на множестве Пусть щ{-) есть стратегия игрока г Є N. Определим множество Yf С Pi как множество всех личных позиций нечетного ранга этого игрока, которые могут реализоваться, если в вершинах четного или нулевого ранга игрок г выбирает вторую альтернативу («играть индивидуально»).
Определение 4. Под множеством стратегий индивидуального поведения Аг(щ(-)) игрока г, стесненным стратегией щ(-) будем понимать подмнооюество множества стратегий этого игрока, отличающихся от щ(-) только выборами в вершинах у Є Yi. Если щ(-) предписывает выбрать первую альтернативу в некоторой вершине z Є Pi четного или нулевого ранга, то полагаем Аг(щ(-)) — 0.
Пусть в некоторой вершине х древовидного графа К сформировалось простое коалиционное разбиение А(х) = {S(x),ii,... , гп_5}, 5(ж) = s, которое не изменяется до окончания игры. Рассмотрим на К подыгру п — s + 1 лиц, обозначаемую через К(х), начинающуюся в х, в которой коалиция S(x) является индивидуальным игроком. Найдем в подыгре К(х) ситуацию абсолютного равновесия. Пусть YlyeSix) г(у) представляет собой выигрыш коалиции S(x) в ситуации абсолютного равновесия, здесь у — окончательная вершина графа, которая реализуется в этой ситуации. С целью определения выплат игрокам коалиции S(х) составим вспомогательную кооперативную игру s лиц в форме характеристической функции v(-). Положим yeS(x) v(R) есть значение антагонистической игры, происходящей между коалициями R (максимизирующим игроком) и N \R (минимизирующем игроком); Вычислим компоненты вектора Шепли [57] — выплаты игрокам коалиции S(x): Для каждого набора стратегий й(-) = (zZi(-),..., йп(-)) в игре на древовидном графе К определим функции выигрыша игроков следующим образом. Предположим, что в ситуации й(-) реализуется простое коали ционное разбиение Л = {S,ij, (ij ф S)}, \S\ 2 и путь {0:xi,... ,xi}. Тогда есть значение вектора Шепли, вычисленного для коалиции S в подыгре K(yt), где yt — это первая вершина пути {О, xi,..., хі}, на котором сформировалось коалиционное разбиение А. В рассматриваемой постановке в качестве принципа оптимальности будем использовать так называемое слабое равновесие. Оно включает такие наборы стратегий игроков, в которых выигрыш отклонившегося индивидуального игрока (не принадлежащего коалиции) не увеличивается, при условии, что остальные игроки придерживаются фиксированных стратегий данного набора. Дадим формальное определение слабого равновесия.
Модель дуополии Курно как пример многошаговой игры с простой коалиционной структурой специального класса
С помощью характеристической функции рассчитываются выплаты игрокам, входящих в простую коалицию в соответствии с некоторым принципом оптимальности теории кооперативных игр. В качестве такого принципа оптимальности выберем вектор Шепли [57] в силу его единственности. Теперь каждому игроку в вершине ZQ предписан некоторый выигрыш.
Далее игровой процесс переходит в вершину z\ Є FZQ такую, что z\ = (ZQ\XZQ), где xZo — реализовавшаяся ситуация в игре T(ZQ, A(ZQ)). В вершине z\ определена одновременная игра Г( і), в которой коалиционное разбиение формируется аналогичным образом: игроки выбирают альтернативы «кооперироваться» или «не кооперироваться» одновременно и независимо друг от друга; игроки, выбравшие альтернативу «кооперироваться», формируют одну коалицию; игроки, выбравшие альтернативу «не кооперироваться», являются индивидуальными игроками. Таким образом формируется простое коалиционное разбиение A(zi) = {S(zi), {г{1},..., { NV\5(Z )і}}- В соответствии с коалиционным разбиением получаем игру Г(«і, A(zi)). Игроки S(z{), zj1,..., if}f\S/Zl\\ одновременно и независимо друг от друга выбирают свои стратегии из множеств стратегий, определенных в игре r( i). Формируется некоторая ситуация xZl, и каждый игрок получает соответствующий выигрыш. Доли выигрыша игроков, входящих в коалицию S(zi), получаем способом, аналогичным тому, которым получены выплаты в игре S(zo) (при фиксированных стратегиях игроков г 1,... ,і ш\3/2 \і составляется характеристическая функция игры T(zi,A(z{)), с помощью которой рассчитываются компоненты вектора Шепли для игроков коалиции S(zi)). После того, как все игроки получили выигрыш в игре r(zi), происходит переход к игре Г( 2), где Z2 = Ф( і; xZl) и так далее. Рассмотрим некоторую промежуточную вершину Zj. В этой вершине Zj Є Fz._x, zj — $(zj-u xz -J задана одновременная игра Г( -), в которой коалиционное разбиение формируется аналогичным образом: игроки выбирают альтернативы «кооперироваться» или «не кооперироваться» одновременно и независимо друг от друга; игроки, выбравшие альтернативу «кооперироваться», формируют одну коалицию; игроки, выбравшие альтернативу «не кооперироваться», являются индивидуальными игроками. Таким образом формируется простое коалиционное разбиение множества игроков A(ZJ) = {S(ZJ), {її3},..., {Йл$(г-)}} которое порождает непосредственно связанную с T(ZJ) одновременную игру T(zj,A(zj)). Игроки S(ZJ), {iz{},..., {hN\s(z)\} одновременно и независимо друг от друга выбирают свои стратегии из множеств ки S{ZJ), {%},... ,{iZ\N\S(Zj)\} получают выигрыши Hs{2j) = X) Н?, Для выделения выигрышей игроков, входящих в коалицию S(ZJ) фиксируются стратегии игроков, не входящих в коалицию S(ZJ), и составляется характеристическая функция v$(z.) игры T(ZJ,A(ZJ)) по правилу: Для любой непустой коалиции R С S(ZJ), vs(z.)(R) — максимальный гарантированный выигрыш коалиции R, то есть значение антагонистической игры между коалициями R (максимизирующим игроком; выигрыш коалиции R равен сумме выигрышей игроков этой коалиции) и S(ZJ)\R (минимизирующим игроком; выигрыш коалиции S(ZJ)\R равен выигрышу коалиции R, взятому с обратным знаком) при фиксированных стратегиях игроков, не входящих в коалицию Функция vs(z-), заданная на множестве коалиций, удовлетворяет условию супераддитивности: для любых непересекающихся коалиций R С S(zj) и Т с S(ZJ) vs{zj)(R U Т) 175(,,)(Д) + vs[Zj)(T). . (Z.)(0) = O. С помощью характеристической функции vS(Zj) игрокам коалиции S(ZJ) предписывается некоторый выигрыш в соответствии с вектором Шеп-ли. После этого процесс переходит в вершину Zj+i Є FZj) для которой Zj+i = Q(ZJ\XZ.). Игра прекращается, как только достигается окончательная вершина zi, то есть такая, для которой множество FZl пусто. Выигрыш игрока в игре Гд- представляет собой сумму выигрышей этого игрока в одновременных играх, определенных вдоль реализовавшегося пути. В каждой вершине z древовидного графа К каждому участнику игры известны стратегии остальных игроков, выбранные ими во всех одновременных играх, которые реализовались вдоль пути, ведущего в вершину z. В самой вершине z каждому из игроков не известен только тот выбор стратегий остальных игроков, который осуществляется в этой вершине.
Построение ситуации равновесия по Нэшу в многошаговой сетевой игре
Пусть N = {1,... ,п} — множество игроков. Построим дерево игры — конечный древовидный граф К = (X, F) с начальной вершиной XQ. Множество X есть множество вершин графа К, a F : X ь-» X есть точечно-множественное отображение, которое каждому элементу х Є X ставит в соответствие множество Fx вершин графа, следующих непосредственно за вершиной х. Вершины х древовидного графа К, для которых Fx = 0 будем называть окончательными (терминальными).
Множество X вершин древовидного графа К представим стандартным образом в виде объединения п + 1 непересекающихся множеств: где множество Pi — множество личных позиций игрока г, г Є N, а множество Рп+і — множество окончательных позиций древовидного графа В дальнейшем через г{х) будем обозначать игрока, который делает ход в вершине х в игре на древовидном графе К. Опишем пошаговое развитие игрового процесса. Начальный шаг. В начальной вершине XQ древовидного графа К определена сеть GXo = (N,6(XQ)). Через дх обозначим множество ребер сети GXo. Множество узлов N совпадает со множеством игроков (узел сети отождествляем с игроком), и 9{XQ) : дх ь- R — числовая функция, которую мы будем интерпретировать как функцию полезности. Шаг 1. Игрок г(х0) имеет ровно п альтернатив в вершине XQ\ не предпринимать никаких действий, при этом игровой процесс переходит в вершину г/ц Є FXo; разорвать связь с одним игроком j Є N, j i(xo), если ребро (i(xo),j) є gx; при этом игровой процесс переходит в вершину yij Є FXo; предложить одному игроку к, к ф I{XQ) установить связь (г(хо), к), если ребро (I(XQ), к) дх; при этом игровой процесс переходит в вершину у\k Є FXQ. Каждая из п вершин /ц, {yij}j, {уік}к принадлежит множеству FXo. В зависимости от выбора игроком г(хо) альтернативы, в вершинах множества FXo начальная сеть изменяется, соответственно множество ребер новой сети имеет следующий вид: дУп _ дх0 если игрок г(хо) не предпринимает никаких действий; 9Vlj — 9Х \ ( (жо)5І)5 если игрок г(хо) разрывает связь с игроком j; дУік — дХо у (г(жо), к), если игрок г(хо) устанавливает связь с игроком к. Таким образом, для вершины х\ Є FXo = {уп, {yij}j, {yik}k} множество ребер gXl однозначно определено. Если xi . Рп+і, то мы переходим к рассмотрению шага 2 для каждой вершины х\ Є FXQ. Этот шаг полностью аналогичен шагу 1, поэтому опуская изложение второго шага игры, рассмотрим некоторый шаг t. Шаг t (1 t I). Предположим, мы построили древовидный граф до вершин, которые можно достичь из начальной вершины XQ не более чем за t — 1 шагов. Пусть {XQ, Х±: ..., xt_i} — некоторая траектория из XQ построенного древовидного графа в вершину xt i, в которую можно попасть из XQ за t — 1 шаг. По построению во всех позициях xo,xi,..., Xt-\ соответствующие множества ребер дх, дХх,..., gXt x однозначно определены. Определим множество gXt. В вершине ж{_1 у игрока i(xt i) имеется ровно п альтернатив: не предпринимать никаких действий, при этом игровой процесс переходит в вершину уц Є FXt_x\ разорвать связь с одним игроком j Є N, j ф i(xt-\), если ребро (i(xt-i),j) Є gXt x\ при этом игровой процесс переходит в вершину ytj Є FXt_t; предложить одному игроку к, к ф- i(xt-i) установить связь (i(xt-i), к), если ребро (i(xt-i), к) $. gXt x\ при этом игровой процесс переходит в вершину ytk Є FXtl. Каждая из п вершин уц} {ytj}j, {ytk}к принадлежит множеству FXt_r. В зависимости от выбора игроком i(xt-i) альтернативы, в вершинах множества FXt_Y текущая сеть изменяется, соответственно множество ребер новой сети имеет следующий вид: дУп — gxt-i: если игрок i(xt-i) не предпринимает никаких действий; дУи = gXt-i (i(xt..i), j), если игрок i(xt-i) разрывает связь с игроком j; gVtk = gXt-i \j (i(xt-i), к), если игрок i(xt-i) устанавливает связь с игроком к. Таким образом, для вершины xt Є FXt_x = {ytl, {ytj}j, {ytk}k} множество ребер gXt однозначно определено. Если xt Рп+и т0 мы переходим к рассмотрению очередного шага построения древовидного графа для каждой вершины xt Є FXt_x. Если в вершине xt игровой процесс не заканчивается, т.е. если Xt Pn+i, то мы переходим к рассмотрению следующего шага игры, и построение игры на древовидном графе продолжается аналогичным образом. При t = I построение древовидного графа К закончено.