Петросян_Теория_игр

лишь от производственной программы). Для простоты будем счи­ тать, что выигрыш центра А0 удовлетворяет условию

/0(*)= £/(**),

где слагаемое 1(хк) интерпретируется как выигрыш игрока А0, полу­ чаемый от игрока Вк. Предположим также, что /(jtfc)^0 для всех хкеВк(ик) и 4(0) = 0, /(0) = 0, к=\, ..., п.

Подобно тому как это сделано в § 5, представим иерархическую игру п. 6.3 в виде бескоалиционной игры (п+1) лица в нормальной форме, где стратегиями игрока А0 будут векторы ие U, а стратеги­ ями игроков Вк — функции из соответствующих множеств. Постро­ им характеристическую функцию »(•) этой игры, следуя п. 9.2 гл. III. Для каждого подмножества S игроков v (5) будет равно значению (оно существует в условиях п. 6.3) антагонистической игры между коалициями S и N\S, в которой выигрыш коалиции S определяется как сумма выигрышей, принадлежащих множеству S игроков.

	Пусть N={A0,	Bit .... Вя}. Тогда
	S(A)=	sup	sup		{£['(**)+4(**)]|-
		п			U-1	)
	{ueU: Y.uk=b}		хкеВк{и,д
		*-1	*=1	п
	Заметим, что для всех Sc{Blt			.... Вя}, v(S)=0,		поскольку игрок
А0	всегда может распределить весь ресурс Ь среди членов коалиции
N\S, в которую		он входит,	лишив,		таким образом, коалицию

S ресурсов (т. е. А0 всегда может положить ик=0 для k:BkeS, что приводит к Вк(0) = 0 для всех BkeS). Рассуждая аналогично, имеем v(Ao)=0, поскольку игроки BV .... В„ всегда могут сделать выигрыш центра А0 равным нулю, полагая х*=0 для к= 1, ..., и (не производя

продукции). В том случае, когда коалиция S содержит центр А0, очевидно, что А0 будет распределять весь ресурс среди членов коалиции. Это соображение приводит к следующей формуле:

Z(S)=	sup	sup	J £	[l(xk)+lk(xk)]\
{ueU:	Z	«*=*} xkeBk(uk)	^k:BkeS	J
	k-BkeS	k:BkeS

для S:A0eS.

Можно показать, что при таком определении характеристичес-

200

кой функции С-ядро множества дележей

п

а = (ос0, а15 ..., а„):а,^0, г'=0, 1, ..., п, £ a,=«(JV)

1 = 0

всегда непусто.

6.4. Иерархические системы с подразделениями двойного подчи­ нения называются ромбовидными (рис. 21). Управление подраз­ деления двойного подчинения С зависит от управления В± и от управления i?2. Можно представить ситуацию, в которой центр Bv представляет интересы отрасли, а В2 — региональные интересы, включающие вопросы охраны окружающей среды. Простая ром­ бовидная система управления является примером иерархической системы с тремя уровнями принятия решений. На высшем уровне находится административный центр, располагающий материальны­ ми и трудовыми ресурсами. Он воздействует на деятельность двух подчиненных ему центров, принадлежащих следующему уровню. От решений, принимаемых этими центрами, зависит объем произ­ водства предприятия, находящегося на последнем уровне иерар­ хической системы.

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

постановке, условимся считать, что на		1-м шаге ходит				игрок А0
и выбирает элемент (стратегию) u = {ult		и2) из некоторого множест­
ва U, где U — множество	стратегий	игрока		А0.	Элемент и е U
ограничивает возможности выборов игроков Вх				и В2 на следующем
шаге. Другими словами, множество выборов игрока В± оказывается
функцией параметра ut (обозначим его через Bt				(uj),	и, аналогично,
множество выборов игрока В2 оказывается функцией параметра иг
(обозначимего через В2(и2)).	Через co^sB^(ux)		исо2еВ2(и2)			обозна­
чим элементы множества выборов игроков В1			и В2		соответственно.
Параметры оз^ и со2, выбираемые игроками В± и В2, задают ограни­
чения на множество выборов игрока С на 3-м шаге игры, т. е. это

множество оказывается функцией параметров со1			и ш2. Обозначим
его через С (сои со2), а элементы этого множества (производствен­
ные программы) — через «.
Пусть выигрыши всех игроков А0, Blt		B2,
С зависят только от производственной про­
граммы v, выбираемой игроком С, и равны
соответственно	lY (v), l2 (v), l3 (v), /4 (v),	где
Такую иерархическую игру можно предста­
вить как бескоалиционную игру четырех лиц
в нормальной форме, если считать стратеги­
ями игрока А0	элементы и=(и1, м2)е U, а стра­
тегиями игроков Bv B2 и С — функции со^ (мх),
а>2(и2) uvico^	ю2) со значениями в множествах

201

В1(и1), В2(и2), С{wу, со2) соответственно (обозначим множества таких функций через В1; В2, Q, которые каждому возможному выбору игрока (или игроков), находящегося на более высоком уровне, ставят в соответствие выбор данного игрока. Полагая

К,(и, Шу(), ш2(), »(•))«/((«((»!(иД со2(и2)), i=lA,

получим нормальную форму игры Г

Г= (С7. В15 В2, С, Klt К2, Къ, К4).

6.5.Будем искать ситуацию равновесия по Нэшу в игре Г. Для этого выполним вспомогательные построения.

Для каждой	фиксированной	пары (ш15	со2), (eols
со2) е (J Bx (иу) х В2 (и2) обозначим через v* (coy, со2) решение параме-
ueU
трической экстремальной задачи
	max /4 (v)=/4(«* (со!, оо2))-		(6-6)
	«бС(а>,,й)3)

(Считаем, что максимум в (6.6) достигается.) Решение «*(•)=«* (соу, со2) задачи (6.6) оказывается функцией параметров со,, а>2 и v* ()е С. Рассмотрим вспомогательную параметрическую (с параметрами

ы1( и2) неантагонистическую игру Г'(и1# M2 )= {BI(«I)> Вг("Д '2- 'з} двух лиц By и 2?2, где /2 = /2 («* (соу, со2)), /3 = /3 («* (Шц со2)). Стратеги­ ями игрока .#! в Г'(«1, и2) являются элементы coy el^ («Д стратеги­ ями В2 — элементы со2еВ2(ы2). Предположим, что в игре Г'(иу, и2) существует ситуация равновесия по Нэшу, которую обозначим (co*(uy), cof(u2)). Отметим, что со?() является функцией параметра MiHco.QeB,, i=l,2.

Пусть, далее, и* = (и*, и*) — решение следующей экстремальной задачи:

max ly{v*(a>t(иД со? (и2))).	(6.7)
ueV

Лемма. Совокупность (и*, cof(), со*(), «*(•)) является ситуаци­ ей равновесия по Нэшу в игре Г.

Доказательство. Согласно определению и* из (6.7) следует соотношение

Ку(и*, cof Q, ш?(), v*(.))=maxly(v*(cof(11Д a>J(u2)))>

^/х (•• (mf (иД со?(и2)))=^ (и. o)f Q, со?(.), «* (•))

для всех и е U. Поскольку cof (uf), cof (и*) образуют ситуацию равно­ весия по Нэшу во вспомогательной игре Г'(м|, и*2), для любой функции соу()еВу, сОу(и*) = сЪуеВу(и*) выполняются соотношения

К2(и*. шГ(•), <»?(•), v*(.)) = l2(v*(cof(uf), cof(uf))>

202

> / 2 («•(&!, « 2 *(K 2 *))) = * 2 ( U * , Ш 1 ( . ),		0 * 0 ,	»•(•))•
Аналогичное неравенство справедливо и для игрока Вг.
По определению функции v* из (6.6) имеем:
К4(М*, cof О, а>?0, » * 0 ) = / 4 ( » ' К ( 4 о* (»<?))) =
max	/4 («) > /4 (v) = * 4 (и*.	cof (•),	со? (.), « (•))
t;eC(cu*(«f),cu*(«J))
для любой функции i;()eC, v(cof(uf),		cof(uf))=veC(cof(uf),
co?(uf)).
Лемма доказана.		для каждой коалиции
6.6 Применяя	максиминный подход,
5 с {А0, Bv B2, Q	определим v'(S) как наибольший гарантирован­
ный выигрыш S	в антагонистической игре между коалицией S,

выступающей в качестве максимизирующего игрока, и коалицией

S' = {A0, BV Вг C}\S. Предположим, что существует такое v0e(дсо^ со2) для всех ш15 со2, что /,(«0) = 0, /=1, 2, 3, 4.

Будем различать два вида коалиций:

\)S:C$S;2)S:CeS.

В первом случае Sa{A0, Bv Bz) и игрок С, являющийся членом коалиции N\S, может выбрать стратегию vo:/f(vo) = 0, i=l, 2, 3, 4,

поэтому v'(S)=0.

Во втором случае определим характеристическую функцию v (S) следующими равенствами:

а) S= {С}
v'(S)=min	min	min	max /4(«)
uet/	a^eB,^,) ш2еВ2(и2) DEC(cDlt<U2)

(здесь и далее предполагаем, что все max и min достигаются);

б) S={A0, С)
i/(S)=max		min	min	max	(/x («) + /4 («));
net/	а^еВДи,) <D2EB2(U2) oeCCtBi.a)!)
в)5={51( С}
t/(S)=min		max	min	max	(l2(v) + U(v))'>
ueU	<U,EB,(U,)		<B2eB2(u2)	г е С ^ . ш ^
r)S={B2,C}
v'(S)=min		max	min	max	(/3(«) + /4(«));
net/	«UJEBJ^J		ш,бВ,(и,) »еС(ш,,ш2)
д) 5 = ^ , 5 2 , С}					4
v'(S)=min
		max	max	max £ №)'>
ueU		<u,6B,(u,) ш2еВ2(ц2) »6C(m„a)j) ,-_2

е)5={Л0 .^1. С}

