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

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

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

Л"

—

выпуклая

игра.

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

игры

определяется

по

формуле

w=min тах#(л:, у).

Игрок 1

обладает оптимальной смешанной стратегией

/х

с конеч-

ным

спектром,

состоящим не более

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

точки

множест-

ва X. В

то

же

время

все

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

на которых

достига-

ется

min max H{x, у), являются

оптимальными

для

игрока

Если,

кроме того, функция Н(х, у) при каждом

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

хеХ

строго

выпукла по у, то

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

единст-

венна-

Проиллюстрируем эти результаты на примере.

Пример 11. Рассмотрим частный случай примера 1 (см. п. 1.2).

Пусть

и множество S представляет собой замкнутый

круг на плоскости с центром в точке О и радиусом R.

Функция выигрыша Н(х, у)=р(х, y),xeS,yeS, где р() — функ-

ция расстояния в R

, является строго вьшуклой по у при любом

фиксированном х, a S — выпуклое множество. Поэтому согласно

теореме п. 5.5 значение игры v равно

«=min maxp(x, у). (5.15)

yeS xeS

Вычисляя min max в (5.15), получаем, что v=R (см. пример 8 п. 2.6).

При этом точка y

eS, на которой достигается минимум выражения

тах/>(х, у), единственная и совпадает с центром круга S (т. е.

xeS

точкой О). Эта точка и является оптимальной стратегией игрока

2 (минимизирующего). Теорема утверждает, что у игрока 1 (мак-

симизирующего) существует оптимальная смешанная стратегия,

предписывающая положительную вероятность не более чем трем

точкам множества S. Однако вследствие симметрии множества

S в действительности оптимальная смешанная стратегия ц

игрока

1 предписывает с вероятностью

выбирать любые две диамет-

рально противоположные точки на границе множества S. Для до-

казательства оптимальности стратегий /х

, у

достаточно устано-

вить,

что К(х, y

)^K(pi

, y

)^K(jx

, у) для всех х, yeS, где К —

математическое ожидание выигрыша, К(р

, y

)=RI2 +

R/2

Действительно, К(х, y

)=p(0, x)^R и К(ц

, y)=p(x

y)/2

p(x

y)/2^R,

где х

ах

— произвольные диаметрально противополож-

ные точки на границе круга S. Оптимальность стратегий /х

и у

доказана.

5.6. Рассмотрим частный случай выпуклой игры Г=(Х, Y, Н),

когда X=Y=[0, 1], т. е. выпуклую игру на единичном квадрате.

Из теоремы п. 5.5 следует, что игрок 2 всегда имеет оптимальную

чистую стратегию }>

[0,

1]»

а.

игрок

— смешанную, сосредоточен-

ную не более чем на двух точках, при этом значение игры равно

v = min max Н(х, у). (5.16)

>б(0,

1] *б[0, 1]

Множество всех существенных стратегий {х} с [0, 1] игрока 1 явля-

ется подмножеством решений уравнений (п. 4.2)

H(x,y

)=v,xe[0, 1], (5.17)

где

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

Чистые стратегии х игро-

ка 1, удовлетворяющие равенству (5.17), иногда называются урав-

новешивающими.

Множество всех уравновешивающих стратегий иг-

рока / замкнуто и ограничено, т. е. компактно. Оптимальной чистой

стратегией игрока 2 является любая точка у

[0,

1], на которой

достигается (5.16).

Обозначим через

Н'

(х,

у) частную производную функции Н по

у (при у=0 и у=1 понимается соответственно правая и левая

производные).

Лемма.

Если

—

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

2 в

выпуклой

игре

на

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

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

Н,

дифференциру-

емой по у и

>0,

то

найдется уравновешивающая

стратегия х?

игрока

1, для

которой

Н'

(х

,у

)^0. (5.18)

Если же

<1,то

существует такая уравновешивающая стратегия

х"

игрока

1, что

(х»,у

)>0. (5.19)

Доказательство. Докажем (5.18). (Вторая часть леммы до-

казывается аналогично.) Предположим противное, а именно: для

каждой уравновешивающей стратегии х игрока / выполняется нера-

венство Н

(х,

)>0,

т. е. функция Н(х, •) в точке у* строго

возрастает. Это означает, что найдутся такие

е(рс)>0

и 0(х)>О, что

для^ер), 1], удовлетворяющих неравенству в(х)>у

—у>0, выпол-

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

Н(х,у)<Н(х,

)-Е(Х).

В силу непрерывности функции Н имеем, что для каждой урав-

