Петросян Л.А. и др. Теория игр

Подождите немного. Документ загружается.

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

ц„еХ,

что

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

Поскольку X

—

компакт в топологии слабой сходимости (лемма

п. 4.5), то из последовательности

{/^}^.

ц„еХ,

можно выбрать

слабо сходящуюся подпоследовательность. Пусть сама последова-

тельность

{n„}%L\

слабо сходится к некоторой мере

еХ.

Тогда

lim

KQi

у)

= ton j H(x,

y)dn

(х) = J #(х,

y)dfi

(х)=К(ц

, у), yeY.

я-юо в-»ооХ X

Но К(ц

, у) не меньше v для каждого yeY. Следовательно,

minK(p,

, ;)>« и на

еX

достигается требуемый максимум.

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

min max.

4.8.

Перейдем непосредственно к доказательству теоремы п. 4.4.

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

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

={х\,

..,,

х»,

Х„

с X,

={y\,

..., yi

Y„

a Y,

соответственно множеств Хя Y. Это означает, что для любых точек

хеХ я yeY найдутся такие точки х?е

Х„

и у\е

Y„,

что

(x,

xf)<-,

(y,yj)<-,

(4.11)

где p

(), р

(') — метрики пространств Хя Yсоответственно.

Для произвольного целого п построим матричную игру с мат-

рицей А„={а$, где

о?,=Я(х?, yj),

х?еХ

y)eY

(4.12)

Игра с матрицей

А„

имеет значение

0„

и оптимальные смешанные

стратегииp„

= (ifi,...,

я?„),

t„={x

...,

TJJ

игроков

я 2 соответственно

(см.

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

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

метрических компактов, поэтому она равномерно непрерывна, т. е.

для заданного е>0 можно найти такое 5>0, что как только

р^х,

)<5,

{у, /)<<5,

то

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

Выберем и_настолько большим, чтобы

1/п<8,

и определим

стратегию ц„

X по правилу

{F)=

£ "Г (

414

)

{•IxJeF,

х"еХ„}

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

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

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

\K(fi

,y)-K<ji

y])\<8.

Следовательно, для любого ye Y

(Y„—(1/и)-сеть

множества У)

К(ц

,у)>в„-Е. (4.16)

Так как min

K(jx„,

у) достигается (лемма п. 4.7), то

v>6„-e. (4.17)

Аналогично можно показать, что

И<в„ + Е. (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=\im9

, (4.20)

я-»оо

где

0„=v(A„)

—

значение матричной игры

матрицей

(4.12).

4.10. Из доказательства теоремы

п.

4.4 следует, что непрерывную

игру можно с любой степенью точности аппроксимировать конеч-

ными играми. Более того, справедлив следующий результат.

Теорема.

Бесконечная антагонистическая игра

Г=(Х, 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;=%vJ, . (4.22)

(-1

)-\

где К(р, v) — выигрыш в смешанных стратегиях

(ji,

v) в игре Г. Из

(4.16) и аналогичного неравенства для стратегии v„ получаем, что

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

К{х, v„)-e<e

<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].

Покажем, что в некоторых направлениях они не поддаются обобще-

нию.

Пример

10.

(Игра на

квадрате,

не

имеющая значения

смешанных

стратегиях [67]). Рассматривается антагонистическая игра Г ={Х,

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

{

—1,

если х<у<х+1/2,

0, если х=у или x=x+\j2,

если у<х или x+\j2<y.

Эта функция имеет разрывы на прямых у=х и у=х+

Покажем, что

sup inf ОД, v) =

1/3;

inf sup ОД, v)=3/7. (4.24)

/IV V Ц

Пусть ц — вероятностная мера на [0, 1]. Если ц ([0,

))^

/з>

то

положим

Уц=1.

Если же ц ([0,

))>

/з>

то

выберем 8>0, чтобы

V-

(№>

1г~^])

/з>

положим

Уц=

—

Ь-

В каждом из этих случаев

получаем неравенства

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

yj^l/l,

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

С другой стороны, если ц выбрано так, что ц ({0}) = ^ ({

})=^

({1}) =

то для всех уе[0,

имеем

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

Щ1,

у)]>1/3.

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

Теперь пусть

— какая-либо вероятностная мера на [0, 1]. Если

vflO,

1))>3/7, то положим х,=

Если v ([0, 1))<3/7, то v({l})>4/7,

и в этом случае положим х

=0, если v([0,

))<l/7; если же v([0,

1г))

1/7, то выберем <5>0 так, чтобы v([0,

—^])>

1/7, и положим

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).

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

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

существование решения в бесконечных антагонистических играх

с непрерывной функцией выигрыша и компактными множествами

стратегий. Вместе с тем представляет теоретический и практический

интерес выделение таких классов игр, когда один или оба игрока

имеют оптимальные чистые стратегии. Такие игры рассматривают-

ся в данном параграфе.

5.1.

Определение. Пусть XcR",

YCR"—

компакты,

множе-

ство Y—

выпукло,

функция H:Xx.Y-*R

непрерывна