203

v'(S)—ma\ max min max £ /,(»);

ж)5={Л0, ^2. С}

v'(S)=max max min max J] /,(«);

«et/ OjeBjCuj) o^Bjfu,) oeCfOj.ojj) f„i 3 4

3) S={A0, Bv B2, C}

«'(S^max max	max	4
		max У /,(«).

иб17 ш,еВ,(и,) eu2eB2(u2) oeCCo^.CDj) ,-=|

При таком определении характеристическая функция обладает свойством супераддитивности, т. е. для любых S, Ra {А0, Ву, Вг, С}, для которых Sf]R=0, имеет место неравенство v(S{]R)>v(S)+v(R).

§ 7. МНОГОШАГОВЫЕ ИГРЫ С НЕПОЛНОЙ ИНФОРМАЦИЕЙ

7.1. В § 1 — 4 рассматривались многошаговые игры с полной информацией, определенные на конечном древовидном графе Сг=(Х, F), в которых каждый из игроков в момент совершения своего хода точно знал, в какой позиции или в какой вершине дерева он находится. Именно поэтому удалось ввести понятие стратегии игрока /как однозначной функции ut(x), определенной на множестве

очередности Xt со значениями в множестве Fx. Однако если попы­ таться исследовать многошаговую игру, в которой игроки при совершении своих выборов не знают точно позиции, в которой они совершают ход, или могут лишь предполагать, что эта позиция принадлежит некоторому подмножеству А множества очередности Xh то реализация стратегии игрока как функции от позиции хеХ,

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

