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

По определению « для любого и существует такая мера

ц„еХ, что

minK(p.„,y)^v-lln.

У

Поскольку X — компакт в топологии слабой сходимости (лемма п. 4.5), то из последовательности {/^}^.ь ц„еХ, можно выбрать слабо сходящуюся подпоследовательность. Пусть сама последова­ тельность {n„}%L\ слабо сходится к некоторой мере ц0еХ. Тогда

lim KQim у) = ton j H(x, y)dnn (х) = J #(х, y)dfi0 (х)=К(ц0, у), yeY.

я-юо	в-»ооХ	X
Но К(ц0,	у) не меньше v для	каждого yeY. Следовательно,

minK(p,0, ;)>« и на ц0еX достигается требуемый максимум.

Аналогично доказывается, что inf sup в (4.9) можно заменить на min max.

4.8. Перейдем непосредственно к доказательству теоремы п. 4.4. Доказательство. Так как X я Y — метрические компакты, то

для любого целого и существуют конечные (1/л)-сети

Хя={х\, ..,, х»,п}, Х„ с X, Yn={y\, ..., yin), Y„ a Y,

соответственно множеств Хя Y. Это означает, что для любых точек хеХ я yeY найдутся такие точки х?е Х„ и у\е Y„, что

Pl(x, xf)<-, p2(y,yj)<-,	п	(4.11)
п
где pt(), р2(') — метрики пространств Хя	Yсоответственно.
Для произвольного целого п построим матричную игру с мат­
рицей А„={а$, где
о?,=Я(х?, yj), х?еХп, y)eYn.		(4.12)

Игра с матрицей А„ имеет значение 0„ и оптимальные смешанные стратегииp„ = (ifi,..., я?„), t„={xnb ..., TJJ игроков 1 я 2 соответственно

(см. теорему п. 6.1 гл. I).

Функция Н(х, у) непрерывна на декартовом произведении Хх Y метрических компактов, поэтому она равномерно непрерывна, т. е. для заданного е>0 можно найти такое 5>0, что как только

р^х, Xе)<5, р2{у, /)<<5,

то

80

\Н(х,у)-Н(,х',У)\<8. (4.13)

Выберем и_настолько большим, чтобы 1/п<8, и определим стратегию ц„ е X по правилу

lxn{F)=

£

"Г

(414)

{•IxJeF, х"еХ„}

для каждого борелевского множества F пространства X. Имеем

Если PzC^' )?)<^ то согласно (4.4), (4.5) и (4.13) получаем

\H{x,y)-H{x,yl)\<s,

\K(fin,y)-K<jimy])\<8.

Следовательно, для любого ye Y (Y„—(1/и)-сеть множества У)

К(ця,у)>в„-Е.	(4.16)
Так как min K(jx„, у) достигается (лемма п. 4.7), то
У	(4.17)
v>6„-e.
Аналогично можно показать, что
И<в„ + Е.	(4.18)
Из (4.17) и (4.18) получаем
v > v — 2е.
Но по лемме п. 2.2 гл. I неравенство v^v вьшолняется	всегда.
Учитывая произвольность е>0, получаем"
« = «;	(4.19)

тогда из леммы п. 4.7 и (4.19) следует утверждение теоремы (см. п. 2.1).

4.9. Следствие. Имеет место равенство
v=\im9n,	(4.20)

я-»оо

где 0„=v(A„) — значение матричной игры с матрицей (4.12).

4.10. Из доказательства теоремы п. 4.4 следует, что непрерывную игру можно с любой степенью точности аппроксимировать конеч­ ными играми. Более того, справедлив следующий результат.

81

Теорема. Бесконечная антагонистическая игра Г=(Х, Y, Н), где X, Y — метрические компакты, а Н — непрерывная функция на их произведении, при любом Е>0 имеет ^.-оптимальные смешанные стратегии с конечным спектром.

Доказательство теоремы следует из доказательства (п. 4.8) теоремы п. 4.4. Действительно, по игре Г построим матричные игры с матрицами А„ и смешанные стратегии ц„еХ, определяемые соот­ ветственно (4.12), (4.14) для произвольного целого и. Стратегии v„e У игрока 2 по аналогии определяются следующим образом:

v.(G)=		I	т?,		(4.21)
		{J^eG.^e Y„)
где f"=(Ti, ..., т^ — оптимальная			смешанная	стратегия	игрока
2 в игре с матрицей А„ и значением в„.
По построению имеем
D,= n	« t	; =	% v J ,	.	(4.22)
(-1	) -	\

где К(р, v) — выигрыш в смешанных стратегиях (ji, v) в игре Г. Из (4.16) и аналогичного неравенства для стратегии v„ получаем, что

для произвольного £>0 найдется номер п такой, что

К{х, v„)-e<en<K(ji„, У)+Е

(4.23)

для всех хеХ и yeY. Учитывая, что стратегии ц, и v, имеют конечный спектр ХЙ и Y„ соответственно (Х„ и Г, — конечные (1/и)-

сети соответственно множеств X и Y), получаем утверждение те­ оремы (см. п. 3.4).

4.11.Объединяя результаты теорем п. 4.4 и 4.10, можно сделать вывод, что бесконечная антагонистическая игра с непрерывной фун­ кцией выигрыша и компактными множествами стратегий для любо­ го Ё > 0 имеет е-оптимальные стратегии игроков, являющиеся смеся­ ми конечного числа чистых, а также смешанные оптимальные стра­ тегии в классе борелевских вероятностных мер. В частности, эти результаты справедливы для игр на квадрате (п. 1.3) с непрерывной функцией выигрыша.

4.12.Имеется большое число работ, в которых доказывается существование значения бесконечных антагонистических игр. На­ иболее общий результат в этом направлении принадлежит Сайону

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

82

Пример 10. (Игра на квадрате, не имеющая значения в смешанных стратегиях [67]). Рассматривается антагонистическая игра Г ={Х,

Y, Н), где Х= У=[0, 1], а функция выигрыша Н имеет вид

{	—1, если х<у<х+1/2,
	0, если х=у	или	x=x+\j2,
	1, если у<х	или	x+\j2<y.
Эта функция имеет разрывы на		прямых	у=х и	у=х+1/2.
Покажем, что
sup inf ОД, v) = 1/3; inf sup ОД, v)=3/7.				(4.24)
/ I V	V	Ц

