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

Тип работы:
Реферат
Предмет:
Кибернетика


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 021.8 + 025.1 ББК 78. 34
МНОГОШАГОВЫЕ СЕТЕВЫЕ ИГРЫ С ПОЛНОЙ ИНФОРМАЦИЕЙ 1
Петросян Л. А. 2, Седаков А. А. 3
(Факультет прикладной математики — процессов управления, Санкт-Петербургский государственный университет, Санкт-Петербург)
В статье рассматриваются многошаговые сетевые игры с полной информацией. В каждый момент игры задается текущая сетевая структура, связывающая игроков. Предполагается, что любое ребро сети имеет полезность (полезность одного игрока от связи со вторым), и игроки вправе изменять структуру сети на каждом шаге. Предлагается способ нахождения оптимального поведения игроков в играх такого типа.
Ключевые слова: сеть, сетевые игры, функция полезности, характеристическая функция, вектор Шепли, равновесие по Нэшу.
1. Построение многошаговой сетевой игры с полной информацией
Пусть N = {1,…, п} - множество игроков. Построим дерево игры — конечный древовидный граф К = (X, ^) с начальной вершиной хо [2, 6]. Множество X есть множество вершин графа К, а: X м X есть точечно-множественное отображение,
1 Текст приводится в соответствии с изданием «Математическая теория игр и ее приложения. — 2009. — Т. 1. № 2».
2 Леон Аганесович Петросян, доктор физико-математических наук, профессор (spbuoasis7@peterlink. ru).
3 Артем Александрович Седаков, кандидат физико-математических наук (formail@list. ru).
которое каждому элементу х Є X ставит в соответствие множествоХ вершин графа, следующих непосредственно за вершиной х. Вершины х древовидного графа К, для которыхХ = 0 будем называть окончательными (терминальными). Множество X вершин древовидного графа К представим стандартным образом в виде объединения п + 1 непересекающихся множеств: X = Рі и … и Рп и Рп+1, где множество Рі - множество личных позиций игрока і, і Є N, а множество Рп+і - множество окончательных позиций древовидного графа К. В дальнейшем через і(х) будем обозначать игрока, который делает ход в вершине х в игре на древовидном графе К.
Опишем пошаговое развитие игрового процесса.
1.1. ПОСТРОЕНИЕ ДРЕВОВИДНОГО ГРАФА
МНОГОШАГОВОЙ СЕТЕВОЙ ИГРЫ
Начальный шаг. В начальной вершине х0 древовидного графа К определена сеть СХ0 =, 6(х0)). Через дХ0 обозначим множество ребер сети СХ0. Множество узлов N совпадает со множеством игроков (узел сети отождествляем с игроком), и
9(хо): дХ0 м К — числовая функция, которую мы будем интерпретировать как функцию полезности.
Шаг 1. Игрок і(х0) имеет следующие п альтернатив в вершине хо:
• не предпринимать никаких действий, при этом игровой процесс переходит в вершину у11 Є ^Х0-
• разорвать связь с одним игроком ] Є N, ] = і(х0), если ребро (і(х0),і) Є дХ0- при этом игровой процесс переходит в вершину у у Є ^Хо-
• предложить игроку к, к = і(х0) установить связь (і(х0), к), если ребро (і(х0), к) Є дХ0- при этом игровой процесс переходит в вершину У1к ЄХо.
Таким образом, каждая из п вершин у11, {уу }у, {у1к }к принадлежит множествуХ0. В зависимости от выбора игроком і(хо) альтернативы, в вершинах множестваХ0 начальная сеть изменя-122
ется, соответственно множество ребер новой сети имеет следующий вид:
gy11 = gxo, если игрок i (xo) не предпринимает
никаких действий-
gyij = gxo (i (x0), j), если игрок i (x0) разрывает связь
с игроком j —
gyik = gxo у (i (x0), k), если игрок i (x0) устанавливает связь
с игроком k.
Следовательно, для вершины xi G F? o = {yii, {yij}j, {yik}k} множество ребер gx1 однозначно определено. Если x1 G Pn+1, то мы переходим к рассмотрению шага 2 для каждой вершины xi G Fxo. Этот шаг полностью аналогичен шагу 1, поэтому, опуская изложение второго шага игры, рассмотрим некоторый шаг t.
Шаг t (1 & lt- t ^ l). Предположим, мы построили древовидный граф до вершин, которые можно достичь из начальной вершины х0 не более чем за t — 1 шагов. Пусть {x0,xi,…, xt-i}
— некоторая траектория из х0 построенного древовидного графа в вершину xt-i, в которую можно попасть из Х0 за t — 1 шаг. По построению во всех позициях Х0, xi,…, xt-i соответствующие множества ребер gxo, gx1,…, gxt-1 однозначно определены. Определим множество gxt.
В вершине xt-i у игрока i (xt-i) имеются следующие n альтернатив:
• не предпринимать никаких действий, при этом игровой процесс переходит в вершину yti G Fxt-1 —
• разорвать связь с одним игроком j G N, j = i (xt-i), если ребро (i (xt-i), j) G gxt-1 — при этом игровой процесс переходит в вершину ytj G Fxt-1 —
• предложить игроку k, k = i (xt-i) установить связь (i (xt-i), k), если ребро (i (xt-i), k) G gxt-1 — при этом игровой процесс переходит в вершину ytk G Fxt-1.
Таким образом, каждая из п вершин у41, {у^-}^-, {у*& amp-}&- принадлежит множеству ^Х4_ 1. В зависимости от выбора игроком г (ж*-1) альтернативы, в вершинах множества ^Х4_ 1 текущая сеть изменяется, соответственно множество ребер новой сети имеет следующий вид:
дш = дж'-1, если игрок г (ж*-1) не предприни-
мает никаких действий- дУ1] = дх4−1 (?(х4−1), ]), если игрок г (ж*-1) разрывает связь
с игроком ]-
дугк = дх (-1 у (?(ж4−1), й), если игрок г (ж*-1) устанавливает
связь с игроком й.
Следовательно, для вершины ж* е ^с41 = {у*1, {у*,-},•, {у**-}& amp-} множество ребер дх однозначно определено. Если ж* е Рг+1, то мы переходим к рассмотрению очередного шага построения древовидного графа для каждой вершины ж* еС (_1. Если в вершине ж* игровой процесс не заканчивается, т. е., если ж* е Рг+1, то мы переходим к рассмотрению следующего шага игры, и построение игры на древовидном графе продолжается аналогичным образом. При? = I построение древовидного графа К закончено.
1.2. ОПРЕДЕЛЕНИЕ ИНДИВИДУАЛЬНЫХ ВЫПЛАТ ИГРОКАМ
Определение 1. Пусть Б С N. Вещественную функцию
V: X х 2 м м К, заданную на декартовом произведении множества X и множества всех подмножеств множества N и определенную по правилу
(1) '-(у, Б) = ^ % (у^
(«?)ейу: ??ез
где у е X, будем называть характеристической функцией. Здесь % (у) — значение функции полезности 0(у), определенной сетевой
124
игрой Су = (^ 0(у)), которое представляет собой полезность игрока г от связи с игроком ] в вершине у.
Задав конечное множество игроков N и функцию '-(у,), определенную по правилу (1), можно построить игру в форме характеристической функции, в которой для каждого игрока определены лишь полезности связей с другими игроками. Определим выплаты игрокам в сети. С этой целью выбираем некоторый принцип оптимальности теории кооперативных игр. Для простоты в качестве такого принципа оптимальности выберем вектор Шепли [9], и с его помощью определим дележ 7(у) = (71 (у),.. , 7га (у)), компоненты которого вычисляются по формуле:
(2) 7к (у) = Е (п — ^ - 1)! ['-(у. 3) — '-(у, 3 к)].
{3: ЗСМ, кеЗ}
Здесь в — число элементов множества Б, '-(у, Б) — характеристическая функция, определенная по правилу (1).
Распишем более подробно выражение, стоящее в квадратных скобках в правой части равенства (2). Подставив значения характеристической функции '-(у,) из (1) для любого у е X и к е N, имеем:
'-(у, Б) — '-(у, Б к) =
= Е ^ (у) — Е ^ (у) =
(«?)ейу: ??ез (??)ейу: ??е^к:
= Е ^ (у)+ Е ^ (у).
(?, к) еау: ?е3к (^,^'-)еау: ?е3к
С учетом полученного компоненты вектора Шепли записы-
125
ваются в виде:
(У) = ^
{5: ЙСМ, кей}
(3)
(П — 8)1(8 — 1)!
П!
^ ^ (У) +
(г, к)ЄдУ: гЄ5к
+ ^ ^ (У)
(^,І)Єйу: іЄ5к
где у е X, к е N.
Величина? 6^ (у) + X) 0*у (у) пред-
(?, к) еау: ?е3к (^,^'-)еау: ?е3к
ставляет собой вклад игрока к, если тот, присоединившись к коалиции Б к, приведет к образованию коалиции Б. Здесь первое слагаемое ^ ^ (у) представляет собой дополнитель-
(?, к) еа»: ?е3к
ную полезность игроков коалиции Б к, внесенную игроком к. Второе слагаемое ^ ^ (у) представляет собой допол-
(Мейу: ?е3к
нительную полезность игрока к, получаемую при присоединении к игрокам коалиции Б к.
Пусть в игре реализовался путь {жо, ж1,…, жг}. Тогда выигрыш игрока г е N вдоль этого пути определяется следующим образом:
^ 7?(ж), г е N
же{жо,…, жг}
где 7^(ж) представляет собой г-ю компоненту вектора Шепли, вычисленного по правилу (3) в сетевой игре = (^ 0(ж)).
1.3. ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ МНОГОШАГОВОЙ
СЕТЕВОЙ ИГРЫ С ПОЛНОЙ ИНФОРМАЦИЕЙ
Определение 2. Многошаговой сетевой игрой п лиц с полной информацией называется древовидный граф К, на котором:
• задано разбиение множества вершин X на п + 1 множество Ру
Р2,…, Рп, Рп+1, где P?, г е N есть множество личных позиций игрока г, множество Рп+1 = {ж: РХ = 0} есть множество окончательных вершин-
• в каждой вершине ж е X однозначным образом задана сеть
= (^ в (ж)): множество узлов сети N (множество игроков) и функция полезности в: ^ К.
Определение 3. Стратегией щ (-) игрока г е N назовем отображение, которое каждой вершине ж е P? ставит в соответствие вершину уе^с либо вероятностное распределение на множестве
= {Рс (у)}, у е *с, рс (у) ^ 0, Е рх (у) = 1.
уе^х
Для каждого набора стратегий (ситуации) и () =
(и1(),…, ип ()) в игре на древовидном графе К определим функции выигрыша игроков следующим образом. Пусть в ситуации и (-) = (и1(-),…, ига (-)) реализовался некоторый путь {ж0,ж1,…, ж^} из начальной вершины ж0 в окончательную ж^. Тогда функция выигрыша игрока г:
7?(ж), г е N.
же{жо,…, жг}
Здесь 7?(ж) есть выплата игроку г, которая получена как г-ая компонента вектора Шепли, рассчитанного по характеристической
127
функции '-(ж, ¦) для сетевой игры = (^ в (ж)), заданной в вершине ж (см. (3)).
Определение 4. Набор стратегий и*() =
(«!(•),…, м*(-),…, иП (-)) называется равновесием по Нэшу в многошаговой сетевой игре на древовидном графе К с начальной вершиной ж0, если
^(и*(-)|М-)) & lt- ^?(«*(-)) для любых г е N и любых допустимых щ.
2. Построение ситуации равновесия по Нэшу в многошаговой сетевой игре
Предположим, что длина игры равна I + 1. Для определения оптимального поведения игроков будем использовать концепцию абсолютного равновесия в конечношаговой игре с полной информацией.
Введем функцию Беллмана [1, 5] ^ как выигрыш игрока г в ситуации равновесия по Нэшу в игре за I — Ь шагов (положим ^?+1 = 0). Значения функции Беллмана ^ во всех вершинах древовидного графа К определяются стандартным образом методом обратной индукции (решая уравнение Беллмана от окончательных вершин графа К к начальной при граничном условии).
В данном случае для любой окончательной вершины жг е Рп+1 граничное условие выглядит следующим образом:
^?(жг)= 7?(жг), г е N.
В промежуточной вершине ж* древовидного графа К функция Беллмана удовлетворяет следующему рекуррентному соотно-
128
шению:
^(сО (ж*) = тах ^?(ж4)(ж*) + =
(4) = Тг (ж4)(ж*) + тах =
= ^?(х г)(ж*)+ ^*+1)(у).
Для игрока ] = г (ж*) значения функции Беллмана определяются по правилу:
(5) ^(ж*) = Ц (ж*) + ^+1 (у).
Решая уравнение Беллмана, находим значения, Ь = 0,…, I, г е N. При Ь = 0 уравнение решено. Вектор (^& gt-5(ж0),…, ^& gt-П (ж0)) назовем значением многошаговой сетевой игры с полной информацией.
Вместе с нахождением значения многошаговой сетевой игры определяются и оптимальные стратегии игроков, которые по построению образуют ситуацию абсолютного равновесия в игре: в каждой вершине ж е X древовидного графа К игрок г (ж) выбирает вершину у е Рх согласно правилу (4). В ситуации абсолютного равновесия реализуется некоторый путь в графе из начальной вершины в окончательную. Такой путь будем называть оптимальным путем в многошаговой сетевой игре.
На основании приведенного алгоритма имеет место следующее утверждение.
Теорема 1. Построенная ситуация и*(-) =
(«!(•),… ,»?('-)), в которой для каждой вершины ж е Рп+ъ стратегия и* (ж) игрока г определяется по правилу
(ж) = y,
где у находится из соотношения (4), образует ситуацию абсолютного равновесия по Нэшу в многошаговой сетевой игре, заданной на древовидном графе К.
Однако, не всегда гарантируется единственность абсолютного равновесия по Нэшу в многошаговой сетевой игре.
Замечание 1. Пусть наряду с вершиной y G, доставляющей максимальное значение функции ^*(Х1}(у) в (4), вершина y G также является точкой максимума этой функции. Тогда с очевидностью выполняется следующее равенство:
^Й)(у) = ^Й)(у)& gt-
которое, в свою очередь, приводит к одному и тому же значениюt (& gt-t)(xt). Следовательно, игроку, принимающему решение в вершине ж* (игроку i (xt)), можно выбрать любую вершину y G, доставляющую максимум функции (у) в (4).
В тех же вершинах у и у для отличных от i (xt) игроков j G N, j = i (xt) в общем случае справедливо следующее соотношение:
^+1(у) = ^j+1(y).
Данное обстоятельство означает, что выбор игроком i (xt) вершины из множества
(6) I (xt) = arg max (У)
влияет на решения последующих игроков (в силу различия значений функции Беллмана этих игроков в точках множества I (ж*)). Таким образом, в общем случае в многошаговой сетевой игре имеет место неединственность оптимального пути с различными значениями функции выигрыша.
Случай неединственности оптимального пути легко обходится введением понятия индифферентного равновесия по Нэшу в многошаговой игре с полной информацией [8]. Поскольку в общем случае |I (ж*)| ^ 1, предполагается, что игроку i (xt) безразличен выбор вершины из множества I (ж*). Предпишем i (xt) выбирать эти вершины с одинаковыми вероятностями, т. е. РХ1 (у) = 1/|I (ж*)|, для любого y G I (ж*). Тогда в промежуточной 130
вершине ж* древовидного графа К функция р- удовлетворяет аналогичному (4) рекуррентному соотношению:
(7) Р-(*) (ж*)= 7 г (х0(ж*) + ^ ^*+0(У).
11 (Х*)І уЄ/(*)
Для игрока і = і (ж*) значения функции р определяются по правилу:
(8) РІ(ж*)= 7?(ж*) + ^ РІ+1(У).
1 1 ! 1 уЄ/(*)
Решая уравнение Беллмана, находим значения р-,? = 0,…, I, і Є N. При? = 0 уравнение решено. Вектор (р1 (жо),…, рП (ж0)) также назовем значением многошаговой сетевой игры с полной информацией.
По аналогии с теоремой 1 справедлива следующая теорема. Теорема 2. Построенная ситуация и/Е (¦) =
(и{Е ('-),…, иПЕ ('-))& lt- в которой для каждой вершины ж Є Рг+ъ стратегия и/Е (ж) игрока і определяется по правилу
(ж) = {РХ (у)}, у е 1 (ж), РХ (у) = ^,
где вершины у находятся с использованием соотношений (6)-(7), образует ситуацию индифферентного равновесия по Нэшу в многошаговой сетевой игре, заданной на древовидном графе К.
3. Численный пример многошаговой сетевой игры с полной информацией
Для иллюстрации алгоритма построения решения сетевой игры приведем контрольный пример.
Рассмотрим трехшаговую сетевую игру. Пусть N = {1, 2, 3} есть множество игроков. Построим древовидный граф К с начальной вершиной в ж0.
Пусть в ж0 задана сеть, представленная на рис. 1.
Рис. 1. Сеть Сх°
Множество ребер ^х° = {(1, 2), (2, 3), (3, 2)}. Зададим функцию полезности в (ж0) в виде матрицы 0(ж0):
020 0(ж0) = (0 0 1 I.
010
Предположим, что в начальной вершине ходит игрок 1, у которого есть три альтернативы: (1) не предпринимать никаких действий (при этом игра переходит в вершину ж1), (2) разорвать связь с игроком 2 (при этом игра переходит в вершину ж2), (3) наладить связь с игроком 3 (при этом игра переходит в вершину жз). В зависимости от выбора альтернативы игроком 1 имеем:
дх1 = ^х°, если игрок 1 выбирает первую альтернативу
в вершине ж0-
дх2 = ^х° (1, 2), если игрок 1 выбирает вторую альтернативу в вершине ж0-
дхз = ^х° у (1, з), если игрок 1 выбирает третью альтернативу в вершине ж0.
Пусть функции полезностей 0(ж1), 0(ж2) и 0(ж3) заданы в виде следующих матриц:
(c)(жі) =
0 -3 -1 0 3 -2
2 0 2 І, (c)(Ж2) = (c)(жз) = 1 -1 0 1
5 1 0 3 1 0
Будем считать, что вершины Ж1 и жз являются окончательными, а вершина ж2 является личной позицией игрока 2. В ж2 второй игрок имеет три альтернативы: (1) не предпринимать никаких действий (при этом игра переходит в вершину ж4), (2) наладить связь с игроком 1 (при этом игра переходит в вершину ж5), (3) разорвать связь с игроком 3 (при этом игра переходит в вершину жб). В зависимости от выбора альтернативы игроком 2 имеем:
дХ^ = дХ2, если игрок 2 выбирает первую альтернативу
в вершине ж2-
дХ5 = дХ2 и (2,1), если игрок 2 выбирает вторую альтернативу в вершине ж2-
дХ6 = дХ2 (2, 3), если игрок 2 выбирает третью альтернативу в вершине ж2.
Пусть функции полезностей 0(ж4), 0(ж5) и 0(жб) заданы в виде следующих матриц:
0 -3 -1 0 -1 -1
2 0 2 І, (c)(жб) = (c)(же) = І -1 0 2
5 1 0 2 4 0
Будем считать, что вершины ж4 и жб являются окончательными, а вершина ж5 является личной позицией игрока 3. В ж5 третий игрок имеет три альтернативы: (1) не предпринимать никаких
133
действий (при этом игра переходит в вершину ж7), (2) наладить связь с игроком 1 (при этом игра переходит в вершину же), (3) разорвать связь с игроком 2 (при этом игра переходит в вершину жд). В зависимости от выбора альтернативы игроком 2 имеем:
дХ7 = дХ5, если игрок 3 выбирает первую альтернативу
в вершине ж5-
дх8 = дХ5 у (3,1), если игрок 3 выбирает вторую альтернативу в вершине ж5-
дХ9 = дХ5 (3, 2), если игрок 3 выбирает третью альтернативу в вершине ж5.
Пусть функции полезностей 0(ж7), 0(ж8) и 0(жд) заданы в виде следующих матриц:
/ 0 -3 -1
0(ж7) = 0(ж8) = 0(жд) = I 2 0 2
V 5 1 0
Будем считать, что вершины ж7, же, жд являются окончательными вершинами. Тогда множества личных позиций игроков Р1, Р2, Рз и множество окончательных вершин Р4 имеют вид:
Р = {жо}, Р2 = {ж2}, Рз = {ж5}, Р4 = {ж1,жз, ж4, жб, ж7, ж8,жд},
а древовидный граф К представлен на рис. 2.
Для начала вычислим индивидуальные выплаты игрокам в каждой вершине графа К. Рассмотрим вершину жо. Построим характеристическую функцию по правилу (1):
¦и (жо, {1, 2, 3}) = 4, и (жо, {1, 2}) = 2,
¦и (жо, {1, 3}) = 0, и (жо, {2, 3}) = 2,
¦и (жо, {1}) = -и (жо, {2}) = -и (жо, {3}) = 0.
Х-* Д-8
Л'-Л- _^'Л
у
Л. *
Рис. 2. Древовидный граф К
Индивидуальные выплаты игрокам в хо вычисляются в соответствии с вектором Шепли по правилу (3). Таким образом получаем вектор:
7(хо) = (1, 21).
Аналогичным образом вычисляются индивидуальные выплаты игрокам в остальных вершинах древовидного графа К. Приведем их окончательные значения:
7(хі) = (-1,5, 0,1,5), т (х2) = (0,1,1),
7(хэ) = (0,5, 2,5, 0), 7(х4) = (0,1,5,1,5), 7(хб) = (-0,5, 2,5, 3),
7(ха) = (0, 2, 2),
7(х7) = (1, 2,5,1,5), 7(хв) = (3,5, 2,5, 4),
7(х9) = (1, 2,1).
После определения выплат игрокам в каждой вершине графа К построение ситуации абсолютного равновесия в многошаговой сетевой игре не представляет особых трудностей. Данная процедура полностью аналогична задаче отыскания ситуации абсолютного равновесия в многошаговой игре с полной информацией с той лишь разницей, что в классической постановке выигрыши игроков заданы в окончательных вершинах графа игры, а в промежуточных полагаются равными нулю. Искомая ситуация абсолютного равновесия в многошаговой сетевой игре находится с использованием соотношений (4)-(5).
Оптимальные стратегии игроков следующие:
«1(Ж0) = Ж2, и2(Ж2) = Жб, из (ж5) = Же.
В ситуации абсолютного равновесия (иЗ, иЗ, и3) реализуется оптимальный путь {жо, Ж2, Жб, ж8} из начальной вершины жо в окончательную же. Вдоль оптимального пути игра развивается следующим образом. В начальный момент задана сеть СХ0, указанная на рис. 1. Далее игрок 1 разрывает связь со вторым игроком, что приводит к сети СХ2, показанной на рис. 3. После этого делает
Рис. 3. Сеть СХ2
ход игрок 2, который за свой ход устанавливает связь с игроков 1, что приводит к сети СХб, показанной на рис. 4. И, наконец,
Рис. 4. Сеть СХб
своим ходом игрок 3 заканчивает игру, установив связь с игроком
1, что приводит к сети СХ8, показанной на рис. 5.
Значение многошаговой сетевой игры равно (4,8,9), а пошаговые индивидуальные выплаты следующие: 7(жо) =
136
Рис. 5. Сеть Gx8
(1, 2,1), y (x2) = (0,1,1), Y (Х5) = (-0,5, 2,5, 3), 7(xs) = (3,5, 2,5, 4).
Литература
1. БЕЛЛМАН Р. Динамическое программирование. — М, 1960.
2. ПЕТРОСЯН Л.А., КУЗЮТИН Д. В. Игры в развернутой форме: оптимальность и устойчивость. — СПб, 2000.
3. ПЕТРОСЯН Л.А., СЕДАКОВ А.А., СЮРИН А. Н. Многошаговые игры с коалиционной структурой // Вестник СПбГУ. — 2006. — Т. 10. — № 3. — С. 97−110.
4. ADJEROH D., KANDASWAMY V. Game-Theoretic Analysis of Network Community Structure // International Journal of Computational Intelligence Res. — 2007. — V. 3.
— № 4. — P. 313−325.
5. BELLMAN R.E. On the Theory of Dynamic Programming.
— Proceedings of the National Academy of Sciences, 1952.
6. KUHN H.W. Extensive Games and Problem Information // Ann. Math Studies. — 1953. — V. 28. — P. 193−216.
7. NASH J. Non-cooperative Games // Ann. of Math. — 1951. -V. 54. — P. 286−295.
8. PETROSJAN L.A., MAMKINA S.I. Value for the Games with Changing Coalitional Structure // Games Theory and Applications. — 2005. — V. 10. — P. 141−152.
9. SHAPLEY L.S. A Value for n-Person Games. Contributions to the Theory of Games II, Princeton: Princeton University Press. 1953. — P. 307−317.
10. VIVES X. Nash equilibrium with strategic complementarities // Journal of Mathematical Economics. — 1990. — V. 19. — № 3. -P. 305−321.
11. VIVES X. Strategic Complementarities in Multi-Stage Games. CEPR Discussion Papers 5583. C.E.P.R. Discussion Papers, 2006.
MULTISTAGE NETWORKING GAMES WITH FULL INFORMATION
Leon Petrosjan, Faculty of Applied Mathematics and Control Processes, Saint-Peterburg State University, Doctor of Sc., professor (spbuoasis7@peterlink. ru).
Artem Sedakov, Faculty of Applied Mathematics and Control Processes, Saint-Peterburg State University, Cand. Sc. (formail@list. ru).
Abstract: Multistage networking games with full information are considered. The network structure which connects the players is defined at every time moment. We assume that each verge has a utility (the player’s profit from the connection with another player), and players have a right to change the network structure at every stage. The approach to define optimal players' behavior is proposed.
Keywords: network, networking games, utility, Shapley value, Nash equilibrium.

ПоказатьСвернуть
Заполнить форму текущей работой