Пример 6. (Игра антагонистическая). Делая 1-й ход, игрок 1 вы­ бирает число из множества {1, 2}. Второй ход делает игрок 2. Зная выбор игрока 1, он выбирает число из множества {1, 2}. Третий ход опять делает игрок 1. Зная выбор игрока 2 и помня свой выбор, он выбирает число из множества {1, 2}. На этом игра прекращается, и игрок 1 получает выигрыш Н (игрок 2 — выигрыш (—Н), т. е.

204

-з

-2

г

-5

«

/

/

5

Рис. 22

игра антагонистическая), где функция Я определяется следующим образом:

Я(1,1,1)=-3,	Я(2,1,1) = 4,
Я(1,1,2)=-2,	Я(2,1,2) = 1,
Я(1,2,1) = 2,	Я(2,2,1)=1,	(7.1)
Я(1,2,2)=-5,	Я(2,2,2) = 5.

Граф G = (X, F) игры изображен на рис. 22. Кружками на графе изображены позиции, в которых ходит игрок 1, а квадратиками — позиции, в которых ходит игрок 2. Если множество Хх обозначить через X, множество Х2 — через Y и элементы этих множеств соот­ ветственно — через х е X, у е Y, то стратегия игрока 1 ы, (•) задается пятимерным вектором и1 (•)= {их (xt), ut (x2), uv (х3), ик (хА), иг (х5)},

