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

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

Строго говоря, интеграл в (3.1) должен браться по мере /JXV на декартовом произведении Хх Y. Однако согласно правилам антагонистической игры смешанные стратегии (меры) fiiv игроками выбираются одновременно и независимо друг от друга, т. е. вероятностные меры ц. и v — стохастически независимы.

Определение. Ситуацией (ц, v) в смешанных стратегиях назы­ вается пара вероятностных мер fieX.veT, которые стохастически независимы.

Таким образом, в ситуации (ц, v) в смешанных стратегиях выиг­ рыш К(ц, v) равен повторному интегралу (3.1). Одноточечные множества принадлежат (Т-алгебре подмножеств множества страте­ гий, на которой определяются вероятностные меры, поэтому каж­ дой чистой стратегии х(у) можно поставить в соответствие вероят­ ностную меру p.xeX(vyeY), сосредоточенную в точке хеХ (yeY). Отождествляя стратегии х и цх, у и v,, видим, что чистые стратегии являются частным случаем смешанных, т. е. справедливы включе­ ния X<zX, Ya Y. Тогда выигрыши игрока 1 в ситуациях (х, \) и (ц, у) равны соответственно математическим ожиданиям:

K(x,v)=K(nx>v) = H(x,y)dv(y);

(3.2)

ч	(3.3)
К(ц, у) =К(ц, v,) = H(x, y)dii(x),

где интегралы в (3.1), (3.2), (3.3) понимаются в смысле Лебега — Стилтьеса. Если же распределения ц(х), v(y) имеют плотности f(x) и g(y), т. е. dp.(x)=f(x)dx и dv(y)=g(y)dy, то интегралы в (3.1), (3.2), (3.3) понимаются в смысле Римана — Стилтьеса. Та­ ким образом, Гс Г — подыгра своего смешанного расширения Г. Будем считать, что все интегралы в (3.1) (3.2), (3.3) существуют, каковы бы ни были вероятностные меры ц и v.

Определение. Пусть Г= (X, Y, Н) — антагонистическая игра,

а Т=(Х, Т,	К)—ее смешанное расширение. Тогда ситуация
(ц*, v*) eXx	Т называется ситуацией равновесия в игре Г в смешан­

ных стратегиях, если для всех fieXuve ¥ выполняются неравенства

К(ц, v*) ^К(ц*, v*) *$К(ц*, v),

(3.4)

т. е. (ц*. v*) — ситуация равновесия в смешанном расширении игры

70

Г, a fi*(v*) — оптимальная стратегия игрока 1 (2) в Г. Аналогично, ситуация (//*, v'e)eXxf) называется ситуацией е-

равновесия в игре Г в смешанных стратегиях, если для всех цеХ

Hvef выполняются неравенства

К(ц, у\) - г ^ К ( А , v.) ^К(ц\, v) +в,

(3.5)

т. е. f£, (vf) — е-оптимальная стратегия игрока 1 (2) в Г.

3.3. Подобно тому, как это доказывалось для матричных игр,

можно показать, что если функции выигрыша игр Г=(Х, Y,	Н)
и Г' = (X, Y, Н) связаны равенством Н(х, у) =аН(х, y)+fl,a>0,	то

множества ситуацийравновесия у игр Г и Г' в смешанных стратеги­ ях совпадают, т. е. Z(F') =Z(T), а значения игр связаны соотноше­ нием »(Р)=а«(Г)+0 (см. § 4 гл. I).

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

Теорема. Для того чтобы пара (ц*, v*), ц*еХ, v*e? была ситуацией равновесия (в-равновесия) в смешанных стратегиях в игре Г, необходимо и достаточно для всех хеХ, yeY выполнение нера­ венств

К(х, v*) <K(fi*. v*) <К(ц*. у);		(3.6)
(К(х, *)-в^К(ц*.	v*) <К(ц*. у) + е).	(3.7)

Доказательство. Необходимость теоремы очевидна, по­ скольку чистые стратегии являются частным случаем смешанных. Докажем достаточность для (3.6) (для (3.7) это доказывается аналогично). Пусть ju и v — произвольные смешанные стратегии игроков 1 и 2 соответственно. Тогда из (3.1), (3.2) и (3.6) получаем

K(/i, v*)= \к(х, v*)dn(x)^K(p*. v*),

X

Y

Отсюда вытекают неравенства (3.4), что и требовалось доказать. Из теоремы, в частности, следует, что если (х*. у*) — ситуация

равновесия (е-равновесия) в чистых стратегиях в игре Г, то она является и ситуацией равновесия (е-равновесия) в смешанном рас­ ширении Г, при этом значение игры v сохраняется.

Заметим, что смешанное расширение Г является антагонистичес­ кой игрой, поэтому относительно Г справедливо понятие вполне определенной игры (п. 2.1), а также теорема п. 2.5, только речь теперь идет о ситуации равновесия и значении игры в смешанных стратегиях.

71

3.5.Теорема. Для того чтобы игра Г= (X, Y, Н) имела значение

vв смешанных стратегиях, т. е. sup infK(ji, v)=inf supK(ji, v)=«, необходимо и достаточно выполнение равенства

sup inf K(ii, у) =inf sup K(x, v) =v.		(3.8)
II У	УХ

Если при этом игроки имеют оптимальные стратегии, то внешние экстремумы в (3.8) достигаются и равенства

MK(n*,y)=v,	(3.9)
У
sopK(x,v*)=v	(3.10)

х

являются необходимыми и достаточными условиями оптимально­ сти смешанных стратегий ц* е X и v* e У.

Доказательство. Пусть v — значение игры. Тогда по опреде­ лению

i>=sup inf К(ц, v).

(3.11)

Для фиксированной стратегии ц множество {К(ц, v)\veY} —вы­ пуклая оболочка чисел К(ц, у), yeY. Так как точная нижняя гра­ ница любого множества действительных чисел совпадает с точной нижней границей выпуклой оболочки этих чисел, то

inf К(ц, vj = inf K(fi, у).		(3.12)
vef	yeY

Равенство (3.12) можно получить также из следующих соображений. Поскольку Ус У, имеем

inf K(ii,	v)^MK(/i,y).
vef	yeY

Предположим, что неравенство строгое, т. е.

inf K(\L, v) <inf K(fi, у).

V у

Это значит, что при некотором достаточно малом е>0 выполняется неравенство

inf К(ц, v) + г < inf K(\i, у).

V

у

Таким образом, при всех yeY

72

К(ц. у) > inf К(ц, у) + е.

(3.13)

Теперь, переходя к смешанным стратегиям в (3.13), получаем

inf K((i, v) ^ inf К(ц. v) + в.

УV

Полученное противоречие и доказывает (3.12). Возьмем супремум по и в равенстве (3.12). Тогда

«=sup inf К(и, у).

ЧУ

Аналогично доказывается правое из равенств в (3.8). Обратно, если (3.8) выполнено, то из (3.12) следует, что « — значение игры.

Пусть теперь и*, v* — оптимальные стратегии игроков 1 и 2 со­ ответственно. По теореме п. 3.4 гл. I внешние экстремумы в (3.8) достигаются, а (3.9), (3.10) являются необходимыми и достаточ­ ными условиями оптимальности смешанных стратегий /(* и v*.

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

Следствие. Для любой антагонистической игры Г=(Х, Y, Н), имеющей значение v в смешанных стратегиях, справедливо неравен­ ство

sup inf H(x, y)^:v<inf	sup H(x, у).	(3.14)
х у	у х

Доказательство. Из теоремы п. 3.5 следует:.

sup inf Н(х, у) <sup inf K(u, y)=v=

X у	НУ
=inf sup K(x,	\) <inf sup H(x, у).
v х	у х

Ъ.6. Из (3.14) следует один из способов приближенного решения антагонистической игры. Действительно, пусть внешние экстрему­ мы в (3.14) достигаются, т. е.

v~ =max inf Н(х, у) =inf H(x°, у);			(3.15)
х	у	у	(3.16)
v+ =min sup Н(х, у) = sup H(x, y°)
у	х	х

и пусть a=v+ —v~. Тогда максиминная стратегия х° игрока 1 и ми-

73

нимаксная стратегия у° игрока 2 с точностью до а описывают оптимальное поведение игроков и могут быть взяты в качестве приближенного решения игры Г. Таким образом, в этом случае задача сводится к нахождению максиминных и минимаксных стра­ тегий игроков 1 и 2 соответственно, а точность приближенного решения определяется величиной a=v+—v~, при этом значение игры v согласно (3.14) лежит в интервале ve[v~, v+]. Способам нахождения решения задач (3.15), (3.16) посвящена теория минимакса [31, 30].

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

Определение. Пусть Г= (X, Y, Н) — антагонистическая игра. Тогда чистую стратегию х0еХ (y0eY) игрока 1 (2) называют точкой концентрации его смешанной стратегии ц (х), если р. (х0) >0

(У(УО)>0).

Определение. Чистая стратегия х0еХ (y0eY), где X (соот­ ветственно Y) — топологическое пространство, называется точ­ кой спектра смешанной стратегии ц (v), заданной на борелевской о-алгебре подмножеств множества X (Y), если для любой измери­ мой окрестности ш точки х0 (у0) имеет место неравенство

/z(o))= | ф(*)>0(у(а>)=	| dv(y)>0).
т	а

Спектром смешанной стратегии ц (v) назовем наименьшее за­ мкнутое множество, ц-мера (v-мера) которого равна единице.

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

Спектр смешанной стратегии ц (соответственно v) будем обозна­ чать Хр (Г,).

Докажем аналог теоремы п. 7.6 гл. I о дополняющей нежест­ кости для бесконечных игр.

Теорема. Пусть Г=(Х, Y, Н) — антагонистическая игра, име­

ющая значение v. Тогда, если х0еХ, a v* — оптимальная смешанная
стратегия игрока 2 и
K(x0,v*)<v,	(3.17)

то х0 не может быть точкой концентрации какой-либо оптималь­ ной стратегии игрока 1.

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

Доказательство. Из оптимальности смешанной стратегии

74

v* £ Г следует, что для всех хеХ выполняется неравенство

К(х, V * ) < D .

Интегрируя его по оптимальной смешанной стратегии (мере) /х* игрока / на множестве Х\{х0}, получаем

J K(x,v*)dn*(x)^v J dpL*(x).

Пусть /I*(JCO)>0, т. е. JC0 —точка концентрации оптимальной сме­ шанной стратегии /х* игрока 1. Тогда из (3.17) имеем

К(х0, v*)n* (x0)<vn* (х0).

Складывая два последних неравенства, получаем противоречие

J K(x, v*)dn*(x)=K(jx*, v*)=v<v.

X

Поэтому /i*(xo)=0 для всех оптимальных стратегий ц*еХ.
3.8. Для бесконечных антагонистических игр можно ввести по­
нятие доминирования стратегий аналогично тому, как это делалось
в § 8 гл. I.	_

Определение. Стратегия ц±еХ игрока 1 строго доминирует стратегию (i2e X (JJ.^ fi2), если

H(jii,y)>H(ji2,y)

для всех yeY. Аналогично, стратегия v^Y игрока 2 строго до­ минирует стратегию v2eY (vl>v2), если

Н(х, У1 )<Я(Х, v2)

для всех хеХ. Стратегии ц2 и v2 называются строго доминиру­ емыми, если существуют Цу>ц2и Vj>v2.

Если последние неравенства выполняются как нестрогие, то говорят, что цу доминирует ц2 (ju1^=/i2) и vx доминирует v2 (vx^v2).

Приведем без доказательства теоремы о доминировании, аналогичные теоремам п. 8.3.

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

Теорема. Пусть Г=(Х, Y, Н) — бесконечная антагонистическая игра, имеющая решение (X и Y — топологические пространства), и каждый элемент открытого множества Х° с X доминируется некоторой стратегией ц°, спектр которой не пересе­ кается с Х°. Тогда всякое решение игры Г'=(Х\Х°, Y, Н) является решением игры Г.

Аналогичная теорема верна и для стратегий игрока 2.

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

75

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

Пример 9. (Игра, не имеющая значения в смешанных стратеги­ ях.) Рассмотрим игру Г = (Х, Y, Н), где Х= У= {1, 2...} — множество натуральных чисел, а функция выигрышей имеет вид

1, если х>у, Н(х, у)=< 0, если х=у,

* —1, если х<у.

Эта игра не имеет значения в чистых стратегиях. Покажем, что она* не имеет значения и в смешанных стратегиях.

	Пусть fi — произвольная			смешанная стратегия			игрока 7,j
и	dfi(x) = 8x, где	8Х^0	и	£ 8Х=1. Возьмем		е>0	и найдем
у,	такое, что			*"'
			X 8х>1-в.
Тогда
	K(n,yd=t		&*Н{х,уд= Е		8xH(x,yJ	+
		х-1		х^у,
	+ £	8хЩх,у,)=-		£ 8Х+ X 8х<-1		+ 2е.
	х>у,			х<уь	х>у,

В силу произвольности е>0 и так как Н(х, у) не принимает значе­ ний, меньших — 1, имеем

MKQi,y)=-i.

У

Следовательно, поскольку стратегия ц произвольна,

w=sup mf K(ji, y)= — 1.

f У

Рассуждая аналогично, получаем

«=inf sapK(x, v)=l.

V X

Так как v>v, то игра Г не имеет значения в смешанных стратегиях. Как будет показано в следующем параграфе, непрерывности функции выигрыша и компактности пространства стратегий до­ статочно для того, чтобы игра имела решение (значение и оп­

тимальные стратегии) в смешанном расширении.

76

§4. ИГРЫ С НЕПРЕРЫВНОЙ ФУНКЦИЕЙ ВЫИГРЫША

4.1.В данном параграфе рассмотрим антагонистические игры Г=(Х, Y,H)B предположении, что пространства стратегий XuY — метрические компакты (чаще всего они будут подмножествами евклидовых пространств), а функция Н непрерывна по обеим пере­

менным. Под множествами X, Y смешанных стратегий игроков 1 и 2 будем понимать множества вероятностных мер, заданных на о--алгебрах % и v борелевских множеств пространств X и Y соответ­ ственно. Тогда выигрыш K(ji, v) игрока 1 в ситуации (p., v)eXxY в смешанных стратегиях — измеримая функция относительно борелевской <г-алгебры xXv, OHa определяется интегралом (3.1) и пред­ ставляет собой математическое ожидание выигрыша по вероятност­ ной мере ц х v.

Игру Г=(Х, Y, Н), определенную указанным выше способом, будем называть непрерывной игрой.

42. Теорема. Если Г=(Х, Y, Н) — бесконечная антагонисти­ ческая игра, имеющая значение v и ситуацию равновесия (ц*, v*),

а функции К(р.*, у), К(х, v*) — непрерывны соответственно по у и по х, то справедливы равенства

K(ji*, y)=v,	yeY*.;	^ ^
К(х, v*)=«,	xeXf,	(4.2)

где Yy, Хц* — спектры смешанных стратегий v* и ц* соотве­ тственно.

Доказательство. Из теоремы п. 3.4 следует, что неравенство

К(ц*. y)>v

(4.3)

выполняется для всех точек yeY. Если (4.1) не выполнено, то существует такая точка y0eYy*, что К(р*, yQ)>v. В силу непрерыв­ ности функции К(р*, у) неравенство (4.3) в некоторой окрестности ю точки у0 — строгое. Из того, что у0 е У„. точка спектра смешан­ ной стратегии v*, следует v*(to)>0. Отсюда и из неравенства (4.3) получаем

v=KQi*, v*)=J К(ц*, y)dv*(y)>v.

Y

Противоречие доказывает справедливость (4.1). Равенство (4.2) до­ казывается аналогично.

Данный результат является аналогом теоремы о дополняющей нежесткости п. 7.6 гл. I. Напомним, что чистая стратегия х, входя­ щая в спектр оптимальной стратегии, называется существенной. Таким образом, теорема утверждает, что для существенных страте­ гий должны быть выполнены равенства (4.1), (4.2).

77

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

4.3. Лемма. Если функция Н:Хх Y-+R1 непрерывна на XxY, то интегралы К(р.,у) и К(х, v) являются соответственно непрерывными функциями от у и х для любых фиксированных смешанных страте­ гий реХи veY.

Доказательство. Функция Н(х, у) непрерывна на компакте XxY, поэтому она равномерно непрерывна.

Возьмем произвольное Е>0 и найдем такое 8>0, что как только

р2(Уи У2)<&, то для любого х выполняется неравенство
	\Н(х,У))-Н{х,у2)\<в,			(4.4)
где р2 () — метрика в пространстве Y.
Тогда		у2)Ы$Н(х,	yi)dp{x)-
\К{р, У1)-К(р,
		х
-jH(x,	y2№(x)\ = \$[H(x, уд~Н{х, у2)№(х)\*ь
X	X
<$\Н(х, У1)-Н(х,		y2)\dp{x)<zldn{x)=&.		(4.5)
X			X

Следовательно, функция К{р, у) непрерывна по у.

Аналогично доказывается непрерывность функции К{х, v) по х. 4.4. Сформулируем основную теорему данного параграфа.

Теорема. Бесконечная антагонистическая игра Г=(Х, Y, Н), где X, Y — метрические компакты, а Н — непрерывная функция на их

произведении, имеет решение в смешанных стратегиях	(значение
и оптимальные стратегии).
Доказательство теоремы основано на аналитических свойствах
смешанного расширения игры Г=(Х, Y, К) и некоторых вспомога­
тельных результатах.
4.5. Напомним, что последовательность борелевских мер/i„, п=\,2,...,	заданных
на борелевской (т-алгебре % компактного метрического пространства X, называется
слабо сходящейся, если
Km j <p (x)d^ (x)=J q> (х)ф (х)	(4.6)
для любой непрерывной функции q> (x), хеХ.	_

Лемма. В условиях теоремы п. 4.4 множества смешанных стратегий 7 и Y(MHOжества борелевских вероятностных мер) — метрические компакты в топологии слабой сходимости.

Приведем схему доказательства для множества смешанных стратегий 7 (для Т — рассуждения аналогичны).

Пространство борелевских мер It, заданных на борелевской £-алгебре х ко­ мпактного метрического пространства X, метризуемо, поскольку в X можно ввести метрику

78

pQi', ц")=тах(р', p"),

где р' и p" — нижние границы таких чисел г' а г" соответственно, что для любого замкнутого множества F<zX

lt(F)<lf(V,,(F))+i', /i"(F)<S(V, (F))+r",

где Vr(F)={xeX}: tninp1 (x, z)<r), r>0, a pt (•) — метрика в пространстве X.

zeF

Известно [85], что сходимость в этом метрическом пространстве равноснльна слабой СХОДИМОСТИ, а семейство мер ц на борелевской <т-алгебре пространства X слабо компактно (т. е. компактно в описанном выше метрическом пространстве всех борелевских мер) тогда и только тогда, когда это семейство равномерно ограничено

ц(.Х)<с	(4.7)
я равномерно плотно, т. е. для любого г>0 существует такой компакт А Я X, что
ц(Х\А)^в.	(4.8)
Условие (4.8) следует из компактности X, а (4.7) — из того, что меры	цеХ
нормированы (ji(X) = \).

4.6. Заметим, что в условиях теоремы п. 4.4 множество сметанных стратегий 7(7) игрока / (2) является компактом и в обычном смысле, поскольку в данном случае слабая сходимость последовательности мер {ц„}, п=1, 2, ..., равносильна сходимости в обычном смысле:

lim ц„(А)=ц(А)

л-*ао

для любого борелевского множества АяХ такого, что его граница А' имеет меру нуль: ft(Ar)=0.

Доказательство этого результата представляет определенные технические слож­ ности. Его можно найти, например, в [4, с. 367].

4.7. Обозначим через v л v соответственно нижнее и верхнее значения игры Г=(АГ, Y, К):

»=sup	inUKQi, у), ii=inf		supK(x, v).	(4.9)
д	у	v	х

Лемма. В условиях теоремы п. 4.4 экстремумы в (4.9) достига­ ются, поэтому

D=max minК(ц, у), i;=min maxK(x, v).		(4.10)
цеХ yeY	yeY хеХ

Доказательство. Так как Н{х, у) непрерывна, то по лемме п. 4.3 для любой меры /хе X функция

K(M,y) = jH(x,y)dfi(.x)

X

непрерывна по у. Так как Y — компакт, то К(ц, у) в некоторой его точке будет достигать минимума.

79