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

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

Val Tf»

(JCO,

, T)= max Val Г

J»

, yfr T). (3.6)

В силу непрерывности по t функции

С'

(у) и выполнения условия

С°Е(У)=У второе слагаемое в (3.5) стремится к нулю при и-»оо.

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

е^

(и). Из (3.5), (3.6) получаем

Val Г?» (х

, у* T)>Val Г|» (х

, у\\ Г)-е, (л). (3.7)

В силу непрерывности функции

Vairf"^,

Уо,

T) из (3.7) имеем

неравенство

Val Г?» (*о, Л, 7>Val Г J- (x

, y

, Г)-в, (и)-в, (и), (3.8)

где

Б2

(п)-»0 при и-+оо. Переходя в (3.8) к пределу при и-»оо

(что возможно на основании лемм п. 3.3, 3.4 и теоремы о су-

ществовании предела у монотонной ограниченной последовате-

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

Urn Val Г

?»

(JKO,

, Т) > lim Val Гf- Ос, у

, Т). (3.9)

Из леммы п. 3.3 вытекает противоположное неравенство. Следова-

тельно, оба предела в (3.9) совпадают.

3.6. Утверждение теоремы п. 3.5 доказано в предположении, что

последовательность разбиений интервала [0, 7]

<т„={/

=0</!<...</„= Т), п=\,...,

удовлетворяет условию

—

tj=TI2",j=0, 1,...,

2"—

Утверждения

тесрегы г. 3.5 и лемм п. 3.3, 3.4 справедливы для всякой последова-

тельности <7„ измельчающихся разбиений интервала [0, 7], т. е.

такой, что

о„+1

а„

(это означает, что разбиение

n+i

получается из

а„

добавлением новых точек)

у ((т„)=max (f,+i-/,)-* 0.

/ л-юо

Рассмотрим теперь такие любые последовательности разбиений

интервала [0, 7]

{<т„}

и {а

Лемма. Имеет

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

lim Val Г?»

(х

Уо,

= lim Val rf- (JC

, y

, T),

п-»со л-юо

гдех

eR",

T<co.

250

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

верждение леммы неверно, и предположим для определенности, что

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

lim Val Г?» (х„, У

о,

Т)> lim Val Г(

(х

, у

, Т)..

л-*оо л-»ао

Тогда согласно теореме п. 3.5 имеем

lim Val Г? (х

, у

, Т)

lim Val rf» (х

Уо,

Т).

Л-+0О Л-»00

Отсюда найдутся натуральные числа т

щ такие, что выполнено

неравенство

Val Г pi (х

, у

, 7)>Val rf-i

(JC

, Т).

Обозначим через Ъ разбиение интервала [О, Т\ точками, принад-

лежащими как разбиению cr

, так и разбиению а'

. Для него

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

Val Т\ (х

Уо,

7)<Val rf-i (х

, у

, Т)<

<Val Грч (х

Уо,

7)<Val Г? (х„,

Уо,

Г).

Откуда

Val Г*

(хо,

уо,

7)<Val Г? (х

, у

, Т).

Это противоречит (3.3), следовательно, сделанное предположение

неверно и утверждение леммы справедливо.

3.7. Теорема. При всех х

, у

, Т<

оо

в игре Г (х

, у

, Т) суще-

ствует ситуация

е-равновесия

для

любого

е>0. При этом

Val Г

(JCO,

уо,

Т) = lim Val Г? (х

, у

, Т), (3.10)

я-»оо

где

{а„}

— любая последовательность измельчающихся разбиений

интервала [0, 2].

Доказательство. Зададим произвольно выбранное число е>0

и покажем, что найдутся такие стратегии и, (•) и «, (•) игроков

Р и Е соответственно, что для всех стратегий и (-)еР и v QeE

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

К (хо, уо, и

(•), v ())-Е^К (х

, уо, Щ (•), v, (•))<

<К

(хо,

уо,

(•),«.(•))

«•

(

311

В силу теоремы п. 3.5 найдется такое разбиение а интервала [0, Т\,

251

что

Val Tf (x

Уо,

7)-lim Val Г? (x

, y

, T)<°

n-+cc 2

lim Val ГГ»

(JCO,

Уо,

7)-Val Г

, y

, T)<°

Л-ЮО 2

Положим м'() = (ст, a

,), v

() = (er, b^, где a^, b^ — оптимальные

стратегии игроков P"u Е соответственно в играх Г J (х

, уо, Т)

иГ1(хь,л,7).

Тогда справедливы соотношения:

(х

, и (•), v 0)<Val Г?

(дсь,

Уо,

Т)<

lim

Val Г5» (х

уо,

7)+-,«(•)еЕ; (3.12)

л-»оо 2

(хо,

Уо,

и (•), «' ())^Val Г

(х

уо,

Т)>

>lim

Val ГГ»

(хо,

уо,

7)--,

()еР. (3.13)

л-»оо 2

Из (3.12), (3.13) и теоремы п. 3.5 имеем

-'-<К

(хо,

уо,

и (•), v

(•))-Urn

Val ГГ" (х

, у

, Т)<- (3.14)

и-»сс

Из соотношений (3.12)—(3.14) следует (3.11).

В силу произвольности б из (3.14) следует (3.10). Теорема до-

казана.

3.8.

Замечание. При доказательстве теоремы существования

нигде не был использован специфический вид выигрыша р (х (7),

(Т)).

Существенной является лишь непрерывная зависимость вы-

игрыша от реализованных траекторий. Поэтому теорема п.3.7 оста-

ется справедливой, если вместо р (х (7), у (7)) рассмотреть любой

непрерывный функционал траекторий х (/), у (t).

частности, таким

функционалом может быть min p (x (t), у (*)), т. е. минимальное

расстояние между игроками в процессе игры. Поэтому результат

данного параграфа остается в силе и для дифференциальной игры

преследования на достижение минимального результата с пред-

писанной продолжительностью.

252

§ 4. ДИФФЕРЕНЦИАЛЬНЫЕ ИГРЫ ПРЕСЛЕДОВАНИЯ

НА БЫСТРОДЕЙСТВИЕ

4.1.

Дифференциальные игры преследования на быстродействие

представляют собой частный случай дифференциальных игр с ин-

тегральным выигрышем, определенных в п. 1.8. Классы стратегий

Р и Е те же, что и в игре с предписанной продолжительностью.

Предположим, что в R

задано множество F=

{(х,

у):

(х, у) < /,

/>0},

и пусть х (/), у (/) — траектории игроков Р и Е в ситуации

(и (•), v (•)) из начальных состояний х

уо-

Обозначим

(*о,

Уо,

и (•), v ())=min {t:(x (/),

(0)е?У,

(4.1)

если не существует такого /, что

(JC

(t),

(t))eF,

то

t„

(х

;

и (•), v (•))

полагается равным +оо. В дифференциальной игре преследования

на быстродействие выигрыш игрока Е полагают равным

К (х

уо,

и (•), v (•)) =

/„

(х

, у

; и (•), v (•)). (4.2)

Выигрыш игрока Р в ситуации 5=(х

, у

, и (•), v (•)) равен

{

— К (S)}

(игра антагонистическая).

Игра зависит от начальных состояний х

, у

, поэтому будем

обозначать ее через Г

(х

,у

Из определения функции выигрыша (4.2) следует, что в игре

(хо,

Уо)

целью игрока Е является максимизация времени сближе-

ния с игроком Р на заданное расстояние />0. Игрок Р, наоборот,

стремится минимизировать это время.

4.2.

Между игрой преследования на быстродействие Г (х

, у

)

и игрой преследования с предписанной продолжительностью на

достижение минимального результата существует прямая связь.

Пусть Г (х

, уо, Т) — игра преследования с предписанной продол-

жительностью Т на достижение минимального результата (выиг-

рыш игрока Е равен min p (x

(t),

у (/)). Было показано, что для игр

такого типа при любом

Е>0

в классе кусочно-программных страте-

гий существует ситуация е-равновесия (см. п. 3.8). Пусть V

(х

Т) — значение такой игры, а V

(х

) — значение игры Г (х

Уо),

если оно существует.

Лемма. При

фиксированных

, у

о функция

(х

, Т)

непрерыв-

на и не

возрастает

по Т

на отрезке

[0, оо].

Доказательство. Пусть 7'i>7'2>0. Обозначим через vj

(•)

253

стратегию игрока Е

игре Г

(х

{

которая гарантирует игроку

Е, что расстояние между ним и игроком Р на отрезке [О, Т{\ не

меньше max [О, V (х

, у

Т\)

—

е].

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

гарантирует расстояние max

[О,

V (х

, у

о,

7\) —е] между ними на

отрезке

[О,

TJ, где

<Ti.

Поэтому

(ль,

Уо,

)>тах

[О,

V (х

, у

, Г,)-

е]

(4.3)

(е-оптимальная в игре Г (х

, у

, Тх) стратегия не обязательно е-

оптимальна в игре Г (х

, у

)).

Поскольку е может быть выбрано

произвольным, из (4.3) следует второе утверждение леммы. Непре-

рывность V

(х

, Т) по Т доказывать не будем. Отметим лишь,

что это свойство можно получить, используя непрерывность V (х

Т) по

хо, уо-

4.3.

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

V(x

,yo,T)=l (4.4)

относительно Т. Возможны следующие три случая:

1) уравнение (4.4) не имеет корней;

2) имеет единственный корень;

3) имеет более одного корня.

В случае 3) из невозрастания и непрерывности функции V

(х

, Т)

по Т следует, что уравнение (4.4) имеет целый сегмент корней, т. е.

функция V (х

уо,

Т) как функция от Г имеет интервал постоянства.

Рассмотрим каждый случай отдельно.

Случай 1. В этом случае возможно:

a) V(x

, уо, Т)<1 для всех 7>0; б) inf V(x

, у

, Т)>1;

Г2»0

в) inf V(x

,yo, T) = l.

В случае а) имеем

V(x

уо,

0) = р(х

)<1,

т. е. /„ (х

уо,

и (•), v ())=0 для всех и (•), v (•). Тогда значение игры

(хо,

Уо)

равно V

(хо,

Уо) = 0.

В случае б) выполняется равенство

inf V

(хо,

уо,

Т)= lim V

, Т)>1.

Отсюда для любого Т>

(сколь угодно большого) у игрока Е най-

254

дется соответствующая стратегия v QeE, которая гарантирует

ему избежание /-встречи на отрезке

[О,

Т\. Но тогда игрок Р

не

имеет

стратегии, которая бы гарантировала ему /-встречу с игроком Е за

конечное время. В то же время нельзя утверждать, что игрок

Е обладает стратегией, гарантирующей избежание /-встречи за лю-

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

такая стратегия существует, сводится к решению игры качества для

игрока Е. Таким образом, при /<lim V (х

, у

о,

Т) можно лишь

Г-»оо

утверждать, что значение игры Г (х

, у

), если оно существует,

больше любого наперед заданного Г, т. е. равно +оо;

в) рассмотрим совместно со случаем 3).

Случай 2. Пусть Т

— единственный корень уравнения (4.4).

Тогда из невозрастания и непрерывности по Т функции V

(х

уо,

Т)

следует, что

V (х

уо,

T)>V

(х

уо,

То)

при всех Т< Т

(4.5)

(хо,

, T)<V

(хо,

То)

при всех Т>

;

lim V

(хо,

уо,

T)=V

(хо,

уо,

То).

(4.6)

Т->Т

Фиксируем произвольное

Т>Т

Рассмотрим игру преследования

Г (х

Уо,

Т). Она обладает ситуацией е-равновесия в классе кусочно-

программных стратегий для любого е>0. Это означает, в частно-

сти,

что для любого £>0 существует стратегия и, ()еР игрока Р,

которая гарантирует ему сближение с игроком Е на расстояние

(хо,

уо,

Т)

е,

т. е.

(и,

(•), v ())< V

(хо,

уо,

T) + e,v (•)еЕ, (4.7)

где К

(и

(•), v (•)) — функция выигрыша в игре Г (х

уо,

Т). Из (4.5),

(4.6) следует существование ё>0 такого, что для любого е<ё най-

дется число Т

(е),

То<

t (e)<

при котором

е = V

(хо,

уо,

То) - V

(хо,

уо,

(в)).

(4.8)

Из (4.7), (4.8) следует, что для любого е<е

(и,

(•), v (•))< V

{хо,

,T)

e^V

(хо,

, Т

(е))

+ е=

= V(xo,y

, То) =

в(-)еЕ,

т. е. стратегия и, (•) обеспечивает /-встречу за время Т. Отсюда,

255

в силу произвольности Т>

следует, что для любого Т>

найдет-

ся отвечающая ему стратегия и

(•)

Р,

которая гарантирует /-встре-

чу за время Г. Иными словами, для любого

8 > 0

существует щ

(•)

(хо,

Уо,

и, (•), v (•)) < Г

+8 при всех v

(•)

е Е. (4.9)

Аналогично доказывается существование v

()eEтакого, что

(*о,

Уо,

и (•), v

(•)) ^ Го -

«5

при всех и (•) е

Р.

(4.10)

Из (4.9), (4.10) следует, что в игре преследования на быстродей-

ствие Г (х

, у

о)

для любого 8>0 существует ситуация е-равновесия

в кусочно-программных стратегиях и значение игры равно Г

, где

Го

— единственный корень уравнения (4.4).

Случай 3. Обозначим через

Го

минимальный корень уравнения

(4.4).

Теперь, вообще говоря, мы не можем утверждать, что значе-

ние игры Val Г (х

)

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

(х

, Г

) = / следу-

ет лишь, что в игре Г (х

, у

, Г

) у игрока Р для любого е>0

существует стратегия и, (•), гарантирующая ему за время Г

встречу

с игроком Е на расстоянии не более чем /+е, а из существования

более одного корня уравнения (4.4) и монотонности V (х

, у

, Г) по

Г получаем существование интервала постоянства функции V

(х

Т) по Ге[Г

, Г]]. Поэтому увеличение продолжительности игры

(JC

уо,

) на 8, где 8<Т

{

—

не приводит к уменьшению гаран-

тированного сближения с игроком Е, т. е. для всех

Те[Т

Т{\

игрок

Р может лишь обеспечить сближение с игроком Е на расстояние

1+е

(для любого е>0), и нет основания считать, что при каком-то

Те

[Г

Г]] величина е окажется равной нулю. Если бы в игре Г (х

Уо,

То)

существовала ситуация равновесия (а не ситуация е-равнове-

сия),

то значение игры Г (х

, у

) было бы равно Г

и в случае 3.

4.4.

Модифицируем понятие ситуации равновесия в игре Г (х

Уо).

Далее в этом параграфе удобнее использовать запись Г

(х

,1)

вместо Г (хо,

уо),

подчеркивая, что игра Г (х

, .Уо, 0 заканчивается

при сближении игроков на расстояние /.

Пусть

„

(х

, уо, и (•), v (•)) — время до момента сближения на

расстояние / в ситуации (и (•), v (•)) и заданы е^О, <5>0.

Определение. Будем

говорить,

что пара стратегий

(•), v\ (•)

образует ситуацию

е,

8-равновесия

в игре Г (х

, у

, /), если

256

t'n

(х

, у

; и (•), vi (-)) + e>t'

(хо,

;

й? (•), v\ (•))>

>t'

;Zi О, v

(•))-£,

для всех

стратегий

и ()еР, v QeE.

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

существует

такая

последовательность

{$к},

&к^0, <5*-*0, что во всех играх Г (х

;

l+Sfc) для

любого

е>0

существуют ситуации

е-равновесия.

Тогда предел

Ит V

(х

уо,

/+<5*)= V

(хо,

уо,

Jfc-»oo

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

Г (х

, у

, I) в

обобщенном

смысле.

Заметим, что величина V (х

, у

,1) не зависит от выбора после-

довательности {8

} вследствие монотонного убывания функции

(хо,

уо,

I) по /.

Определение. Будем говорить, что игра Г (х

, у

, I) имеет

значение

обобщенном

смысле,

если существует такая

последовате-

льность

-*0,

что для

любого

е>0 и 8

}

игре

Г (х

уо,

существует ситуация

в,

-равновесия.

Можно показать, что если игра Г (х

, у

о,

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

в обычном смысле, то значение ее V (х

, у

о,

О (в обобщенном

смысле) существует и равно

lim

(хо,

уо,

и\ (•), vt (•))= V

(хо,

уо,

/).

«-.о

-+0

Из определения значения и решения игры Г

(х

о,

/) (в обобщенном

смысле) вытекает, что если в игре Г (х

, у

о,

О Для любого е>0

существует е-ситуация равновесия в обычном смысле (т. е. решение

в обычном смысле), то V

(х

Уо,

1)= V' (х

.Уо,

0 (достаточно взять

последовательность <5*=0 для всех к).

Теорема. Пусть уравнение (4.4) имеет более одного корня

и Т

—

наименьший

корень,

<со.

Тогда существует значение

(х

о,

1)(в

обобщенном смысле) игры преследования на

быстродей-

ствие

(хо,

уо,

О и

(х

уо,

/)=

То.

Доказательство. Из монотонности и непрерывности функции

(

о,

Уо,

Т) по Т следует существование такой последовательности

257

слева, что V

(х

)-*

(х

)=I

в точках Т

функция

У (*(ь

Уо,

) строго монотонна. Пусть

=V(x

)-l^0.

Из строгой монотонности функции V

(х

уо,

Т) в точках Т

выте-

кает, что уравнение V

(х

, Т)=1+5

имеет единственный корень

. Это означает, что для любого

е{8

)

в играх Г (х

, у

, 1+8

)

существует ситуация е-равновесия для любого е>0 (см. случай 2) п.

4.3).

Значит, в игре Г

(JC

, /) существует решение в обобщенном

смысле:

Urn V(х

, у

,1+ 5

)=lim T

= Т

= V (х

, у

,1)

t-»0O /fc-»QO

и теорема доказана.

Рассмотрим теперь случай в) п. 4.3. Имеем: inf V

(х

уо,

Т)=1.

Пусть

-*со.

Тогда lim

(х

уо,

) =

Из монотонности и непре-

к-*ао

рывности V

{хо,

уо, Т) по Г следует, что последовательность {7*}

можно выбрать так, что в точках Т

функция V

{х

, Т) строго

монотонна. Тогда как и при доказательстве теоремы п. 4.4 можно

показать, что существует такая последовательность {8

}, что

lim V(x

, /+«5*) =

Шп

=7'o=oo.

fc-»oo Jk-»oo

Таким образом, и в данном случае обобщенное решение суще-

ствует, а обобщенное значение игры Г (х

Уо,

I) равно бесконеч-

ности.

4.5.

Часто оказывается важным определить, может ли игрок

Р гарантировать /-встречу из данных начальных позиций х, у за

фиксированное время Т. Если это невозможно, то может ли игрок

Е гарантировать избежание /-встречи в течение заданного времени.

Пусть V

(х,

у, Т) — значение игры с предписанной продолжите-

льностью Т из начальных состояний х, yeR" с выигрышем

min р (х (0, у (*))• Тогда возможны следующие альтернативы:

0<!«Г

1) V{x,y, T)>1;

2) V{x,y, T)<1.

Случай 1. Из определения функции V (х, у, Т) следует, что для

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

258

стратегий и (•) справедливо неравенство

К(х, у; и (•),

(.))> V (х, у, Г)-е.

Выбрав

достаточно малым, можно добиться выполнения неравен-

ства

К (х, у; и (•), «; (.))> V

{х,

у, Т)-г>1

для всех стратегий и ()еЕ игрока Р. Из вида функции выигрыша

К следует, что, используя стратегию «* (•), игрок £ может гаран-

тировать выполнение неравенства min р (х (/),

(/))>/независимо

от действий игрока Р, т. е. в рассматриваемом случае игрок Е гара-

нтирует избежание /-встречи на отрезке времени

[0,

7] независимо от

действий игрока Р.

Случай 2. Пусть

Го

— минимальный корень уравнения

V (х, у, Г)=/при фиксированных х, у (если р (х, у)<1, то Г

полага-

ем равным 0). Тогда из определения V (х, у, Г

) следует, что в игре

Г (х, у, Г

) игрок Р при любом е>0 обладает стратегией и* (•),

гарантирующей выполнение неравенства

К (х, у;

и.*

(•), v (-Ж V (х, у, Г

)+£=1+е

для всех стратегий v ()eE игрока Е. Из вида функции выигрыша

К следует, что, используя стратегию и \ (•), игрок Р может гаран-

тировать выполнение неравенства min р (х

(t),

у (г))</+е независи-

мо от действий игрока Е. Продолжая произвольным образом стра-

тегию

м*

(•) на отрезок [Г

, 7], получаем, что в случае 2 игрок Р при

любом е>0 может гарантировать (/+е)-встречу с игроком Е за

время Г независимо от действий последнего.

Фактически доказана следующая теорема (об альтернативе).

Теорема. Для любых х, yeR", Г>0

справедливо,

по крайней

мере,

одно

из

следующих

утверждений:

1) из

начальных состояний

х, у

игрок

может

течение времени

гарантировать избежание

1-встречи

независимо

от

действий

игро-

ка Р;

при любом

е>0

игрок

может гарантировать (1+в)-встречу

игроком

Е из

начальных состояний

х, у за время Г

независимо

от

действий

последнего.

4.6.

Для каждого фиксированного Г>

все пространство R"x.R

делится на три непересекающиеся области: область A

{x,y:V

{x,

у,

Т)<1),

которую будем называть зоной захвата; область В=

{х,

у: V(х, у, Т)>1), которую естественно назвать зоной избежа-

259