Пусть ц — вероятностная мера на [0, 1]. Если ц ([0, 1/2))^1/з> т о положим Уц=1. Если же ц ([0, 1/2))>1/з> т о выберем 8>0, чтобы

V- (№>11г~^])>1/з> и положим Уц=112 — Ь- В каждом из этих случаев получаем неравенства

inf К(ц, v)^K(v,

yj^l/l,

V

которые доказываются непосредственной проверкой.

С другой стороны, если ц выбрано так, что ц ({0}) = ^ ({1/2})=^ ({1}) = 1/3, то для всех уе[0, 1] имеем

J H(x, у№(х)=1/3[Я(0, у)+Н(\/2, у) + Щ1, у)]>1/3.

о

Следовательно, доказано первое из равенств (4.24).

Теперь пусть v — какая-либо вероятностная мера на [0, 1]. Если vflO, 1))>3/7, то положим х,= 1. Если v ([0, 1))<3/7, то v({l})>4/7,

и в этом случае положим ху=0, если v([0, 1/2))<l/7; если же v([0,

11г))> 1/7, то выберем <5>0 так, чтобы v([0,1/2 —^])> 1/7, и положим xv= 1/2—(5. В каждом из указанных случаев убеждаемся, что

sup ОД, У):>ОДУ, V)>3/7.

м

С другой стороны, если v выбрано так, что

v({l/4}) = l/7, v({l/2}) = 2/7, v({l})=4/7, то для любого хе[0, 1] имеем

]н(х,у)а\(у)=1р[Н{х, 1/4)+2Я(х, 1/2)+4Я(х, 1)]<3/7.

о

Таким образом, доказано второе из равенств (4.24).

83

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

В§ 4 при достаточно общих предположениях было доказано существование решения в бесконечных антагонистических играх

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