новешивающей стратегии х и е(Зс)/2 найдется такое 5(х)>0, что при

в(х)>у

—у>0 выполняется неравенство

Н(х, у)<Н(х, у)-е(х)12<Н(х,

Уо

)-е(х)/2 =

=Н(х, у

)-е(х)/2

для всех, уравновешивающих стратегий х, для которых \x—x\<S(x).

Множество уравновешивающих стратегий компактно, поэтому его

можно покрыть конечным числом таких

(х)-окрестностей. Пусть

— наименьшее из всех соответствующих чисел

(х).

Тогда имеем

неравенство, справедливое для всех уравновешивающих стратегий

х (в том числе и для всех существенных стратегий)

Н(х, у)4:Н(х,

)-е/2,

где у

-тшв(х)<у<у

Пусть (i

— оптимальная смешанная стратегия игрока /. После-

днее неравенство справедливо для всех точек спектра стратегии ц

поэтому, интегрируя, получаем

К(ц

y)^KQi

, y

)-e/2=i>-e/2,

что противоречит оптимальности стратегии ц

Теорема. Пусть Г—выпуклая игра на единичном квадрате

с функцией

выигрыша

Н,

дифференцируемой

по у при любом х,

Уо

—

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

2,av —

значение

игры.

Тогда:

если

уо=1, то

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

имеет-

ся

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

х', для

которой выполняется

(5.18);

если

уо=0,

то

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

имеет-

ся

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

х", для

которой выполняется

(5.19);

если

0<у

<1,то

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

най-

дется

такая,

которая

является

смесью

двух

существенных

страте-

гий х?

их",удовлетворяющих

(5.18),

(5.19),

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

а и

1 —

а,

а с

[0,

1].

При этом а является решением уравнения

«Я;

(х

)

а)Щ

{х",

)=0.

(5.20)

Доказательство. Пусть у

=1- Тогда найдется уравновешива-

ющая стратегия

х"

игрока 1, для которой выполняется (5.18). Тогда

