Петросян_Теория_игр

системы (1.7) из начальных состояний х0, у0. Стратегии и*(х, у, i), v* (х, у, 0 называются оптимальными стратегиями игроков Р и Е.

Установим различие понятий ситуации равновесия в кусочнопрограммных и синтезирующих стратегиях. Заметим, что опреде­ лить ситуацию равновесия в обычном смысле в классе функций и (х, У, 0> v(x, у, i) невозможно из-за непрямоугольности пространства ситуаций, т. е. в синтезирующих стратегиях невозможно потребо­ вать выполнения неравенства (1.13) для всех стратегий и (х, у, t), v (х, у, i), поскольку некоторые пары (и*, v), (и, v*) могут не быть допустимыми (система уравнений (1.7) в соответствующей ситуации может не иметь решения вообще или не иметь единственного реше­ ния).

В дальнейшем, если специально не будет оговорено, во всех случаях будем рассматривать классы кусочно-программных страте­ гий. Прежде чем перейти к доказательству существования ситуации е-равновесия в дифференциальной игре, рассмотрим один вспомога­ тельный класс многошаговых игр с полной информацией.

§2. МНОГОШАГОВЫЕ ИГРЫ С ПОЛНОЙ ИНФОРМАЦИЕЙ

ИБЕСКОНЕЧНЫМ ЧИСЛОМ АЛЬТЕРНАТИВ

2.1.Рассмотрим класс многошаговых игр с полной информаци­ ей, представляющих собой обобщение игр с полной информацией из

§1 гл. IV. Игра происходит в л-мерном евклидовом пространстве

R". Будем обозначать через х е R" местоположение (позицию) игрока 1, а через yeRn — местоположение игрока 2. Пусть для каждых xeR", yeR" определены множества Ux, Vy соответственно, которые будем предполагать компактными множествами евклидового про­ странства R". Игра начинается из позиции х0, у0. На 1-м шаге игроки 1 я 2 выбирают точки хх е С/Хо и ух e F>0. При этом выбор игрока 2 сообщается игроку 1 до выбора им точки JCX e UXo. В точках

xt, yt игроки 1 и 2 выбирают точки хге UXl ny2e Vyx, и выбор игрока 2 сообщается игроку / перед выбором им точки х2 е UXl и т. д. На

к-м шаге в позициях хк_и ук_х игроки выбирают xkeUXk_x, уке Vyk_v

и выбор игрока 2 сообщается игроку / перед выбором им точки xkeUXk_v Процесс заканчивается на JV-м шаге выбором xwe [/,„_,,

yNe VyK_t и переходом в состояние xN, yN.

Семейства множеств Ux, Vy, xeRn,yeRn предполагаются непре­ рывными в метрике Хаусдорфа по х, у. Это означает, что для любого Б > 0 найдется такое д>0, что при |JC—лс0|<^ (\у—у0\<&)

240

(U^=>UX. (£/,).=>£/,„; (V,X=V,. (V,)t*V„.

Здесь Ut(V,) — £-окрестность множества U(V).

Следующий результат хорошо известен в анализе (см. [12]).

Лемма. Пусть /(х1, / ) — непрерывная функция на декартовом произведении Uxx Vr Тогда если семейства \UX}, \Vy} — непрерывны

по Хаусдорфу по х, у, то функционалы

fi (х, y)=ma.x minf(x', / ) ,

/eVy x!eVx

F2(x, y)=min min/(f, / )

*eVx?eVy
непрерывны_по х, у.	игроков
Пусть x=(x0, .... xN) и y=(y0, .... yN) — траектории
1 и 2 соответственно, реализовавшиеся в процессе игры. Выигры­
шем игрока 2 является величина
max f(xk,yk)=F(x,y),	(2.1)

где/(х, у) — непрерывная функция от х, у. Выигрыш игрока 1 равен (-F) (игра антагонистическая).

Будем предполагать, что данная игра с полной информацией, т. е. в каждый момент времени (на каждом шаге) игрокам известны позиции хк, ук и момент времени к+l, а игроку 1, кроме того,

известен выбор yk+i игрока 2 в этот момент.
Стратегиями игрока	1 являются	всевозможные	функции
и(х, у, t) такие, что и(хк..и	ук, к)е UXk_r	Стратегиями игрока 2 —
всевозможные функции v(x, у, t) такие, что v(xk-\, Ук-и			k)eVyk_v

Эти стратегии будем называть чистыми стратегиями (в отличие от смешанных).

Пусть игроки 1 и 2 применяют чистые стратегии и(х, у, t), v(x, у, t). В ситуации (и (•), v (•)) игра происходит следующим образом. На

1-м шаге игрок 2 из состояния у0	переходит в состояние yt=v (х0, у0
1) и игрок 1 — из состояния х0	в состояние хх = и(х0, j>i \) = и(х0,
v(x0, у0, 1), 1) (поскольку игрок 1 знает выбор игрока 2). На 2-м
шаге игроки переходят в состояния у2=^(х1, yi} 2), хг = и(х1,		уг,
2) = u(xlf v(JCX, yv 2), 2) и т. д. На к-ьл. шаге игроки 1 и 2 переходят из
состояний хк_и yk-i в состояния yk=v(xk.i, ук-и к), хк=и{хк-и		Ук,

k) = u(xk-i, v(xk-i, Ук-i, к), к). Таким образом, каждой ситуации (м(), «(•)) однозначно соответствуют траектории игроков 1 и 2: х=(х0, ...

„., xN) и у=(у0, .... yN), следовательно, и выигрыш К(и(), v()=F(x, у), определяемый по формуле (2.1).

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

241

позиций (хр, j'o) и продолжительности N, поэтому будем обозначать ее через Г (х0, у0, N). Для дальнейшего исследования каждую игру Г(х0, у0, N) удобно отнести к семейству игр Г (х, у, Т), зависящих от параметров л:, у, Т.

2.2. Справедлив следующий результат, являющийся обобщением теоремы п. 2.1 гл. IV для конечных игр с полной информацией.

Теорема. В игре Г(х0, у0, N) существует ситуация равновесия
в чистых стратегиях и значение игры V(x0, y0, N) удовлетворяет
рекуррентному соотношению
V{xQ, y0, A:)=max {f(x0, y0), max min V(x, у, k-1)},	(2.2)
уеГУо xeUXi)

k=l,...,N;V(x,y,0)=f(x,y).

Доказательство проведем методом индукции по числу шагов игры. Пусть N=1. Определим стратегии «*(•), «*(•) игроков в игре Г(х0, j'o, 1) следующим образом:

min f{x, y)=f(u* (х0, у, 1), у), ye УУо;

«о*

если max min f(x, y)=f(u* (x0, у*, 1), у*), то v* (x0, y0, l)=j>*. Тогда

УеУу, xeVxa

К(и*(•), v*())=max{f(x0, y0), max min f{x, у)}

yeVy<> xeUXo

и для любых стратегий и (•), v (•) игроков в игре Г (х0, у0, 1) справед­ ливы соотношения

*(«*(.), .(.))<*(«*(•), v*QHK(u(.), •*(.))•

Тем самым утверждение теоремы справедливо при N= 1. Предположим теперь, что утверждение теоремы справедливо

при N^n и докажем ее для N=n+1, т. е. для игры Г(х0, у0, п+1). Рассмотрим семейство игр Г(х, у, и), xeUx„, уеУУо. Обозначим

через ujy(), vlyi) ситуацию равновесия в игре Г(х, у, и). Тогда

•£("£У(-)> *ху(У)~ V(x' У> и)> гДе У(х> У- п) определено соотношениями (2.2). Используя непрерывность функции f(x, у) и лемму п. 2.1, нетрудно доказать непрерывность функции V(x, у, п) по х, у.

Определим стратегии й" (•), v" (•) игроков в игре Г(х0, j'o, и + 1) следующим образом:

min V(x, у, п)= F(w"+1 (х0, у, 1), у, п), уе УУ{);

*eUx0

если max min V{x, у, и)= К(й"+1 (х0, у, 1), у, и), то v"+ (x0, у0, 1)=у,

У*Ууа **VXa

для хфх0, уфу0 функции vn+ (х, у, 1) и ы"+ (х, у, 1) определим произвольно:

242

un+l(., *)=й;1Л(., к-\),к=2,...,«+1,

«Я + '(Д)=<,1 Г-.А:-1)Д=2) ...,и+1.

Здесь л^ 6 UXo, y16 F>0 — позиции, которые реализовались после 1-го шага в игре Г(х0, у0, п+1). По построению,

К(й"+1 (•), vn+l())=max{/(x0, y0), max min V(x, у, и)}. (2.3)

Фиксируем произвольную стратегию м(.) игрока 1 в игре Г(х0, у0,

п+1). Пусть и(х0, у, 1)=х1г где j>=»,,+l (д:0, у0, 1), и ы^(-) — сужение стратегии ц() на игру Г (л:, у, п), хе UX(>, ye Vyo.

Справедливы следующие соотношения:
К(й"+1 (•), Z"+1 ( Ж max{f(x0, y0), V(xlt у, и)} =
=max{f(x0, y0), K(unxJ(), <*())}<
<max{Ax0,>;0), K(uxj(.), ^ (•))} = *(«(•), " + 1 Q) .	(2-4)
Аналогично доказывается неравенство
K(un+l (.), S"+l 0)>*(5"+ l (•), •(•))	<2-5)

для любой стратегии «(•) игрока 2 в игре Г(х0, у0, л+1). Из
соотношений (2.3) — (2.5) следует справедливость утверждения те­
оремы для N=n+1.	Тем самым доказательство теоремы по индук­
ции закончено.	_

Рассмотрим теперь игру Г(х0, у0, N), которая отличается от игры Г(х0, у0, N) тем,_что в ней сообщает свой выбор игрок 1. Таким образом, в игре Г (х0, у0 N) на каждом шаге к игрок 2 кроме состояний л*_1, ук-\ и шага к знает состояние хке UXk_v выбранное

игроком /. Игрок 1 на каждом шаге к знает лишь х*-ь ук-и Аналогично, теореме п. 2.5 можно показать, что в игре Т(х0, у0, N) существует ситуация равновесия в чистых стратегияхи значение игры V (х0, у0, N) удовлетворяет рекуррентному уравнению

"Р(*о> Уо- k)=max{f(x0, y0), min max V(x, у, k-l)},

_ **ихаУеУУа

k=l,...,N,V(x,y,0)=f(x,y). (2.6)

2.3. Рассмотрим игры Г'(д;0, у0, N) и Г' (х0, у0, N), которые отличаются от игр Г(х0, у0, N) и Г(х0, у0, N) соответственно лишь видом функции выигрыша. Предположим, что в этих играх выиг­ рыш игрока 2 равен расстоянию между ним и игроком 1 на послед-

243

нем шаге игры, т. е. р (%, yN). Тогда утверждение теоремы п. 2.2 и ее следствие сохраняют силу и вместо рекуррентных уравнений (2.2), (2.6) справедливы уравнения

V'{x, у, fc)=max min V'(xf, у',		к-I),
/eVy	x-<=Ux
k = l,...,N,V'(x,y,0)=p(x,y);			(2.7)
V'{x, y, A;)=min max V'(xf, y',		k-l),
3ieUx	/eVy
k=l, ..., N, V'(x. у, 0)=p(x,		у)	(2.8)

Пример З. Рассмотрим дискретную игру преследования, в кото­ рой множества Ux представляют собой круги радиуса а с центром

в точке х, а множества Vy — круги радиуса /? с центром в точке

у(а>Р). Это соответствует игре, в которой игрок 2 (убегающий) перемещается на плоскости со скоростью, не превосходящей /?, а игрок 1 (преследователь) — со скоростью, не превосходящей а. Скорость преследователя превосходит скорость убегающего, и иг­ рок 1 ходит вторым. Игра такого типа называется дискретной игрой «простое преследование» с дискриминацией убегающего игрока. Игра продолжается N шагов, и выигрыш игрока 2 равен расстоя­ нию между игроками на последнем шаге.

Найдем значение игры и оптимальные стратегии игроков, ис­ пользуя функциональное уравнение (2.7).

Имеем

V{x, у, l)=max min p (х', / ) .

(2.9)

/еГу x!eUx

Так как Ux и V, — круги с центрами в х и у и радиусами а и /?, то, если Ux-=iVy, имеем V(x, у, 1)=0, если же Uxj>Vy, то V(x, у, 1)=

р{х, y)+fl — a=p(x,	y) — (a—pr) (см. пример 8 п. 2.6 гл. П). Таким
образом,
ГО, если Ux-=>Vy, т. е. р(х,		у)-(а~Р)<:0,
У[рС>У' )	\р(х,у)-(а-Р),еслиихфУу,
или, что то же самое,
V(x, у, 1)=тах[0, р{х, у)-(а-/?)].			(2.10)
Докажем, применив индукцию по числу шагов к, что имеет
место следующая формула:
V(x, у, Jt)=max[0, p(x, y)-k(a~fi)],		k^2.	(2.11)

Пусть (2.11) выполнено при к=т—\. Покажем, что формула спра­ ведлива для к=т. Воспользовавшись уравнением (2.7) и соотноше-

244

ниями (2.9), (2.10), получим

V{x, у, m)=max min V(x', у', /я—1) =

=max min {max [0, p (x', y') — {m — 1) (a - /?)]} =

=max[0, max min {p(x', /)}-(>"— 1) («—/01=

y'sVy xfeUx

=max [0, max {0, p (x, y) - (a - 0)} - (m -1) (a -ft)]=
=max[0, p(x,	y)~m(a~P)],
что и требовалось доказать.	у0)-т(а-р),	т.	е.	р(х0.у0)-
Если V(x0, у0, т)=р(х0,
—т(а—р)>0, то оптимальная	стратегия	игрока	2 диктует ему

выбирать на к-ъл шаге игры точку ук пересечения линии центров хк_и

yk-i с границей Vyk_v наиболее удаленную от x*_i. Здесь хк-и yk-.i — позиции игроков после (к— 1)-го шага, к=1, ..., N. Опти­

мальная стратегия игрока 1 диктует ему на к-м шаге игры выбирать точку из множества UXk_v наиболее близкую к точке ук. Если оба игрока действуют оптимально, то последовательность выбранных

точек х0, xv	.... xN, y0, ylt...,	yN лежит на прямой, проходящей через
х0, у0. Если	V(x0, y0, т)=0, то оптимальная стратегия игрока
2 произвольна, а игрока		1 — та же. При этом после некоторого

шага к выполняется равенство max min р(х, у)=0, поэтому, н&чя-

уеГУк xeUXk

ная с (к+ 1)-го шага, выбор игрока 1 повторяет выбор игрока 2.

§3. СУЩЕСТВОВАНИЕ СИТУАЦИЙ г-РАВНОВЕСИЯ

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

ПРОДОЛЖИТЕЛЬНОСТЬЮ

3.1. В данном параграфе будет доказано существование ситу­ аций е-равновесия в дифференциальных играх преследования с пред­ писанной продолжительностью в классе кусочно-программных стратегий, определенных в п. 1.6. Рассмотрим подробно случай, когда выигрыш игрока Е — расстояние р (х (7), у (7)) в последний момент игры Т.

Пусть динамика игры задается следующими дифференциальны­ ми уравнениями:

для P:x=f(x,	и);	(3.1)
для E:y=g (у, v).		(3.2)
Здесь х (/), у (t)elf, и (t)eU, v (t)eV,	где U, V — компактные мно-

245

жества евклидовых пространств R и R соответственно, te[0, со). Пусть выполнены все требования п. 16.

Определение. Обозначим через С'Р (х0) множество точек xsR",

для которых существует измеримое программное управление u(t)eU, переводящее точку х0 в х за время t, т. е. x(t0) = x0,

х (t0+t)=x. Множество С'Р (х0) называется множеством достижи­ мости игрока Р из начального состояния х0 за время t.

Аналогично определяется множество достижимости С'Е(уо) иг­ рока Е за время t из начального состояния у0.

Предположим, что функции /, g таковы, что множества до­ стижимости С'р (х0), С'Е {уо) игроков Р и Е соответственно удовлет­ воряют следующим условиям:

1) С'р (х0), С'Е (у0) определены при всяких х0, y0^Rn, t0, te[0, со)

(t0 ^ t) и являются компактными множествами пространства R";

2)отображение С'Р (х0) непрерывно по совокупности аргументов

вметрике Хаусдорфа, т. е. для любых е>0, х0еЛ", te[0, со) суще­

ствует такое <5>0, что если \t—t'\<5, р (х0, х'0)<8, то р* (С.рХ0), С'Р (х0))<8. То же выполняется для С'Е (у0).

Напомним, что метрика Хаусдорфа р* в пространстве компакт­ ных подмножеств R" задается так:

р* (А, В) = шах (р' (А, В), р' (В, А)), р' {A, £)=max p (а. В)

аеА

и р {a, i?)=min р (а, Ь), где р — стандартная метрика в R".

ЬвВ

Теорему существования будем доказывать для игры преследова­ ния Г (х0, >>о, Т) с предписанной продолжительностью, где х0,

y0eRn — начальные позиции игроков Р и Е соответственно, а Г — продолжительность игры. Игра Г (х0, у0, Т) протекает следующим образом. Игроки Р я Е в момент времени /0 = 0 начинают переме­ щаться из позиций х0, уо в соответствии с выбранными кусочнопрограммными стратегиями. В момент времени t=T игра закан­ чивается, при этом игрок Е получает от игрока Р выигрыш, равный р (х (7), у (7)) (см. п. 1.8). В каждый момент времени te[0, 7] игры

246

Г (х0, уа, Т) обоим игрокам известны момент времени t, своя позиция и позиция противника. Обозначим через Р (х0, t0, t) (Е (уп, t0, 0) множество траекторий системы (3.1) ((3.2)), исходящих из

точки х0 (уо) и определенных на интервале [/„, t].

3.2. Фиксируем некоторое натуральное и > 1 . Положим <$=Г/2"

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

Г(х0, jo, Т) игры Г? (х0, уо, Т), i = 1, 2, 3.

Игра Г* (х0, уо, Т) протекает следующим образом. На 1-м шаге игрок Е, находясь в позиции у0, выбирает ух из множества СЕ (у0), а игрок Р, находясь в позиции х0 и зная выбор ух игрока Е на этом

шаге, выбирает точку хх е Ср		(х0). На к-м шаге, к=2,		3, ..., 2", игрок
Е, зная позицию игрока		Р xk_xeCP{xk_-i)	и свою позицию
Ук-1еСв(Ук-г), выбирает	точку Ук^СЕ{ук-\).		Игрок	Р, зная х*-ь
Ук-и Ук, выбирает хкеСР	(x*_i). На 2"-м шаге игра			заканчивается,

и игрок Е получает выигрыш, равный р (х (Т), у (7)), где л; {Т) — х„,

У(Т)=у2„.

Отметим, что выбор игроками на к-ъл шаге точек хк, ук из

множеств достижимости Ср (xk_t), CE {ук-\) можно трактовать как выбор ими соответствующих траекторий из множеств Р (хк-и (к—1)8, к§), Е (ук_х, (к—1)6, к5), оканчивающихся в точках хк, ук в момент t=к8 (или выбор управлений и (•), v (•) на [(к— 1) 8, kb~\, которым эти траектории соответствуют согласно (3.1), (3.2)).

Игра ГI (х0, уо» Т) отличается от игры Г? (х0, у0, Т) тем, что на

к-м шаге игрок Р выбирает хкеС6Р (x*_i), зная хк-и				ук-и а игрок Е,
зная, кроме того, хк, выбирает ykeCsE			(yk-i)-
Игра Г ' (х0, Уо, Т) отличается от игры Г | (х0, у0,				Т) тем, что на
2"-м шаге игрок Р выбирает х2„еСр			(x2„_,), после чего игра закан­
чивается	и	игрок Е получает выигрыш р (х (Г),		у (Т—8)), где
х (T)=Xg.	у	(Т-8)=у2„

3.3. Лемма. В играхTf (x0, yQ, T), / = 1 , 2, 3, существуют ситу­ ации равновесия при всех Ха, уо, Т< оо и значение игры Val Г? (х0, уо, Т) есть непрерывная функция х0, уо е R". При всяком и ^ 0 выполняется неравенство

Val Tf (х0, уо, TKVal Г^ (х0, у0, Т), Т=2"8.

(3.3)

247

Доказательство. Игры r f (х0, Уо, Т), i=\, 2, 3, принадлежат

классу многошаговых игр, определенных в § 2. Существование ситуации равновесия в играх Г f (х0, уо, Т) и непрерывность функций

Val r f (jc0, y0, Т) по х0, у0 непосредственно следует из теоремы п. 2.2 и ее следствия. Для значений игр Tf (х0, у0, T), i—\, 2 справедливы рекуррентные уравнения

Val Г? (хо, Уо, Т)=	max	min	Val r f (x, у,	T-S),
Val Г^ (x0, y0, T) =	min	max	Val Г | (x, у,	T-S)
	xecr(XQ> „ е д			0)=р (x, у).
при начальном условии Val r f		(x, y, 0)=Val Г* (x, у,

Применяя последовательно лемму п. 2.2. гл. I, убедимся в справед­ ливости неравенства (3.3).

3.4. Лемма. При любом целом л>0 справедливы неравенства

Val rf» (х0, у0, 7)<Val rf»+' (x0, y0, T),

Val Г J- (x0, уо, Г » Val rf»+' (х0, у0, Т),

где8к=*Т/2к.

Доказательство. Покажем справедливость первого из нера­ венств. Второе неравенство доказывается аналогично. Во избежание

громоздкости обозначений будем далее полагать С? (уЬ=С*£ (у,),

С* (x,)=Cffr (х,), i=0, 1, ..., 2 " - 1 . Имеем

Val rf»+» (XQ, уо, Т) =					max			min
				,,.Сп+1 <у0)			х,еСл+1 ty
max		min		Val rf»+' (x2, y2,				T-28„+1)^
H+l		Л+1
y2eC frj) x2eC			(*,)
		^	max		max
			Л+1		У2еС	Л+1
		yleC		^(P		<V
min	min			Val rf»+» (x2, y2,				Т-2дя+1)=
л+1	(V x2eC	л+1
x\eC		(xp		Val rf"+' (xu			yu	T-5„).
=	max	min
	n		n

yi*c fr(P xieC (V

Продолжая этот процесс, получим

248

Val Tf»+1 (хо, Уо, 7)2*			max	min ...
			n		л
		y^C	(y,,)	* ] 6 C	(xj
max	min	p (x2„, y2„)=\al			Г?" (x0, Уо, 7")-

nn

3.5.Теорема. При всех х0, yo^R", T<ao справедливо равенство пределов:

lim Val Г?» (хо, уо, Т) = \ш Val Г|- (хо, Уо, Т),

в-»оо	я-»со
Г/це<5л=Г/2л.
Доказательство. Фиксируем некоторое		л>0. Пусть и (•),
v (•) — пара стратегий	в игре Г*" (х0, >0, 7).	Эта пара является

таковой и в игре Г з" (хо, уо, 7). Пусть в ситуации и (•), v (•) реализует­ ся последовательность х0, х{, ..., х2„, у0, уь ..., у2„. Обозначим функции выигрышей в играх Г2" (х0, Уй, Т), Г|" (х0, у0, 7) соответст­

венно через К2 (и (•), v ()) = р (х2„, у2„), Къ (и (•), v ())=р (х2„,		у2„_^.
Тогда
К2 (и (•), * ( ) Х * 3	(« (•), «; ())+р {у2П_{, у2„).
В силу произвольности и (•), v (•) отсюда имеем:
Val Г|» (х„, л ,	Г К Val Г|» (х0, j 0 , 7) +
+ max	max р (у, у1).	(3.4)

Пусть у\п$С6£ (уо), тогда Cj-*" (y\n) с Cj(y0). Запишем неравенст­ во (3.4) для игр с начальным состоянием х0, yfy. Учитывая пре­ дыдущее включение, получим

Val П» (х0, у\\	7)<Val	Г|» (х0, у\», Т) +
+ max	max	p (у, у1).	(3.5)
уеСЦу^	у'еСЬ(у)

Из определения игр Tf" (х0, у0, Т) и Г|"(х0, у0, Т) вытекает равенство

249