5.1. Определение. Пусть XcR",	YCR"— компакты, множе­
ство Y— выпукло, функция H:Xx.Y-*Rl		непрерывна по совокуп­
ности аргументов и выпукла по yeY	при любом фиксированном
значении хеХ. Тогда игра Г(Х, Y, Н) называется игрой с выпуклой
функцией выигрыша (выпуклая игра).
Приведем симметричное определение относительно игрока 1.
Определение. Если XcR™, YcR"—		компакты, множество

X выпукло, функция выигрыша Н непрерывна по совокупности ар­ гументов и вогнута по хеХпри любом фиксированном у е Y, то игра Г=(Х, Y, Н) называется игрой с вогнутой функцией выигрыша (вогнутая игра).

Если же XcR™, YcR" — выпуклые компакты, а непрерывная по совокупности аргументов функция выигрыша Н(х, у) вогнута по х при любом фиксированном у и выпукла по у при каждом х, то игра Г(Х, Y, Н) называется игрой с вогнуто-выпуклой функцией выигрыша (вогнуто-выпуклая игра).

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

Теорема. Пусть Г=(Х, Y, Н) — выпуклая игра. Тогда игрок

2 имеет оптимальную чистую стратегию, при этом значение игры равно

«==minmax#(jc, у).	(5.1)
уеТ хеХ