из выпуклости функции Н(х', у) следует, что она не возрастает по

у на всем промежутке [0, 1], достигая при у=\ своего минимума.

Это означает, что

#(х\ у

НН(х', у) (5.21)

при всех уе[0, 1]. С другой стороны, из (5.17) следует, что

Н(х, у

)^Н(х; у

) (5.22)

при всех хе[0, 1]. Неравенства (5.21), (5.22) показывают, что

(х

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

Случай

уо=0

исследуется аналогично. Перейдем к случаю 3.

Бели

0<>>

<1,

то имеются две уравновешивающие стратегии х!

и х", удовлетворяющие (5.18), (5.19) соответственно.

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

q>(fi)=№'yV,

)Hl-P)H;(x", у

Из (5.18), (5.19) следует, что <р(0)>0, <р(1)<0. Функция

q>(fj)

непре-

рывна, поэтому найдется <хе[0,

1],

для которого <р(а) = 0.

Рассмотрим смешанную стратегию ц

игрока 1, заключающую-

ся в выборе стратегии х' с вероятностью а и стратегии х" с вероят-

ностью

—а.

Функция

К(ц

у)=аН{х!, у)+(1-«)Н(х", у)

выпукла по у. Ее производная по у в точке у=у

равна

(ji

Уо

)=хн;(х',

)+у

-«)#;(*",

Уо

)=о.

Следовательно, в точке у

функция К(ц

, у) достигает минимума.

Отсюда, учитывая (5.17), имеем

К(Ио>

yo)<K(fi

, у),

К(Мо-

У)=Н(х, y

)=v=maxH(x,

)^H(x,

)

при всех хе[0, 1] и уе[0, I], что и доказывает оптимальность

стратегий ц

и у

5.7. Теорема п. 5.6 дает способ отыскания оптимальных страте-

гий, который мы проиллюстрируем на примере.

Пример 12. Рассмотрим игру на единичном квадрате с функцией

выигрыша Н(х, у)=(х—у)

. Это есть одномерный аналог примера

И, только в качестве функции выигрыша здесь взят квадрат рассто-

яния. Поэтому естественно ожидать, что значение v игры будет

равно v= 1/4, оптимальной стратегией игрока 2 является середина

отрезка у

= 1/2, а оптимальной стратегией игрока / — выбор с ве-

роятностью 1/2 крайних точек 0 и 1 отрезка [0, 1]. Покажем это,

используя теорему п. 5.6.

Заметим, что д

Н(х, у)/ду

= 2>0, так что игра Г — строго

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

тегию, которая является чистой (теорема п. 5.5). Пусть у — фик-

сированная стратегия игрока 2. Тогда

тах(х

Таким образом, из (5.16)

-*-{"-*

если

у<Л\1,

если >>>1/2.

»=min< min

(1— у)

min y

Оба внутренних минимума достигаются на

=1/2

и принимают

значение 1/4. Поэтому

ю=

1/4, а у

= 1/2

— единственная оптималь-

ная стратегия игрока 2.

Найдем оптимальную стратегию игрока 1. Для этого заметим,

что 0<у

<1 (у

=1/2). Найдем существенные стратегии игрока 1.

Уравнение (5.17) в данном случае принимает вид (х—1/2)

= 1/4.

Откуда JC

=0HX

=1,T. е. существенными для игрока 1 являются

крайние точки отрезка [0, 1].

Вычислим производные

ЯЖ, Jo)=l >0, Н'

(х

)=-1<0.

Составим уравнение (5.20) относительно а. Имеем

2а—1

= 0, откуда

=1/2.

Таким образом, оптимальная стратегия игрока 1 состоит

в выборе им чистых стратегий 0 и 1 с вероятностью 1/2.

5.8. В заключение параграфа приведем результат, аналогичный

п. 5.6 для вогнутой игры.

Теорема. Пусть Г —

вогнутая

игра на единичном квадрате

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

Н,

дифференцируемой

по х при любом фик-

сированном

у, х

—

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

1, av —

значение

игры.

Тогда:

если

то

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

имеет-

ся

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

у', для

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

Н'

(х

,У)>0; (5.23)

если

то

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

имеет-

ся

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

у", для

которой

,y"H0; (5.24)

если

то

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

най-

дется

такая,

которая

является

смесью

двух

существенных

страте-

гий

у'

у",

удовлетворяющих

(5.23),

(5.24),

с вероятностями /? и 1 —

/?.

При

этом

число

/?е[0, 1]

является решением уравнения

рн'Лч,

/)+0-№(*о> У)=о.

§ 6. ОДНОВРЕМЕННЫЕ ИГРЫ ПРЕСЛЕДОВАНИЯ

В этом параграфе приведено решение некоторых одновременных

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

стратегий игроков невыпуклые. К таким играм не применимы ре-

зультаты

5, поэтому решение для обоих игроков находится в клас-

се смешанных стратегий. Существование решения в этом классе

гарантируется теоремой п. 4.4.

6.1.

Пример 13.

(Одновременная игра преследования

кольце.)

Эта

игра является частным случаем примера 1 п. 1.2, когда множества

= S

= S и S представляют собой кольцо. Радиусы внешней и вну-

тренней окружностей кольца S обозначим соответственно R и г,

R>r.

Покажем, что оптимальными стратегиями игроков

я 2 являют-

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

(для игрока 2) и внешней (для игрока 1) окружностях кольца

S. Обозначим эти стратегии fi* (для игрока 1) и v* (для игрока

2).

При указанных стратегиях среднее значение выигрыша (рас-

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

2я 2я

K(ji*, v*)=-^ | Г

-2Rrcos(<p-\l/)d<pdij,=

4j>

+ r

-2Rrcos{ dt, = Ф(г, Д), (6.1)

где \//и

— полярные углы чистых стратегий игроков

и 2 соответ-

ственно. Если игрок

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

р,

ф, то ожидаемое расстояние (игрок 2 придерживается стратегии

v*) равно

2я

-£Р

К(х,у*)=Ф(г,р)=- y/r

-2prcostdt

При r^p^R функция

q>(p)=p

—2prcos<j;

монотонно воз-

растает. В частности,

(p(p)^q>(R)

при r^p^R. Отсюда имеем Ф(г,

р)^Ф(г, R). Поэтому для любой стратегии игрока 1 ожидаемое

расстояние не больше

(г,

R).

Рассмотрим теперь ситуацию (ц*, у), в которой yeS, p и

ц>

—

полярные координаты точки у. Имеем

2я

K(M*,y)=0(p,R)=- [ JR

-2Rpcos{</{,

r^p^R

Зафиксируем R и рассмотрим функцию Ф(р, Л) на отрезке

O^p^R.

Дифференцируя по р, можно убедиться, что

— = 0, ———>0, 0<р<Л.

Поэтому функция

(р,

R) монотонно возрастает по р, следователь-

но,

(г,

<Ф(р,

K(x,v*HK(M*,v*HK(p.*,y)

для всех х, у

Таким образом, оптимальность стратегий ц* и v*

доказана, а значение игры v равно

v =

K(ji*,

v*), где К(ц*, v*)

определяется (6.1). В частности, если S—окружность радиуса

R (случай г=Л), то значение игры равно 4R\n.

6.2. Пример 14. Рассмотрим одновременную игру, когда игрок

2 выбирает пару точек у

, у

}, где у

eS,y

eS,& игрок

не зная

выбора игрока

2,—

точку xeS. Выигрыш игрока 1 полагаем рав-

ным min р

(x,

). Приведем решение для случая, когда множество

i-l, 2

S представляет собой круг радиуса R с центром в начале координат

(точке

О):

S=S(0,R).

Рассмотрим функцию Ф(г, р) =

+ р

—4гр/я, где г и р принима-

ют значения из промежутка г, ре

[О,

R]. Установим свойства функ-

ции

(г,

р).

Лемма 1.

Функция

Ф(г, R) (как

функция переменного

г) являет-

ся

строго выпуклой

достигает абсолютного

минимума в

единст-

венной точке

2R/n.

Доказательство. Имеем д

Ф/дг

=2>0. Следовательно, функ-

ция Ф(г, р), re

[О,

R] строго выпукла, а производная

дФ(г,К) 4R

—-— = 2г (6.2)

or я

строго монотонна. Очевидно, что функция (6.2) в единственной

точке r

=2R/n обращается в нуль. В силу строгой вьшуклости Ф(г,

R) точка г

является единственной точкой абсолютного минимума.

Лемма доказана.

Лемма 2. Функция Ф(г

, р)

строго

выпукла по р и

достигает

абсолютного максимума

точке

=R.

Доказательство. В силу симметрии функция Ф(г, р) строго

выпукла по р. Поэтому максимум этой функции достигается в од-

ной из точек 0 или R. Имеем

Ф(г

, Д)-Ф(г

, 0)=г§ + Л

-4г

Л/я-г§ =

-4/n(2Rln)R=R

(я

-8)/л

>0.

Лемма доказана.

Из лемм 1, 2 вытекает, что пара (r

, R) является седловой точкой

функции Ф:

Ф(г

,р)<Ф(г

,Л)<Ф(г,Л).

Теорема.

Оптимальными смешанными стратегиями

являются:

для игрока 2 —

выбор

точки y

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

на

окружности

S(0, r

) с

центром

точке

О и

радиусом

(у

= —у

для игрока 1 —

выбор

точки х с

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

на

окружности

5(0, R).

Значение игры равно величине

Ф(г

, R).

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

через ц* и v* для игроков 1 я 2 соответственно. Пусть игрок

/ придерживается стратегии ц*, а игрок 2 — произвольной чистой

стратегии y={y

yi=(riCOS(pi,

r,sin<p;), i = l, 2. Рассмотрим сна-

чала случай, когда

у^=у

Обозначим через г число r

а через

— угол

<Pi=(p

Выигрыш игрока 1 равен

2л

К{ц*,у)=~

+г

-2Rr

cos

(ф-(р)Щ

2я J

•

—

(Лг)

= Ф(г, К).

(6.3)

Тогда по лемме

имеем К(р*, у)^Ф(г

, К).

В дальнейшем будем предполагать, что у

Фу

. Введем на плос-

кости полярную систему координат следующим образом. За начало

координат возьмем точку О, за полярную ось — луч, выходящий из

точки О перпендикулярно хорде АВ (множеству равноудаленных от

у\

и у2

точек круга S(0, R)). Для простоты записи предположим, что

и относительно новой системы координат точка y

имеет те же

координаты

(rjCoscpi,

r,sin

93,).

Тогда (рис. 6) выигрыш первого игро-

ка равен

2я

:— min

rf —

2RriCos(}l/

—

q)d\chl/

К(ц*,у)-

~2п

r\- 2Rr

cos (ф

ср

)]

# +

2я-0

+ -

2я

+ г\ -2Rr

cos

(ф -

(pi)]

йф.

Пусть

^i(<?) =

[(Л

+ г

)р-2Rr

sinpcos(p]/n, -p^cp^p;

F2(<?) =

+ Л)(n-P) + 2Rr

sinpcosф\/п,

р^(р^2п~р.

Стационарными точками функций F

и F

являются 0 и я соответст-

венно, так как имеем 0</?<я/2 и функция F[

(ср)

= - Rr

sin

sincp,

Рис.

((p)=

—Rr

sin /? sin

q>,

причем 0 и я — точки абсолютного мини-

мума функций F. и F

(F[ (ф)

при

<р е (—/?,

0),

(ф) >

при

(0,

/?);

аналогично,

Р'

((р)<0

при фе(/?, л),

((p)>0

при фе(я, 2я

—

/J)).

Следовательно,

^(^*,>;) = Р'

(ф

)+^

(ф

)^,Р

(0)+^

(я) =

(Л

+ г| -

2Лг

cos

ф)(А1/

-if

2ir-0

(

+ rf-2

cos(^-

))#, (6.4)

2я J

т. е. игрок 1 при использовании игроком 2 стратегии

=(—

{г

0} получит меньший выигрыш, чем при использовании

стратегии

U=(r,cos<Pi, rjSinpj), 1 =

Пусть теперь точки у,

_и

лежат на диаметре круга 5(0, R)

и расстояние между ними

2г.

Обозначим через 2а центральный угол,

опирающийся на дугу, стягиваемую хордой _АВ (рис. 7). Пред-

положим, что

>»!

= (.&

cos

—

г,

0),

=(Rcosa-|-r, 0). Тогда выигрыш

первого игрока равен

i/r(a,

r)=— [(Л

cos

^ - Л

cos

a-г)

+Л

sin

ф]4ф +

2я J

—a

2я-«

+— [(i?cos^-J?cosa+f)

+ i?

sin

^]# =

-iW-

2Rcos\l/(Rcosa + r) + (Rcosa+r)

]dil/+

— a

2ff-ct

+— [i?

-2J?cos^(i?cosa-r)+CRcosa-r)

]#=

2я J

{[i?

+ (i?cosa + r)

]a-2i?sina(i?cosa +

+[.R

+ (i?cosa-r)

](7c-a)4-2i?sinax(J?cosa-r)}.

Покажем, что функция ф(а, г) при фиксированном г достигает

минимума по а при а

я/2.

В результате элементарных вычислений

получим дф/да

{2Rsinu[(it—2a)r — nRcos

а]}/ж,

поэтому для доста-

точно малых значений а имеем дф(а, г)/оа<0, так как

sin

О,

r(n

— 2a) —

nRcosa<0 (в предельном случае гя—яЛ<0). Вместе

с тем

дф

(я/2,

г)/да =

При каждом фиксированном г функция дф(а, г)/8а не имеет

нулей по а, кроме а=я/2. Предположим противное. Пусть a

—

нуль этой функции в интервале (0, я/2). Тогда при <х=а

обратится

в нуль и функция G(a)

(n—2a)r—nRcosa.

Таким образом,

G(a,) = G(rc/2) =

Очевидно, что G(a)>0 для всех ae(a

, я/2). Это противоречит

выпуклости функции G(a) (G"(a)

nRcosa>0). Поэтому дф(а,

г)/да<0 при ae(0, я/2) и дф(п/2, г)/да=0. Следовательно, функция

ф(а, г) достигает абсолютного минимума по а при а=я/2: ф(а,

г)^ф(п/2, г). Значит, и в этом случае имеем

К(Ц*,

у)=Ф(ос,

г)^ф(п/2, г) =

Ф(г,

К)>Ф(г

, R). (6.5)

Из соотношений (6.3) — (6.5) вытекает, что для любой чистой

стратегии у={у^, у

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

K(n*,y)>Q>(r

,R). (6.6)

Пусть игрок 2 применяет стратегию v*, а игрок 1 — произвольную

чистую стратегию х=(рсо&ф, рыпф). Тогда игрок 1 получает

выигрыш

К(х, v*)=— тт\р

г1-2рг

со${ф-<р),

2я J

+r%

+ 2pr

costy-(p)]d<p=— min(p

+ r§-

-2pr

cos£, p

+ rl+2pr

cos£)dl;=Q>(r

, p)

и в силу леммы 2 имеем

*(х,у*)=Ф(г

,рКФ(г

,Л). (6.7)

Из неравенств (6.6) и (6.7) получаем, что

р.*

являются оптималь-

ными стратегиями игроков, а Ф(г

, R) — значение игры. Теорема

доказана.

6.3.

Пример

15.

Пусть игрок 2 выбирает набор из т точек у

••-,

Ут),

где

yteS,

..., т, а игрок 1 одновременно с ним — точку

xeS. Вьшгрыш игрока 1 полагаем равным min р(х, у). Решим

Ы1,

..., т