по совокуп-

ности аргументов и выпукла по yeY при любом

фиксированном

значении

хеХ.

Тогда

игра Г(Х, Y, Н)

называется игрой

выпуклой

функцией выигрыша

(выпуклая игра).

Приведем симметричное определение относительно игрока 1.

Определение. Если

XcR™,

YcR"—

компакты,

множество

выпукло,

функция

выигрыша

непрерывна

по

совокупности

ар-

гументов

вогнута по

хеХпри

любом фиксированном

у е Y, то

игра

Г=(Х, Y, Н) называется игрой с вогнутой функцией выигрыша

(вогнутая игра).

Если же

XcR™,

YcR" — выпуклые компакты, а непрерывная по

совокупности аргументов функция выигрыша Н(х, у) вогнута по

х при любом фиксированном у и выпукла по у при каждом х, то

игра Г(Х, Y, Н) называется игрой с

вогнуто-выпуклой

функцией

выигрыша (вогнуто-выпуклая

игра).

Рассмотрим игры с выпуклой функцией выигрыша. Аналогич-

ные результаты справедливы и для вогнутых игр.

Теорема. Пусть Г=(Х, Y, Н) —

выпуклая

игра. Тогда игрок

имеет оптимальную чистую

стратегию,

при этом

значение

игры

равно

«==minmax#(jc, у). (5.1)

уеТ хеХ

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

метрике евклидовых пространств

R™

R"),

а функция Я непрерывна

на произведении Хх, Y, то согласно теореме п. 4.4 в игре Г существу-

ет значение v и оптимальные смешанные стратегии

/х*,

v*. Известно,

что множество вероятностных мер с конечным носителем всюду

плотно в множестве всех вероятностных мер на Y [85]. Поэтому

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

с конечным

спектром, слабо сходящаяся к v*. Пусть спектр стратегии

состоит

из точек у*, ..., yfy, и они выбираются с вероятностями п\, ..., г\\

Тогда в силу выпуклости функции Н имеем

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

где

y"=Yi

ljy

>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 с R

Y—выпуклое

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

строгое неравенство

<Р

(ЛУ1

+ 0 ~ %г) < *9 (У1> + 0 -1)9

(Уг); У\Уг

Y, y

Фу

Теорема.

Пусть

Т=(Х, Y,H) —

выпуклая игра

со

строго

выпук-

лой функцией

выигрыша.

Тогда игрок 2 имеет

единственную

оп-

тимальную

стратегию,

которая

является

чистой.

Доказательство. Пусть ц* —оптимальная стратегия игрока

U (p(y)=K(ji*, у) и v — значение игры. Если у — точка спектра

оптимальной стратегии игрока 2, то вьшолняется равенство

(п.4.2).

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

ср

(у)=min

ср

(у)=v.

yeY

Функция

<р(у)

является строго выпуклой, поскольку для Ле(0, 1)

имеет место неравенство

ср

{ку,

-Х)у

)=JЩх,

У1

)Ф*

(*)<

<XiH(x,y

)dfx*(x)

(l-X)^H(x,y

)dfi*(x) =

Аф(у

)

+ (1-А)ф(у

). (5.5)

Из (5.5) следует, что функция

ср(у)

не может достигать минимума

в двух различных точках. С другой стороны, существование точки

минимума У функции ср(у) гарантируется теоремой п. 5.1, что

завершает доказательство.

5.3.

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

теоремам по п. 5.1 и 5.2 для вогнутых и вогнуто-выпуклых игр.

Теорема.

Пусть

Г = (Х, Y, Н), X с

FT,

УсЛ" —

вогнутая

игра.

Тогда значение игры

вычисляется

по

формуле

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

* У

каждая чистая

стратегия

х*. на

которой достигается

max min

(5.6),

является оптимальной

для

игрока

Если,

кроме

того,

функция

Н(х, у)

строго вогнута

по х при

каждом фиксированном

yeY, то

оптимальная стратегия игрока

единственна.

Теорема. Пусть Г=(Х, Y, Н),

X<zFT,

Y a R" —

вогнуто-вы-

пуклая

игра.

Тогда значение игры

равно

v=mmmaxH(x, y)=max min#(;e, у). (5.7)

ух х у

игре

всегда существует ситуация равновесия

(х*, у*) в

чистых

стратегиях,

где х* е

у*

е Y

— чистые стратегии игроков

1 и 2, на

которых достигаются внешние экстремумы

(5.7).

Если

при

этом

функция

Н (х, у)

строго вогнута

(выпукла) по

переменной

х (у) при

любом фиксированном

yeY

(хеХ),

то

игрок 1

(2)

имеет

единствен-

ную

оптимальную

стратегию,

которая

является

чистой.

5.4. Выясним структуру оптимальной стратегии игрока 1 в вы-

пуклой игре

Г=(Х, Y, Н).

Теорема. В

выпуклой

игре Г=(Л

, Y, Н), Г с R" игрок 1 имеет

оптимальную смешанную стратегию

ц* с

конечным

спектром,

со-

стоящим

не

более