Доказательство. Так как X и Y— метрические компакты (в

метрике евклидовых пространств R™ и R"), а функция Я непрерывна на произведении Хх, Y, то согласно теореме п. 4.4 в игре Г существу­ ет значение v и оптимальные смешанные стратегии /х*, v*. Известно, что множество вероятностных мер с конечным носителем всюду плотно в множестве всех вероятностных мер на Y [85]. Поэтому

существует последовательность смешанных стратегий v" с конечным

спектром, слабо сходящаяся к v*. Пусть спектр стратегии v" состоит из точек у*, ..., yfy, и они выбираются с вероятностями п\, ..., г\\п. Тогда в силу выпуклости функции Н имеем

84

K(x, v")= § п1Н{х, ?„)>Н(х, у"),

(5.2)

где y"=Yirljyl>i- Переходя к пределу при л-юо в неравенстве (5.2)

j-i

(если необходимо, то следует рассмотреть подпоследовательность

{у"}), получаем
К(х, v*)^H(x, у), хеХ,	(5.3)

где у — предельная точка последовательности {у"}. Из (5.3) и лем­ мы п. 4.2 имеем

	та\К(х,	v*)^maxH(x,	у).	(5.4)
	X	X
Пусть неравенство (5.4) строгое. Тогда
v=maxK(x,	v*)>ma&H(x, y)^min		ma.xK(x, v)=«,
X	X	V	X

что невозможно. Таким образом, max#(x, y)=maxK(x, v*)=v и из

_ X X

теоремы п. 3.5 получаем, что у — оптимальная стратегия игрока 2. Установим справедливость равенства (5.1). Так как "yeY— оп­

тимальная стратегия игрока 2, то
v=maxH(x, y)^min		max#(x, у).
	х	у х
С другой стороны, вьшолняется неравенство
«=min тахК(х, v)<min maxH(x, у).
v	х	у х

Сравнивая последние неравенства, получаем (5.1).

5.2. Напомним, что функция (р: У-»ЛХ, Y с Rn, Y—выпуклое

множество, строго выпукла, если для всех Ле(0, 1) вьшолняется строгое неравенство

<Р (ЛУ1 + 0 ~ %г) < *9 (У1> + 0 -1)9 (Уг); У\Уге Y, yt Фуг.

Теорема. Пусть Т=(Х, Y,H) — выпуклая игра со строго выпук­ лой функцией выигрыша. Тогда игрок 2 имеет единственную оп­ тимальную стратегию, которая является чистой.

Доказательство. Пусть ц* —оптимальная стратегия игрока U (p(y)=K(ji*, у) и v — значение игры. Если у — точка спектра оптимальной стратегии игрока 2, то вьшолняется равенство (п.4.2).

85

Однако для всех yeY имеем неравенство K(ji*, y)^v, поэтому

ср (у)=min ср (у)=v.

yeY

Функция <р(у) является строго выпуклой, поскольку для Ле(0, 1) имеет место неравенство

ср {ку, + (1 -Х)уг)=JЩх, ЛУ1 + (1 - % 2 ) Ф * (*)<

X
<XiH(x,yl)dfx*(x) + (l-X)^H(x,y2)dfi*(x)	=
= Аф(у1) + (1-А)ф(у2).	(5.5)

Из (5.5) следует, что функция ср(у) не может достигать минимума в двух различных точках. С другой стороны, существование точки минимума У функции ср(у) гарантируется теоремой п. 5.1, что завершает доказательство.

5.3. Приведем без доказательства результаты, симметричные теоремам по п. 5.1 и 5.2 для вогнутых и вогнуто-выпуклых игр.

Теорема. Пусть Г = (Х, Y, Н), X с FT, УсЛ" — вогнутая игра. Тогда значение игры v вычисляется по формуле

w=max min#(.x, у),

(5.6)

*У

каждая чистая стратегия х*. на которой достигается max min (5.6), является оптимальной для игрока 1. Если, кроме того, функция Н(х, у) строго вогнута по х при каждом фиксированном yeY, то оптимальная стратегия игрока 1 единственна.

Теорема. Пусть Г=(Х,	Y, Н), X<zFT, Y a R" — вогнуто-вы­
пуклая игра. Тогда значение игры v равно
v=mmmaxH(x,	y)=max	min#(;e, у).	(5.7)
у х	х	у

В игре Г всегда существует ситуация равновесия (х*, у*) в чистых стратегиях, где х* е X, у* е Y — чистые стратегии игроков 1 и 2, на которых достигаются внешние экстремумы в (5.7). Если при этом функция Н (х, у) строго вогнута (выпукла) по переменной х (у) при любом фиксированном yeY (хеХ), то игрок 1 (2) имеет единствен­ ную оптимальную стратегию, которая является чистой.

5.4. Выясним структуру оптимальной стратегии игрока 1 в вы­ пуклой игре Г=(Х, Y, Н).

Теорема. В выпуклой игре Г=(ЛГ, Y, Н), Г с R" игрок 1 имеет

86

оптимальную смешанную стратегию ц* с конечным спектром, со­ стоящим не более чем из (л + 1)-й точки множества X.

Доказательство этого результата основано на известной теореме Хелли о выпук­ лых множествах, которую мы приведем без доказательства [63, с. 210; 3, с. 107]*.

Теорема (теорема Хелли). Пусть К— семейство из не менее чем п + 1 выпуклого

множества в R , причем каждое множество из К компактно. Тогда, если каждые п + 1 из множества семейства К имеют общую точку, то существует точка, общая всем множествам семейства К.

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

Пусть функция Н(х, у) непрерывна на произведении Хх Y ком­

пактных множеств X с Rm, Y а R". Обозначим Х'=Хх	... х X декар­
тово произведение г множества X.
Рассмотрим функцию </>: X' х X-^R1:
q>(xv ..., х„ у)=тахН(хи у).
Лемма. Функция (р(хх,..., хг, у) непрерывна на	X'xY.

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

для любого 8>0 найдется 5>0 такое, что из неравенств рх (Зс, х)<5,
Рг(У1> Уг)<Ь следует неравенство \Н(х, y^-Hfx, у2)\<е,				где рх(),
р2() — расстояния в Л™ и Л" соответственно.
Имеем
\<р(х1г ...,	х„ yj-<p(xlt	..., х, у2)\ =
= |тах#(х„ уJ-max	Н(хь y2)\ = \H(xh, j^)-#(*,,, у2)},
где
H(xh, yl) = maxH(xi, уJ, #(*,„ y^maxHixt,			y2).
Если px (3c,, xt)<8 для i= 1,..., r, p2{yv		y2)<b и если Я(х„		у^>Н(х1г,
Уг), то
0^H(xti, yx)-H(xi2,	j>2)<# (xfl, ух)-Н{х^		у2)<е.

Аналогичные неравенства имеют место в случае H(xit, у^^Н^х^, у2).

Лемма. В выпуклой игре Y=(X, Y, H), Y с R" значение игры

•Вопросы, связанные с обобщениями и приложениями теоремы Хелли, подробно изложены в книге: Данцер Л., Грюнбаум Б., Кли В. Теорема Хелли. М., 1968.

87

v равно
v=min тахЯ(л, у)=						max min			max H(xh у),	(5.8)
	У	*				xt	Jtn+i	у	1«|«л + 1
где ye F, xteX,		i'=l,	...,	n+l.
Доказательство. Обозначим через
		6=	max			min	max H(xt, y).
			*i	*л+1		У	K i < « + I
Так как min	max H(xt, y)^mitx						maxH(x,		y)=v для каждой систе-
y	1<Кл+1			%		у	х
мы точек (xl5 ..., x„+i)eX"					, то
						0<«.				(5.9)
Для произвольного				фиксированного					набора стратегий xteX,
i=l, ...,л+1, рассмотрим систему неравенств относительно у
		Н (xhyHe,yeY,					i=l,	..., и+1.		(5.10)
Покажем, что система (5.10) имеет решение.
Действительно,
0>min	max H(xhy)=				max			H(Xi,y)^H(xhy),i=l,n+l.
у	1«<л-Н				ЦКл+1

Таким образом, у удовлетворяет системе (5.10).

Следовательно, система (5.10) имеет решение для любых xieX, i'=l,2, ..., и+1.

Зафиксируем х и рассмотрим множество

Dx={y:H(x,y)<6}.

Функция Н{х, у) выпукла и непрерывна по у, поэтому множество Dx выпукло и замкнуто при каждом х. Множества {Dx} образуют

систему выпуклых компактных множеств в R", причем в силу того, что неравенства (5.10) всегда имеют решение, любой набор по (и+ 1)-му множеству системы {Dx} имеет непустое пересечение. По­ этому по теореме Хелли существует точка у0 е Y, общая для всех множеств D„ т. е. такая, что

Н(х,уо)<0

(5.11)

при любых хеХ. Предположим, что вфк. Тогда из (5.9) и (5.11)

88

имеем

0<«=min max#(jc, y)^maxH(x, j0 )<S,

ух x

т.е. в<в. Полученное противоречие и доказывает (5.8). Перейдем к доказательству теоремы. Доказательство. Из предыдущей леммы имеем

v= max	min	max Н{х„у)=тахп. max H(xb		y)=
ж,, ..., дгп+1	у	1<;<я + 1	у 1^/<п+1
		я+1
	=min max £		#(х,> j)71»	(5-12)

УР '=1

где Зс15 ..., Зсл+, —векторы, на которых достигается внешний мак­ симум в (5.8),

Я+1
р = (пи ..., ял+1)еЛл+1, я.^О, J] я,= 1.	(5.13)

Рассмотрим функцию

К(р, y)=t Ж** У)Щ, У* Y, реР,

где Р — состоит из векторов, удовлетворяющих (5.13). Функция К(р, у) непрерывна иорау, выпукла по у и вогнута по р, а множест­ ва Y с FC, Р С R" — компакты в соответствующих евклидовых пространствах. Поэтому по теореме п. 5.3 и из (5.12) имеем

	я+1		л+1
«=min max £		H(xh д/)я,=тах min £ H (хь		у)щ.	(5.14)
у	p i - l	p	у i - l
Из (5.8) и (5.14) следует существование таких р*еР				и у* в Y, что

для всех хеХ и уе У выполняется неравенство

я+ 1

;-|

Теорема доказана.

Сформулируем теорему о структуре оптимальной стратегии иг­ рока 2 в вогнутой игре Г = (Х, Y, Н).

Теорема. В вогнутой игре Т = {Х, Y, Н), X a Rm игрок 2 имеет оптимальную смешанную стратегию v* с конечным спектром, со­ стоящим не более чем из (т+1)-й точки множества Y.

Доказательство теоремы аналогично доказательству предыду­ щей теоремы.

5.5. Суммируем результаты теорем для выпуклых игр, доказан­ ные в этом параграфе.

89