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

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

ют вероятностные меры. Тогда возможных вероятностных мер существенно больше

(и,

как правило, гарантируется существование ситуации равновесия в смешанных

стратегиях). Однако в этом случае не всякая функция Н на Хх Y окажется измери-

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

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

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

желательно, чтобы смешанные стратегии имели наиболее простой вид и в то же

время в этом расширении существовало, по крайней мере, значение игры.

Строго говоря, интеграл в (3.1) должен браться по мере

/JXV

на декартовом

произведении Хх

Однако согласно правилам антагонистической игры смешанные

стратегии (меры) fiiv игроками выбираются одновременно и независимо друг от

друга, т. е. вероятностные меры

ц.

— стохастически независимы.

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

Ситуацией

(ц, v) в

смешанных стратегиях

назы-

вается пара вероятностных мер

fieX.veT,

которые стохастически

независимы.

Таким образом, в ситуации (ц, v) в смешанных стратегиях выиг-

рыш К(ц, v) равен повторному интегралу (3.1). Одноточечные

множества принадлежат (Т-алгебре подмножеств множества страте-

гий, на которой определяются вероятностные меры, поэтому каж-

дой чистой стратегии х(у) можно поставить в соответствие вероят-

ностную меру

eX(v

eY),

сосредоточенную в точке хеХ (yeY).

Отождествляя стратегии х и ц

, у и v,, видим, что чистые стратегии

являются частным случаем смешанных, т. е. справедливы включе-

ния

X<zX,

Тогда выигрыши игрока 1 в ситуациях (х, \) и (ц,

у) равны соответственно математическим ожиданиям:

K(x,v)=K(n

v) =

H(x,y)dv(y);

(3.2)

К(ц,

у) =К(ц, v,) = H(x, y)d

i(x), (3.3)

где интегралы в (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*) —

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

смешанном расширении

игры

Г, a fi*(v*) —

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

1 (2) в Г.

Аналогично, ситуация (//*, v'

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

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

игроков 1 и 2 соответственно. Тогда из (3.1), (3.2) и (3.6) получаем

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

Отсюда вытекают неравенства (3.4), что и требовалось доказать.

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

равновесия (е-равновесия) в чистых стратегиях в игре Г, то она

является и ситуацией равновесия (е-равновесия) в смешанном рас-

ширении Г, при этом значение игры v сохраняется.

Заметим, что смешанное расширение Г является антагонистичес-

кой игрой, поэтому относительно Г справедливо понятие вполне

определенной игры (п. 2.1), а также теорема п. 2.5, только речь

теперь идет о ситуации равновесия и значении игры в смешанных

стратегиях.

3.5.

Теорема. Для

того чтобы игра

Г= (X, Y, Н)

имела значение

v в

смешанных

стратегиях,

т. е. sup inf K(ji, v)=inf supK(ji, v)=«,

необходимо

достаточно выполнение равенства

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

У УХ

Если при этом

игроки имеют оптимальные

стратегии,

то

внешние

экстремумы

в (3.8)

достигаются и равенства

MK(n*,y)=v, (3.9)

sopK(x,v*)=v (3.10)

являются

необходимыми

достаточными

условиями

оптимально-

сти

смешанных стратегий

ц*

е X и

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

К(ц.

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

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

inf K((i,

^ 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) следует, что значение

игры не зависит от способа рандомизации. Так, для доказательст-

ва его существования достаточно найти хотя бы одно смешанное

расширение игры, для которого выполнялось бы равенство (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) достигаются, т. е.

=max inf Н(х, у) =inf H(x°, у); (3.15)

х у у

=min sup Н(х, у) = sup H(x, y°) (3.16)

ух х

и пусть a=v

—v~.

Тогда максиминная стратегия х° игрока 1 и ми-

нимаксная стратегия у° игрока 2 с точностью до а описывают

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

приближенного решения игры Г. Таким образом, в этом случае

задача сводится к нахождению максиминных и минимаксных стра-

тегий игроков 1 и 2 соответственно, а точность приближенного

решения определяется величиной a=v

—v~, при этом значение

игры v согласно (3.14) лежит в интервале ve[v~, v

]. Способам

нахождения решения задач (3.15), (3.16) посвящена теория минимак-

са

[31,

30].

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

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

спектра смешанной

стратегии.

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

Пусть

Г= (X, Y, Н) —

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

игра.

Тогда чистую

стратегию

еХ (y

eY) игрока 1 (2) называют

точкой концентрации его смешанной стратегии

ц (х),

если

р.

(х

) >0

(У(УО)>0).

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

Чистая стратегия

еХ

eY),

где X (соот-

ветственно

Y) —

топологическое

пространство,

называется

точ-

кой

спектра смешанной стратегии

ц (v),

заданной

на

борелевской

о-алгебре

подмножеств множества

X (Y), если для

любой

измери-

мой

окрестности ш точки

(у

)

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

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

т а

Спектром

смешанной стратегии

ц (v) назовем

наименьшее

за-

мкнутое

множество,

ц-мера (v-мера)

которого равна

единице.

Точки концентрации смешанной стратегии являются точками

спектра; обратное, вообще говоря, неверно. Так, чистые стратегии,

в которых смешанная стратегия имеет положительную плотность,

являются точками спектра, но они не являются точками концент-

рации.

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

чать

Хр

(Г,).

Докажем аналог теоремы п. 7.6 гл. I о дополняющей нежест-

кости для бесконечных игр.

Теорема.

Пусть

Г=(Х, Y, Н) —

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

игра,

име-

ющая

значение

Тогда,

если

еХ,

—

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

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

2 и

K(x

,v*)<v, (3.17)

то х

не может

быть точкой концентрации какой-либо

оптималь-

ной стратегии игрока

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

оптимальных стратегий игрока 2.

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

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

К(х, V*)<D.

Интегрируя его по оптимальной смешанной стратегии (мере) /х*

игрока / на множестве

Х\{х

получаем

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

Пусть /I*(JC

)>0, т. е. JC

—точка концентрации оптимальной сме-

шанной стратегии

/х*

игрока 1. Тогда из (3.17) имеем

К(х

v*)n*

)<vn* (х

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

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

Поэтому /i*(x

)=0 для всех оптимальных стратегий

ц*еХ.

3.8.

Для бесконечных антагонистических игр можно ввести по-

нятие доминирования стратегий аналогично тому, как это делалось

8 гл. I. _

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

Стратегия

ц±еХ

игрока

1 строго доминирует

стратегию

e X

(JJ.^

если

H(jii,y)>H(ji

,y)

для всех yeY. Аналогично, стратегия v^Y игрока 2 строго до-

минирует стратегию

eY (v

), если

Н(х, У

)<Я(Х, v

)

для всех хеХ.

Стратегии

и v

2 называются строго доминиру-

емыми,

если существуют

Цу>ц

и Vj>v

Если последние неравенства выполняются как нестрогие, то

говорят, что ц

доминирует ц

(ju

^=/i

) и v

доминирует v

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

п. 8.3.

Теорема. Для бесконечной антагонистической игры, имеющей решение, ни одна

строго доминируемая чистая стратегия игрока не содержится в спектрах его оп-

тимальных смешанных стратегий.

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

решение (X и Y

—

топологические пространства), и каждый элемент открытого

множества Х° с X доминируется некоторой стратегией

ц°,

спектр которой не пересе-

кается с Х°. Тогда всякое решение игры Г'=(Х\Х°, Y, Н) является решением игры Г.

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

3.9. В этом параграфе рассмотрены свойства оптимальных (е-

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

ния решения

игры.

Матричная игра вполне определена в смешанных

стратегиях, т. е. всегда существуют значение и ситуация равновесия,

что следует из теоремы п. 6.1 гл. I. Возможности решения бесконеч-

ных антагонистических игр в смешанных стратегиях ограничены,

что показывает следующий пример.

Пример 9. (Игра, не

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

смешанных

стратеги-

ях.) Рассмотрим игру Г = (Х, Y, Н), где Х= У=

{1,

2...} — множество

натуральных чисел, а функция выигрышей имеет вид

если х>у,

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

—1,

если х<у.

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

не имеет значения и в смешанных стратегиях.

Пусть fi — произвольная смешанная стратегия игрока 7,j

и dfi(x) = 8

, где 8

^0 и £ 8

=1. Возьмем е>0 и найдем

у,

такое, что *"'

X 8

>1-в.

Тогда

K(n,yd=t &*Н{х,уд= Е 8

H(x,yJ +

х-1

х^у,

+ £ 8

Щх,у,)=- £ 8

+ X 8

<-1 + 2е.

х>у, х<уь х>у,

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

ний, меньших

—

имеем

MKQi,y)=-i.

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

w=sup mf K(ji, y)=

—

f У

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

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

V X

Так как v>v, то игра Г не имеет значения в смешанных стратегиях.

Как будет показано в следующем параграфе, непрерывности

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

статочно для того, чтобы игра имела решение (значение и оп-

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

ИГРЫ

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

4.1.

данном параграфе рассмотрим антагонистические игры

Г=(Х,

Y,H)B

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

XuY

—

метрические компакты (чаще всего

они

будут подмножествами

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

функция

непрерывна

по

обеим пере-

менным.

Под

множествами

X, Y

смешанных стратегий игроков

и 2

будем понимать множества вероятностных мер, заданных

на

о--алгебрах

и v

борелевских множеств пространств

соответ-

ственно. Тогда выигрыш

K(ji, v)

игрока

1 в

ситуации

(p.,

v)eXxY

в смешанных стратегиях — измеримая функция относительно боре-

левской <г-алгебры

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) не

выполнено,

то

существует такая точка

что

К(р*,

)>v.

силу непрерыв-

ности функции К(р*,

у)

неравенство (4.3)

некоторой окрестности

ю точки

— строгое.

Из

того,

что у

У„.

точка спектра смешан-

ной стратегии

v*,

следует v*(to)>0. Отсюда

и из

неравенства

(4.3)

получаем

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

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

до-

казывается аналогично.

Данный результат является аналогом теоремы

дополняющей

нежесткости

п. 7.6 гл. I.

Напомним,

что

чистая стратегия

х,

входя-

щая

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

Таким образом, теорема утверждает, что для существенных страте-

гий должны быть выполнены равенства (4.1), (4.2).

Теорема п. 4.2 справедлива для любой непрерывной игры, по-

скольку справедливо следующее утверждение.

4.3.

Лемма. Если

функция

Н:Хх Y-+R

непрерывна

на XxY, то

интегралы К(р.,у)

и К(х,

являются

соответственно непрерывными

функциями

от у и х для любых

фиксированных смешанных

страте-

гий реХи veY.

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

XxY, поэтому она равномерно непрерывна.

Возьмем произвольное

Е>0

и найдем такое 8>0, что как только

(Уи

)<&,

то для любого х выполняется неравенство

\Н(х,

У)

)-Н{х,у

)\<в, (4.4)

где р

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

Тогда

\К{р,

У1

)-К(р, у

)Ы$Н(х,

)dp{x)-

-jH(x,

№(x)\

\$[H(x,

уд~Н{х, у

)№(х)\*ь

<$\Н(х,

У1

)-Н(х, y

)\dp{x)<zldn{x)=&. (4.5)

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

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

4.4.

Сформулируем основную теорему данного параграфа.

Теорема.

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

Г=(Х, Y, Н), где

X, Y

— метрические

компакты,

а Н

— непрерывная

функция на их

произведении,

имеет решение в смешанных стратегиях (значение

оптимальные

стратегии).

Доказательство теоремы основано на аналитических свойствах

смешанного расширения игры Г=(Х, Y, К) и некоторых вспомога-

тельных результатах.

4.5.

Напомним, что последовательность борелевских

мер/i„,

п=\,2,..., заданных

на борелевской (т-алгебре

компактного метрического пространства X, называется

слабо сходящейся, если

Km j <p (x)d^ (x)=J q> (х)ф (х) (4.6)

для любой непрерывной функции

(x), хеХ. _

Лемма. В условиях теоремы п. 4.4 множества смешанных

стратегий

7и

Y(MHO-

жества борелевских вероятностных мер)

—

метрические компакты в топологии

слабой сходимости.

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

Т — рассуждения аналогичны).

Пространство борелевских мер It, заданных на борелевской £-алгебре х ко-

мпактного метрического пространства X, метризуемо, поскольку в X можно ввести

метрику

pQi',

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

где р' и

— нижние границы таких чисел г' а г" соответственно, что для любого

замкнутого множества

F<zX

lt(F)<lf(V,,(F))+i',

/i"(F)<S(V,

(F))+r",

где V

(F)={xeX}: tninp

(x,

z)<r), r>0, a p

(•)

— метрика в пространстве 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(A

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

непрерывна по у. Так как Y

—

компакт, то К(ц, у) в некоторой его

точке будет достигать минимума.