чем из (л +

1)-й точки множества

Доказательство этого результата основано на известной теореме Хелли о выпук-

лых множествах, которую мы приведем без доказательства [63, с. 210; 3, с.

107]*.

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

п + 1

выпуклого

множества в R , причем каждое множество из К компактно. Тогда, если каждые

п + 1

из множества семейства К имеют общую точку, то существует точка, общая

всем множествам семейства К.

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

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

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

пактных множеств X с R

, Y а

R".

Обозначим Х'=Хх

...

х X декар-

тово произведение г множества X.

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

</>:

X' х

X-^R

q>(x

..., х„ у)=тахН(х

у).

Лемма.

Функция

(р(х

,..., х

, у)

непрерывна

на X'xY.

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

множестве Хх Y, поэтому и равномерно непрерывна на нем. Тогда

для любого 8>0 найдется 5>0 такое, что из неравенств р

(Зс,

х)<5,

Рг(У1> Уг)<Ь следует неравенство \Н(х,

y^-Hfx,

)\<е,

где р

(),

()

— расстояния в

Л™

и Л" соответственно.

Имеем

\<р(х

1г

..., х„ yj-<p(x

..., х,

= |тах#(х„ у

J-max

Н(хь y

\H(x

j^)-#(*,,,

)},

где

H(x

)

= maxH(x

, у J, #(*,„ y^maxHixt, y

Если p

(3c,,

)<8 для i= 1,..., r,

)<b

и если Я(х„ у^>Н(х

1г

Уг),

то

0^H(x

)-H(x

)<#

)-Н{х^

)<е.

Аналогичные неравенства имеют место в случае H(x

у^^Н^х^,

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

значение игры

•Вопросы, связанные с обобщениями и приложениями теоремы Хелли, подробно

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

равно

v=min тахЯ(л, у)= max min max H(x

у), (5.8)

У * x

i у 1«|«л +

где ye F,

eX,

i'=l, ..., n+l.

Доказательство. Обозначим через

6= max min max H(x

, y).

*i *л+1 У Ki<« +

Так как min max H(x

, y)^mitx maxH(x, y)=v для каждой систе-

y 1<Кл+1 % ух

мы точек (x

..., x„

i)eX" , то

0<«.

(5.9)

Для произвольного фиксированного набора стратегий

eX,

i=l,

...,л+1,

рассмотрим систему неравенств относительно у

yHe,yeY,

i=l, ..., и+1. (5.10)

Покажем, что система (5.10) имеет решение.

Действительно,

0>min max H(x

y)= max H(Xi,y)^H(x

y),i=l,n+l.

у 1«<л-Н ЦКл+1

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

Следовательно, система (5.10) имеет решение для любых

xieX,

i'=l,2, ..., и+1.

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

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

Функция Н{х, у) выпукла и непрерывна по у, поэтому множество

выпукло и замкнуто при каждом х. Множества {D

} образуют

систему выпуклых компактных множеств в R", причем в силу того,

что неравенства (5.10) всегда имеют решение, любой набор по

(и+ 1)-му множеству системы {D

} имеет непустое пересечение. По-

этому по теореме Хелли существует точка у

е Y, общая для всех

множеств D„ т. е. такая, что

Н(х,у

)<0 (5.11)

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

имеем

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

)<S,

ух x

т. е. в<в. Полученное противоречие и доказывает (5.8).

Перейдем к доказательству теоремы.

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

v= max min max

Н{х„у)=тахп.

max H(x

y)=

ж,, ..., дг

п+

1 у 1<;<я

1^/<п+1

я+1

=min max £ #(х,> j)

» (5-12)

У Р '=1

где Зс

..., Зс

л+

, —векторы, на которых достигается внешний мак-

симум в (5.8),

Я+1

р =

(п

..., я

л+

1)еЛ

л+1

, я.^О, J] я,=

(5.13)

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

К(р,

y)=t Ж**

У)Щ,

У*

Y, реР,

где Р — состоит из векторов, удовлетворяющих (5.13). Функция

К(р,

у) непрерывна иорау, выпукла по у и вогнута

по

р, а множест-

ва Y с

FC,

Р С R" — компакты в соответствующих евклидовых

пространствах. Поэтому по теореме п. 5.3 и из (5.12) имеем

я+1 л+1

«=min max £ H(x

д/)я,=тах min £ H (х

у)щ.

(5.14)

у p i-l p у i-l

Из (5.8) и (5.14) следует существование таких

р*еР

и у* в Y, что

для всех хеХ и уе

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

я + 1

;-|

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

Сформулируем теорему о структуре оптимальной стратегии иг-

рока 2 в вогнутой игре Г = (Х, Y, Н).

Теорема. В

вогнутой

игре Т

{Х,

Y, Н), X a R

игрок 2 имеет

оптимальную смешанную стратегию

v* с

конечным

спектром,

со-

стоящим

не

более

чем из (т+1)-й

точки множества

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

щей теоремы.

5.5.

Суммируем результаты теорем для выпуклых игр, доказан-

ные в этом параграфе.