предписывающим выбор одного из двух чисел {1, 2} в каждой позиции множества X. Аналогично стратегия ы2() игрока 2 пред­ ставляет собой двумерный вектор «2 (')=: {MI(}'I), "гСУг)}' предписы­ вающий выбор одного из двух чисел {1, 2} в каждой из позиций множества У. Таким образом, у игрока 1 в этой игре 32 стратегии, а у игрока 2 — 4 стратегии. Соответствующая нормальная форма игры имеет матрицу размера 32 х 4, которая, однако (это следует из теоремы п. 2.1), имеет ситуацию равновесия в чистых стратегиях. Можно убедиться, что значение рассматриваемой игры равно 4. Игрок 1 имеет четыре оптимальные чистые стратегии: (2, 1, 1, 1, 2), (2, 1, 2, 1, 2), (2, 2, 1, 1, 2), (2, 2, 2, 1, 2), у игрока 2 — две оптимальные стратегии: (1, 1), (2, 1).

Пример 7. Несколько изменим информационные условия приме­ ра 6. Игра антагонистическая. Делая первый ход, игрок 1 выбирает число из множества {1, 2}. Второй ход делает игрок 2. Зная выбор игрока 1, он выбирает число из множества {1, 2}. Третий ход делает игрок /. Не зная выбора игрока 2 и забыв свой выбор, он выбирает

205

Рис.23

число из множества {1, 2}. На этом игра прекращается и выигрыш определяется по формуле (7.1), так же как и в игре примера 6.

Граф G = (X,F) игры не изменяется, однако, находясь в узлах х2,
хъ, х^., х5 (на 3-м ходе игры), игрок 1 не может определить, в каком
из этих узлов он на самом деле находится, но, зная очередность
хода (3-й ход), он может быть уверен, что не находится в узле xt.		На
графе G мы обведем узлы х2,	х3, х±, х5 пунктирной линией (рис. 23).
В результате узел хх оказался обведенным кружком, что можно
интерпретировать как точное знание игроком 1 этого узла, когда он
в нем находился. Узлы ylt	уг обведены квадратиками, что также
означает, что игрок 2, находясь в одном из них, при совершении
своего хода может отличить его от другого. Объединяя узлы		хг,хг,

х4, хь в одно множество, мы иллюстрируем факт их неразличимо­ сти для игрока 1.

Множества, на которые разбиты узлы, будем называть инфор­ мационными множествами.

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

чисел (г,/), ге{1, 2},je{l,	2}, где число i выбирается в позиции		xt,
а число j на 3-м шаге одинаково во всех позициях х2,		хъ, хА,	х5.
Таким образом, выбор	числа j оказывается функцией	множества

206

и может быть записан как и {х2, х3, л;4, х5} =j. В данной игре у обоих игроков по четыре стратегии и матрица игры имеет вид

		(1.1)	(1.2)	(2.1)	(2.2)
