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

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

8V\

их подробно для одной из компонент й

[х, —

вектора

и.

Исследование остальных

компонент вектора и и компонент вектора v проводится аналогично. Дня простоты

предположим, что в некоторой точке (х', у', г)

- ( '

гтора v

(х',

у'.

. . I , 8V(x', у', Г)\

=и

[х.

j=a„

Случай 1. Существует шар в пространстве R с центром в точке х', для всех

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

. . / dV(x. у', Г)\

Чт^Щп

[X,

= а„

Функция

на этом шаре принимает постоянное значение, поэтому

в точке

х' имеем

—=0,

1-1,.., и.

0Х{

Случай 2. Такого шара не существует. Тогда найдется последовательность х

шп х,=х' такая, что

г-»оо

><W

Отсюда

_ / 8V(x

,y', T)\

"—Тх—у

8 / " 8V\ I \_

m V/.i

dXi\(x

у'.

Г)

'\(хг.

й))

8V Э/, . _/ dV(x,y, Т)\

Из непрерывности производных —, — и функции и=и\х,

следу-

ди

\ дх )

ет, что предыдущее равенство выполняется и в точке (х', у', Т).

Таким образом, два последних слагаемых в (6.12) равны нулю, и при всех

(х, у, T)eR х

Л ж

[0,

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

дБ d

V " d

I fi(x, «)-

дх

дТдх

к Ы1

8х,дх

" 8V 8ft " 8

-Irr-E

—^'

J)=0

*=1,

...,«.

iml

dxjdx

ш1

ду,дх

Пусть х (f), у

(<).

'е

[0,

—

решение системы

. / ./ 8V(x,y,T-t)\\ . / _/ dV(x,y,T-t)\\

x=f[x,u[x, Jj,

\y..\y.

с начальным условием х (0)=х<ь у (0)=>>о- Вдоль решения x (f), у

(l)

имеем

270

где

(х

(/), у

(О,

Т- о " д

(х (О,

(О,

т-о

/ чч

8Т8х

к 1ш{

8х,3х

_ у

$®>

~'> э/i

(* (0.

fi (0)_

,_1 Sxi дх

К(х

(0,^(0. Г-О ,-„ -,

чч n L

-,ч -f-r, 3V(x(t),y(t), T-l)\

(0-и

(

х (0,

— J,

-,ч

-Л/ч ^М,

*(0,

г-0\

Однако,

d (dv (х

(о,

у (0, г-

г)\

а»У(х(о, у (о, г- о

- ; 1-1 — //

(* (0,

(ОН

Л\ дх

(

._, dx

dxj

^d*V(x{t),Ht), T-t) ,- _„

а»У(х(0,у(0, Г-Q

+1 — а (у (О, • (0) г-— . *-1,

•••>

и. (6-14)

Заметим, что у дважды непрерывно дифференцируемой функции можно менять

порядок дифференцирования. Перепишем (6.13) с учетом (6.14) в виде

fSV (x («),

(Г),

Г-0\ Д

ЭК (х (Г),

(г),

Г-0 9/i (х (0, 2 (0)

•)\_"

arfr(0.y(0.

л\ ах* / ._, Эх< ах

*-1 «•

Аналогичным образом получим уравнения

d /8V

(х

(/),

(0, т-1)\

"ev(x

(0, у

(О,

г-о fy

(у (о, г (D)

_rf /ау(х(о, у (о,

т-»\_ _ ,

1=1,

..., Л.

Так как при

[О,

Г]

К (х

(0, у

(О,

Г-О-Я

(х (Г),

у (Г)),

то

dt\ дТ

*Ь

Введем следующие обозначения:

„ , Д dV(x(t), J (j), Г-0

F (0=

Зх,

271

„

A dV(x

(t),

(I),

T-l) .

{t)={v

{t)},

{i)t{v

{t)},

„ , дэк(5(0.>М, r-i)

(/)

В результате получим следующую систему обыкновенных дифференциальных урав-

нений для функций х (/), у (О, V

(/), V

(/), F

(r):

±,-/,

(х,

л-

с,;

о-,

к,»,

^ _ " „ ш*. Д(«. Ш) ^ _ " в»

(у.

К,»

ы\

дх

* /-1

ЗУк

(6.15)

=0,

/, fc=l я

и, кроме того, согласно (6.6) имеем

Ут=

I V„g,

(у,

; (у, К,))+ 21

(х, 5 (х, F

)).

f-1

i-1

Для решения системы нелинейных уравнений (6.15) относительно функций х

((),

.у

(О,

Ух (0> ^ (0> ^т(') необходимо определить начальные условия. Для функции

У (* (Of

(0. Г—0 они заданы в момент времени t=T, поэтому введем переменную

Г—

и запишем уравнение характеристик

регрессивной форме. Введем обозначе-

ния х= — х, у= —

у.

Уравнения характеристик принимают следующий вид:

*.=

-/,(*.

й), yt=-gi

(У.

v),

(6.16)

•>'

(х,

и) о •

(у,

5) о

* ,Г, *' 3x

3j>*

При задании начальных условий для системы (6.16) используется соотношение

V(x, у, 1) \т-ъ=Н

(х,

у). Пусть х |

_o=J.

|т-о=-г'- Тогда

дН

F,l

-o=—

' 5х

(

*-*, y-f'. *V. lt-0 =

ен

By,

x—s,

y-/i

(6.17)

Krlt-0-

I ^ |

.O ft

(5',

К, |

))+ Z V

I,.,/,

(5,

(J. K,

)).

i-1

Подробные исследования возможных путей решения системы (6.16)—(6.17) см.

в[1].

Аналогичным образом, используя уравнение (6.8), можно записать уравнение

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

272

§ 7. МЕТОДЫ ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ

ДЛЯ РЕШЕНИЯ ДИФФЕРЕНЦИАЛЬНЫХ ИГР ПРЕСЛЕДОВАНИЯ

7.1.

Пусть Г

(х, у, Т) — дискретная форма дифференциальной

игры Г (х, у, Т) продолжительностью Т>0 с фиксированным шагом

разбиения 8 и дискриминацией игрока Е на время <5>0 вперед.

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

(х, у, Т) значение игры T

(х, у,

Т)*.

Тогда

\imV

(x,y,T)=V(x,y,T)

и оптимальные стратегии в игре T

(x, у, Т) при достаточно малых

8 могут быть эффективно использованы для построения ситуаций

равновесия в игре Г (х, у, Г).

7.2. Идея численного метода состоит в построении алгоритма

нахождения решения игры Г

(х, у, Т). Перейдем непосредственно

к изложению метода.

Нулевое приближение. За нулевое приближение функции зна-

чения игры V

(x, у, Т) принимаем функцию

V°

(х, у, Т)= max min p (£,

г\),

(7.1)

СI (у)

(еСЦх)

где Ср (х),

СЕ

(У)

— множества достижимости игроков Р и Е из

начальных состояний х, yeR" к моменту времени Т.

Выбор функции V\ (x, у, Т) в качестве начального приближения

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

емый регулярный случай) она оказывается значением игры

Г (х, у, Т). Следующие приближения строятся по правилу:

V\ (х, у, Т)= max min V\ (£, i\, T-S),

i,6C«(y)

{eC»(x)

V\ (x, y,T)= max min V\ ({,

r\,

T-8),

V\ (x, y,T)= max min V\ ({, q, T-S) (7.2)

при T>8 и V\ (x, y, T)= Vl (x, y, T) при T^S, к> 1.

Как видно из формул (7.2), операция max min берется по множе-

ствам достижимости С

(у),

(х) за время 8, т. е. за один шаг

дискретной игры Г

(х, у, Т).

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

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

273

7.3.

Теорема. При фиксированных х, у, Т, 8

числовая

последова-

тельность [Vg

(x, у, 7)]

не убывает

ростом

к.

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

V\(x.y.T)>V°

(x,y,T).

Для всех £еСр (х) справедливо: С\~

(О

<=•

(х). Для любых

цеС

(г\),

£еС

(х) имеем

min p (I, rj)^ min о (?,

г\).

Отсюда

(х, у, Т)— max

min max min

p (5, jj)>

ueC^CO (eC'

(x) ijeCj-'fo) fsCj-'(f)

^ max

max min

p (£, jj)=

eC^(y) iieC'-'O,)

}

{x)

= max

min

p (£, n)= V° (x, у,

Т).

Предположим теперь, что для

l^k

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

,(x,y.T)>V'f

(x,y,T) (7.3)

и докажем его для 1=к+1. Из соотношений (7.2) и (7.3) следует, что

(х. у, Т)= max

min

({,

IJ, Г-5)>

>max min Vt

&4>T-S)=V\(x.y,T\

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

случае Т>8 по индукции утверждение те-

оремы доказано. В случае

Т^д

утверждение теоремы очевидно.

7.4. Теорема.

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

{Vg(x,

у,

Г)} сходится за

конечное число шагов

N, при этом

имеет место оценка

iV<

+1,

где

квадратные скобки означают

целую

часть.

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

N=[T/6] +

l. Покажем, что

VHx,y,T)=V^

(x,y,T).

(7.4)

Равенство (7.4) легко получить из построения последовательности

[V*

(x, у, 7)]. Действительно,

, (х, у, Т)= max

min

V?~

«\

, T-8) =

JeC'^ty)

(

eC'

(x)

= max

min max ...

чЧс^Ь)

{'бс;м

бС^(ч

)

274

... max min

V\^

T-(N-l)

8).

Аналогично имеем

(x, у, Т)= max min max ...

4«eC^O0 feCjW if'eC^Oi»)

... max min

V\(f~\

T-(N-l)

8).

Однако Т—

(N—

8 =

<x<8,

поэтому

VsKS, ,4 ,<*•)= У s\S ,4 ,«)=*'«(?

откуда и следует равенство (7.4).

Совпадение членов последовательности V\ при k^N выводится

из (7.4) индукцией. Теорема доказана.

7.5.

Теорема. Предел

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

{V* (x, у, Т)} совпа-

дает

со

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

(х, у, Т).

Доказательство. Данная теорема является, по существу, сле-

дствием теоремы п. 7.4. Действительно, обозначим

(x,y,

r) =

lim

{х,

У,

Т).

Jt-»QO

Сходимость происходит за конечное число шагов, не превосходящее

'N=[T/8]+1,

поэтому в рекуррентном уравнении (7.2) можно перей-

ти к пределу при к-*со. Предельная функция V

(x, у, Т) удовлет-

воряет уравнению

V, (х, у, Т)= max min V, ({, п, Т-8) (7.5)

при начальном условии

{х, у, Т) |

г<а= max min p (<!;,

г\),

(7.6)

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

(х, у, Т) была значением игры Y

(х, у, Т).

1.6. Зная функцию V

(x, у, Т), можно, используя уравнение (7.5),

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

(х, у, Т). С помощью стратегий, оптимальных в игре

(х, у, Т),

строятся е-оптимальные стратегии в основной игре Г (х, у, Т).

Как следует из (7.4), совпадение двух последовательных прибли-

жений на шагах к и к+1 означает, что соответствующее приближе-

275

ние уже является значением игры Г

(х, у, Т), поскольку в этом

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

к-м.

приближени-

ем.

Такое совпадение и является критерием прекращения вычисле-

ний. Имеются достаточные основания полагать, что в широком

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

указанное в теореме п. 7.4, в частности в «регулярном случае»

вычисления прекращаются на 1-м шаге после вычисления функции

V\ (x, у, Т) (это в то же время является критерием «регулярности»).

7.7. Приведем модификацию метода последовательных прибли-

жений, изложенного выше.

В качестве начального приближения возьмем функцию

V°

(х, у, Т) = V\ (х, у, Т), где

(x, у, Т) определена равенством

(7.1).

Следующие приближения строим по правилу:

(х.у, Г)=тах max min

(<!;,

r\,

T-iS)

16[1:Л1 ijeCjJC) {6CJW

при Т>5, где N=[TI5\, и

У*,*

(х, у, Т)= V\ {х, у, Т) при Т^8.

Для последовательности функций {Р* (х, у, Т)} так

же,

как и для

последовательности функций {К* (х, у, Г)}, справедливы утвержде-

ния теорем п. 7.3—7.5.

Доказательство этих утверждений для последовательности фун-

кций

{

Vf (x, у, Т)} почти дословно повторяет аналогичные рассуж-

дения для последовательности функций {V

(x, у, Г)}. Функци-

ональное уравнение для функции значения игры Г

(х, у, Т) прини-

мает в области {(х, у, Т)

Т>

вид

(x, у, Г)=тах max min V

(£,

t\,

T-

i8),

(7.7)

/e[l:A1 46C»(y) (еС*(х)

где N=[T/8), а начальное условие остается прежним, т. е. имеет вид

(7.6).

7.8.

Докажем эквивалентность уравнений (7.5) и (7.7).

Теорема. Уравнения (7.5) и (7.7) с начальным условием (7.6)

являются

эквивалентными.

Доказательство. Пусть функция V

(x, у, Т) удовлетворяет

уравнению (7.5) и начальному условию (7.6). Покажем, что она

удовлетворяет уравнению (7.7) в области {(х, у, 7)\Т>8}.

Действительно, справедливы следующие соотношения:

(х, у,Т)= max min V

(£,»/, T-S)=

= max min max min V

(2f,

rj,

T—28)^

,6C«C) {ec;w чбС^ч)

?GC««)

276

^ max max min min

(5,

rj,

T—2S)--

,6C«

(y) ЦеС'^ч) (eC'

(x) feC

= max min V

(£,

r\,

T-28)^...

цеС»(у) {6C»(x)

...> max min V

(£,

rj,

T—iS)^... .

,бС»

{

C«(x)

При i=

имеем

V, (x, y, T)= max min F, (5,»?, T-5),

поэтому справедливо равенство

(x, у, 7)= max max min V

(<!;,

?/, T—iS),

ie[l:N\

r,eC'(y) (eC»(x)

где N=

[Т/8],

что и доказывает требуемое утверждение.

Пусть теперь функция V

(x, у, Т) в области {(х, у, Т)\Т>д}

удовлетворяет уравнению (7.7) и начальному условию (7.6). Пока-

жем, что она удовлетворяет также уравнению (7.5). Предположим

противное. Тогда в области {(х, у, Т)\Т>8} должно иметь место

неравенство

Однако

Vi (х, у, Т)> max min V

(£,t], T-S).

чеС'М ieC'tx)

max min

(£,

rj,

T—8) =

цбС'С) (еСЧх)

= max min max max min V

(£,

rj,

T—

(i+l) 8)^

tieC^iy) feC^(x) tell-.N-l] jeC'W JeC^K)

> max max max min min V

(£,

rj,

T— (i+l) 8)=

4eC'

(y) ie[l:N-l] jeCjfo) (eC^x) JeCj«)

= max max max min min

(£,

rj,

T— (i+l)

8) =

W-.N-l]

цеС^С) »бС;(ч) feC^M JsCjJtf)

= max max min V

(<!;,

r\,

T-i8)=

(x, у, Т).

ie\l:N\

цеС*(у) (eC

(x)

Полученное противоречие доказывает теорему.

277

§ 8. ПРИМЕРЫ РЕШЕНИЯ ДИФФЕРЕНЦИАЛЬНЫХ

ИГР ПРЕСЛЕДОВАНИЯ

8.1.

Пример 4. (Простое

движение).

Рассмотрим дифференци-

альную игру Г (jc

уо,

Т), в которой движение игроков Р а Е проис-

ходит в евклидовом пространстве tC согласно следующим уравне-

ниям:

дляР:х=а«(/),

||м(/)К1,

х (0)=х

для Е:у =

р\

(О,

II*

(OKI, у (0)=

Уо

, (8.1)

где а,

— константы а>/?>0, х, у, и, veR".

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

Н(х(Т),у(Т))=\\х(Т)-у(Т)\\.

Пусть

Г*

(х, у,Т) — дискретная форма дифференциальной игры

Г (х, у, Т) с шагом разбиения д>0 и дискриминацией игрока Е.

Игра t

(х, у, Т) протекает в N шагов, где N=

Т/8.

Согласно

результатам

2 (см. пример п. 2.3) игра Г

(х, у, 7) имеет значение

V, (х, у, 7

)=тах {0, \\x-y\\-NS(a-P)} =

=тах{0,\\х-у\\-Т(

-Р)},

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

ющей начальные состояния х, у.

Согласно результатам

§ 3

значение исходной дифференциальной

игры

V(x, у, r)=lim V

(х, у, Г)=тах {0, \\х-у\\-Т(а-0)}. (8.2)

«-•о

Можно убедиться, что

V(x,y, T)= max min \\х'—у'\\=р

(х, у),

где Cl(y) = S (у, рТ) — шар в R" радиуса /?Г с центром в точке у,

аналогично Cp(x) = S (х,

<хТ).

Тем самым согласно лемме п. 5.3

у игрока Е

игре Г

(х

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

стратегия v* (t), te[0, Г], которая приводит траекторию игрока

Ев точку

y*eCl(Уо),

для которой

Рт(х

Уо)=

min \\x'-y*\\.

х'еС

(х

)

278

Очевидно,

Уо-хо

v* (j)=v*-< 1л>-*о1

При Уо^Хо,

v при

=х

где

eR" — произвольный вектор такой, что

||v||

Из результатов

§ 6 следует, что в области

Д={(х.*7):||х-:у||-Г(а-/?)>0},

где существуют непрерывные частные производные

SV__.

3V__dV_

х-у

—

--(fi-P),

~ ~J

функция V (х, у, Т) удовлетворяет уравнению (6.4):

dV . (dV \ „ (dV \ „ ,„ „

--amin [-,u -/?тах i—,v =0. (8.3)

В уравнении (8.3) минимум и максимум достигаются при управле-

ниях

- ( dV\ дх у-х

х, — = -= ;

\ дх) 3V\ ly-x\'

дх

- (

Л_

ду

у'

~д~у)~~т~1у-х\\

ду

(8.4)

(8.5)

Стратегии (8.4), (8.5) являются оптимальными в дифференциаль-

ной игре (8.1). Стратегию

(х, у), определяемую соотношением

(8.4),

называют «погонной стратегией», так как в каждый момент

времени вектор скорости игрока Р при использовании этой страте-

гии нацелен на преследуемого игрока Е.

8.2. Пример 5. (Игра

преследования

при наличии сил трения).

Преследование происходит на плоскости. Уравнения движения име-

ют следующий вид:

для игрока Р:

/о £Л

p^au.-kpp,,

i=l, 2,

||ы||<1;

279