(1.1)	Г	- 3	- 3	2	2П
(1.2)		- 2	- 2	- 5	- 5
(2.1)	[	4	1	4	1
(2.2)		1	5		1 5

В этой игре нет ситуации равновесия в чистых стратегиях. Значе­ ние игры равно 19/7, оптимальная смешанная стратегия игрока 1 есть вектор (0, 0, 4/7, 3/7), а оптимальная смешанная стратегия игрока 2 равна (4/7, 3/7, 0, 0). По сравнению с примером 6 гаран­ тированный выигрыш игрока 1 уменьшается. Это вызвано ухудше­ нием его информационного состояния.

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

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

Пример 8. Делая первый ход, игрок 1 выбирает число из множе­ ства {1,2}. Второй ход делает игрок 2, который, не зная выбора игрока 1, выбирает число из множества {1, 2}. Далее, совершая 3-й ход, игрок 1 выбирает число из множества {1, 2}, зная выбор игрока 2 и помня свой выбор на первом шаге. Выигрыш определяется так же, как и в примере 6 (рис. 24). Поскольку при совершении третьего хода игрок знает позицию, в которой он находится, позиции третье­ го уровня обведены кружками, два узла, в которых ходит игрок 2,

Рис. 24

207

-з -г г -5 ч i i

5

Рис. 25

мы обвели штриховой линией, включив их в одно информационное множество.

Пример 9. Делая первый ход, игрок 1 выбирает число из множе­ ства {1, 2}. Второй ход делает игрок 2, не зная выбора игрока /. Далее, совершая третий ход, игрок 1 выбирает число из множества {1, 2}, не зная выбора игрока 2 и не помня свой выбор на 1-м шаге. Выигрыш определяется так же, как в игре из примера 6 (рис. 25).

Здесь стратегия игрока 1 состоит из пары чисел (г, j), где /-выбор на 1-м шаге, a.j — на 3-м шаге игры. Стратегия игрока 2 есть выбор числа j на 2-м шаге игры. Таким образом, у игрока 1 — четыре стратегии, а у игрока 2 — две стратегии. Игра в нормальной форме имеет матрицу размера 4x2:

(1.1)	1	2
	Г —3	21
(1.2)	- 2	- 5
(2.1)	4	1 .
(2.2)	[ 1	5

Значение игры равно 19/7, оптимальная смешанная стратегия игрока 1 (О, 0, 4/7, 3/7), оптимальная стратегия игрока 2 (4/7, 3/7).

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

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

Рассмотрим антагонистическую игру двух лиц, в которой игрок 1 — один человек, а игрок 2 — команда из двух человек А и В. Все трое изолированы друг от друга (находятся в изолированных поме-

208

щениях) и не могут общаться между собой. В начале игры посред­ ник входит в помещение, где находится игрок 1, и предлагает ему выбрать число из множества {1, 2}. Если игрок 1 выбирает 1, то посредник заходит сначала в помещение, где находится А, и пред­ лагает ему выбрать число из множества {1, 2}, затем заходит к В и предлагает ему сделать выбор из множества {1, 2}. Если же игрок 1 выбирает 2, то посредник предлагает игроку В сделать выбор первому. После того как три числа выбраны, игрок 1 выиг­ рывает величину К(х, у, z), где х, у, z — выборы игрока 1 и членов команды 2 А и В соответственно. Функция К(х, у, z) определяется следующим образом:

*(1,1,1)=1,	*(1,2,1) = 7,
*(2,1,1) = 5,	*(2,2,1)=6,
*(1,1,2) = 3,	*(1,2,2) = 9,
К (2,1,2)= 1,	* (2,2,2) = 7.

Из правил игры следует, что, когда одному из членов команды А и В предлагается сделать выбор, он не знает, совершает ли он выбор на 2-м или 3-м шаге игры. Структура игры изображена на рис. 26. Таким образом информационные множества игрока 2 соде­ ржат вершины разного уровня, что соответствует незнанию номера хода в игре. Здесь игрок 1 имеет две стратегии. Игрок 2 имеет четыре стратегии, они состоят из всевозможных комбинаций выбо­ ров членов команды А, В, т. е. его стратегии суть пары (1,1), (1,2), (2Д), (2,2).

Для того чтобы понять, как определяются элементы матрицы выигрышей, рассмотрим ситуацию {2, (2,1)}. Так как игрок ) вы­ брал 2, то посредник идет в комнату к В, который согласно страте­ гии (2.1) выбирает 1. Далее он идет к А, который выбирает 2. Таким образом, выигрыш в ситуации {2, (2,1)} равен К (2, 1, 2)= 1. Матри-

Рис. 26

209