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

для игрока Е:
ri=s„
s^fa-k^,	i=l,	2, ||„||<1;			(8,7)
?.(0) = ??,А(0)=^?,г((0) = г?,
st	(0)=sl	i= 1, 2; а, 0,	fc£)	fc,>0.	(8.8)
Здесь q=(qi, q2) и r=(ri, r2)— местоположение на плоскости
игроков 1 и 2 соответственно; p=(pi,p2)us=(si,				s2) — их импульсы;

кр, кЕ — некоторые константы, интерпретируемые как коэффициен­

ты трения.

Выигрыш игрока Е полагается равным

H(q(T),r(T))=\\q(T)-r(T)\\ =

=Vfo. (Г)-г, (T)]2 + [q2 (Т)-г2 (Г)]2.

В плоскости q=(qi, q2) множество достижимости С\ (q°, p°)

игрока Р из начальных состояний р (0)=р°, q (0)=q° за время Т представляет собой круг (см. упр. 18) радиуса

RP{T)=j^~kpT+kpT-\)
с центром в точке	Кр
a(q0,p0,T) =		q°+po1-^-.
		кр
Аналогично, множество	СЕ(Г°,	S°) представляет собой круг
радиуса

ЛИ7)=^(е"* £ Г +^Г - 1)

с центром в точке

1-е"**"

b(r°,S°, Т) = Г°+—

5°.

кв

Для величины priq0, P°> r°, s°), определяемой соотношением (5.1), в данной дифференциальной игре выполняется равенство

PT(q°,P°. r°. s°)= max

min \\q—r\\.

280

Отсюда (см. формулу (2.10)) имеем
Рт (Я, Р. г, 5)=шах {0, \\а (q, р, Т)-Ь (г, s, T)\\ -(Rp (T)-RE			(Г))} =
=max НЛ*-"'"^-"^-?-
	.!±^4t!_,t^±5t!V		(8.9)
• ( •	к2	к1
	а	Р
В частности, условий а>/?, — >— достаточно, чтобы для любых
	кр	kg

начальных состояний q, p, r, s нашлось отвечающее им Т, при котором рт (q, р, г, s)=0.

Функция рт (q, р, г, s) удовлетворяет дифференциально-экстре­ мальному уравнению (6.1) в области П = {(^, р, г, s, J):pT(q, p,

г, ^)>0}. Действительно, в области С1 существуют непрерывные частные производные

ЗГ* dqi 8pi дг-, Э«,-

Уравнение (6.1) принимает вид

Зр v (8?	,дР	8Р 1	дР 1	\
8Т ы\ \8*	5г<	дР'	8s'	J
-pm&x £ - «i-amin			£ — и,=0.		(8.11)
И<1	,„, Sst	|u|<i	(., dpi

Здесь экстремумы достигаются на управлениях ы, v, определяемых
следующими формулами:
«,= -	dPi	,,	(8.12)
	ару	/эру
	W \8pJ
	dp
v t = -		/=1,2.	(8.13)

VUi/ +UJ

281

Подставляя эти управления в (8.11), получим нелинейное уравнение в частных производных первого порядка

др	Л [dp	dp	dp	Зр	\
дТ	£[ \8qt	дп	dp,	dst	)

Вычисляя частные производные (8.10), убеждаемся, что функция Рт (Я> Р> r> •?) в области Q удовлетворяет уравнению (8.14).

Отметим, что величина рт(я°, Р°, r°, s°) является значением

дифференциальной игры (8.6)—(8.8), а управления, определяемые соотношениями (8.12), (8.13),'оптимальные в области Q.

Из формул (8.12), (8.13), (8.9) находим

Tj-qj+Si		р,
Ц,= ,	"*		К = ,		Щ=Щ, 1=1,2 . (8.15)
а ,	1-е	-к£Г	1-е	-крТ
		•"		У у

В ситуации й, v направление действия силы каждого из игроков параллельно линии, соединяющей центры кругов достижимости (как это следует из формулы (8.15)), и остается постоянным, по­ скольку в этой ситуации центры кругов достижимости перемещают­ ся вдоль прямой линии.

§ 9. ИГРЫ ПРЕСЛЕДОВАНИЯ С ЗАДЕРЖКОЙ ИНФОРМАЦИИ У ПРЕСЛЕДОВАТЕЛЯ

9.1. Ранее в этой главе рассматривались конфликтные управля­ емые процессы, в которых каждый из участников (игроков) имел полную информацию, т. е. в каждый текущий момент игры Р (£) знал свое состояние х (t) [у (/)] и состояние противника у (/) [х (t)]. Были получены теоремы о существовании ситуаций е-равновесия в чистых стратегиях в таких играх и проиллюстрированы различные методы построения движения. Это оказалось возможным, посколь­ ку дифференциальные игры с полной информацией представляют собой предельный случай многошаговых игр с полной информаци­ ей, когда промежуток времени между двумя последовательными ходами стремится к нулю. Иначе обстоит дело с дифференциаль­ ными играми с неполной информацией, где применение смешанных стратегий играет существенную роль. Не останавливаясь на анализе всей проблемы, рассмотрим только случай игры преследования

282

с предписанной продолжительностью, терминальным выигрышем и задержкой поступления информации игроку Р о фазовом состоя­ нии игрока Е на время />0.

9.2. Пусть задано некоторое число />0, называемое временем задержки информации. При 0</</ преследователь Р в каждый момент времени t знает свое состояние х (;), время t и начальное местоположение у0 убегающего Е. При /<<<Г игрок Р в каждый

момент / знает свое состояние х (t), время t и состояние у (t — I) игрока Е в момент /—/. Игрок Е в каждый момент времени t знает свое состояние у (/), состояние противника х (/) и время t. Его выигрыш равен расстоянию между игроками в момент времени Т, выигрыш игрока Р равен выигрышу Е с обратным знаком (игра антагонистическая). Обозначим эту игру Г (х0, уо, Т).

Определение. Под кусочно-программной чистой стратегией v () игрока Е будем понимать пару {т, Ь), где т —разбиение отрезка времени [О, 7] конечным числом точек 0^ti<...<tk=T и Ь — отоб­ ражение, которое каждому состоянию х (tt), у (t,) tt ставит в соот­ ветствие отрезок измеримого программного управления v (<) игрока

Enpute[th	д о ­
определение. Под кусочно-программной чистой стратегией

и (•) игрока Р будем понимать пару {а, а}, где а — произвольное

разбиение отрезка	времени [0,	7] конечным числом точек
0^t\<t'li<...<t'1=T,	а — отображение, которое каждому состоя-
ннчо х(*1)> У {u~h> t't при /<f)		ставит в соответствие отрезок

измеримого программного управления и (/) игрока Р при te[t'u t'i+i). Для f',</ отображение а каждому состоянию х (/',), у0, t\ ставит

в соответствие отрезок измеримого управления и (/) игрока Р при

te[t'u 'i+i)-
Множества всех кусочно-программных чистых стратегий игро­
ков Р и Е будем обозначать соответственно через Р и Е.
Уравнения движения имеют вид
x=f(x,u), usl/cR?,	xeR",
y=g (У. v), veVcR9,	yeR".	(9.1)

Полагаем выполненными все условия, обеспечивающие существова­ ние и единственность решения системы (9.1) для любой пары изме­ римых программных управлений и (i), v (i) при заданных начальных условиях Хо, Уо- Это гарантирует существование единственного ре­ шения системы (9.1) в случае использования игроками Р и Е кусоч­ но-программных стратегий 'и QeP, v ()еЕ при заданных началь­ ных условиях х0, Уо- Таким образом, в любой ситуации (ы (•), v (•))

при заданных начальных условиях х0, у0 функция выигрыша игрока

283

Е определяется однозначно
К (*о, у* и О, v ()) = р (х (7), у (7)),	(9.2)

где х (f), у (0 — решение системы (9.1) при начальных условиях х0, у0 в ситуации (м (•), v (•)), ар — евклидово расстояние.

9.3. Можно на простейших примерах показать, что в рассмат­ риваемой игре Г (х0, уй, Т) ситуации е-равновесия существуют не для

всех чисел е>0. Поэтому для построения ситуаций равновесия воспользуемся подходом, предложенным Ф. Нейманом и О. Моргенштерном для конечных позиционных игр с неполной информаци­ ей [47]. Расширим пространства стратегий игроков Р и Е до так

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

(СКПСП), которые предполагают возможность случайного выбора управления на каждом шаге.

Пример 6. Уравнения движения имеют вид

для Р\х=и,	||и||<а,
для E:y=v,	||«Kl,	(9.3)
a>p>0,	x.yeR1,	u.veR2.

Выигрыш игрока Е равен р (х (7), у (7)), где х (t), у (t) — реше­ ние системы (9.3) при начальных условиях х (tQ)=x0, у (t0)=y0. Иг­ рок Р в течение игры знает лишь начальное состояние у0 против­ ника, а игрок Е имеет полную информацию о состоянии игрока

Р(1=Т).

Пусть v (х, у, t) — некоторая кусочно-программная стратегия игрока Е. Для каждой стратегии v существует стратегия и (х, t) игрока Р, использующая только информацию о начальном положе­ нии игрока Е, своем текущем положении и времени, прошедшем с момента начала игры, гарантирующая выигрыш р (х (7), у (7))<е для 7>р (jc0, у0)1(а—Р). Действительно, пусть и* (х, у, t) — страте­ гия игрока Р в игре с полной информацией, имеющая следующую структуру: до момента встречи t„ осуществляется погонное пресле­ дование игрока Е, а при *„ < /< Г точка х (t) сохраняется в некоторой

е-окрестности убегающей точки. Такая стратегия в игре с полной информацией может быть легкоописана аналитически (см. пример 4 п. 8.1). Построим траектории х (t), у (/) движения игроков в ситу­ ации (и* (х, у, t), v (x, у, t)) из начальных состояний х0, уо> Для этого

достаточно проинтегрировать систему
х=и* (х, у, t), х (t0)=xQ,
y=Z (x, у, t), у (h)=yu.	(9.4)

284

По построению р (х (Т), у (Г))<£. Пусть теперь		й {t) = u* (х (/),
у (t), t), и хотя стратегия и* (х, у, /), использующая для выработки
управления информацию о положении Е, недопустима, стратегия
й (/) является допустимой, поскольку использует лишь информацию
о времени, прошедшем с момента начала игры и о начальном
состоянии игрока Е. Очевидно, что в ситуациях (й (t), v (х, у, t))
и (и* (х, y,J), v (х, у, t)) траектории игроков совпадают, поскольку
стратегия v (x, у, t) одинаково реагирует как на стратегию и* (х,
у,	/), так и на стратегию и (/) выбором управления v (х (/), у (/),J*)).
у,	Таким образом, мы показали, что для каждой стратегии v (х,
	t) существует программное управление й (/), являющееся допусти­
мой стратегией в игре_ с неполной информацией,		и такое, что
Р (* (^L У (У))<е, где х (f), у (t) — соответствующие траектории.
Выбор v (х, у, t) произволен, поэтому отсюда следует, что
	шр1ш>(х(Г),;и(Г)) = 0,	(9.5)

где supinf берется по множествам стратегии игроков в игре с непо­ лной информацией.

Вместе с тем для любой стратегии и (х, г) игрока Р можно построить такую стратегию v (х, у, t) игрока Е, что в ситуации (и (х, г), v (х, у, /)) выигрыш р игрока Е превзойдет рТ. Действительно, пусть м (х, /) — некоторая стратегия игрока Р. Так как его движение не зависит от у (f), то траектория движения игрока Р может быть получена интегрированием системы

х=й (х, t), х (t0)=xu

(9.6)

независимо от движения игрока Е. Пусть х (/) — траектория, полу­ чившаяся в результате интегрирования системы (9.6). Соединим точких (Г) иу0 и направим движение игрока Епо прямой [х (7),>>0]

в направлении от точки х (Г) с максимальной скоростью. Очевид­ но, что такое движение игрока Е обеспечивает расстояние между ним и точкой х (Т) большее или равное /?Г. Обозначим построен­ ную таким образ_ом стратегию игрока Е через v (t). Тогда получим, что в ситуации (й (х, t), v (?)) выигрыш игрока Е больше или равен величине рТ. Отсюда следует, что

infsupp(x(r),>>(r))^pT,

(9.7)

где inf sup берется по множествам стратегий игроков в игре с непо­ лной информацией.

Из (9.5) и (9.7) следует, что значение игры в классе чистых стратегий в рассматриваемой игре не существует.

9.4. Определение. Под смешанной кусочно-программной стра­ тегией поведения (СКПСП) игрока Р будем понимать пару ft () = {т, d}, где х — произвольное разбиение отрезка времени [0, 7] конечным числом точек 0=ti<t2<...<tk=Tи d-отображение, ставящее в со-

285

ответствие состоянию х (f;), у (t, — t), t, при tt>l и состоянию х (/,), Уо, tj при t,^l вероятностное распределение ц, (•), сосредоточенное на конечном числе измеримых программных управлений и (t) при t e [th

Аналогично под СКПСП игрока Е будем понимать пару v ()={о, с}, где а — произвольное разбиение отрезка времени [О, 7] конечным числом точек 0 = ti<t2--<t,= Tu с-отображение, ставящее в соот­ ветствие состоянию х (О, у (t\), t\ вероятностное распределение v, (•), сосредоточенное на конечном числе измеримых программных управлений v (t) при f e[f„ *1+!). СКПСП игроковр и Е будем обозна­ чать соответственно через F и ИГ (ср. со «стратегиями поведения» п. 8.3 гл. IV).

Каждая пара СКПСП ц (•), v (•) индуцирует распределение веро­ ятностей на пространстве траекторий х (/), х (0)=JC0; у (f), у (0)=j>0.

Поэтому под выигрышем R (х0, у0; /* (•), v (•)) в СКПСП будем понимать математическое ожидание выигрыша К (х0, у0; и (•), v (•)),

усредненное по распределениям на пространствах траекторий, кото­ рые индуцируются СКПСП ц (•), v (•). Определив пространства стратегий Р, Ё и выигрыш К, мы определили смешанное расшире­ ние Г (х0, уо, Т) игры Г (х0, уо, Т).

9.5. Обозначим через CTf (x) и С / (у) соответственно множества достижимости игроков Р и Е из начальных состояний х и у в мо­ мент времени Т, а через СЕ (у) — выпуклую оболочку множества С"Е (у). Предположим, что множества достижимости компактны, и введем в рассмотрение величину

у (у, Т)= min max	p (£, п).
Пусть у (у, Т)=р(у, у), где уеСЦу),	уеСЦу). Из определения

точки у следует, что она является центром минимальной сферы, содержащей множество С\ (у). Отсюда получаем, что эта точка единственна. В то же время существуют по крайней мере две точки касания множества СЕ (у) с минимальной содержащей его сферой, которые совпадают с точками у.

Пусть у (t) — некоторая траектория (у (0)=у0) игрока Е при

0</<Г. При перемещении игрока Е вдоль этой траектории вели­ чина у (у (/), Т— 0 изменяется, меняется также и точка у. Пусть у (t) — траектория точки у, соответствующая траектории у (/). На­ зовем точку MeCl~' (уо) центром преследования, если

у (А/, /)= max у (у', I).

у'еС^Чуо)

286

9.6. Рассмотрим вспомогательную одновременную антагони­ стическую игру преследования на выпуклой оболочке_ множества СЕ (у). Преследователь выбирает некоторую точку £еСЕ (у), а убе­ гающий — точку w e С | (у). Выбор совершается одновременно, и иг­ рок Р при выборе точки £ не знает выбора г\ игрока Е, и наоборот. Игрок Е получает выигрыш р (<!;, п). Обозначим значение этой игры через V (у, Т), чтобы подчеркнуть зависимость значения игры от параметров у и Т, которые определяют множества стратегий С \ (у) и СЕ (у) игроков Р и Е. Игру в нормальной форме запишем следу­ ющим образом:

г(у,7)=<С5(у),с5оо,р(у',у')>.

Множество стратегий минимизирующего игрока Р выпукло, функция р(у', у") также выпукла по своим аргументам и непрерыв­ на. Для таких игр мы можем применить теорему п. 5.5 гл. П. Поэтому в игре Г (у, Т) существует ситуация равновесия в смешан­ ных стратегиях. Оптимальная стратегия игрока Р чистая, а оп­ тимальная стратегия игрока Е предписывает положительную веро­ ятность не более чем (л+1) точке из множества СТЕ(у), причем V (у, Т)=у (у, Т). Оптимальная стратегия игрока Р в игре Г (у, Т) заключается в выборе центра минимальной сферы у, содержащей множество СЕ (у)- Оптимальная стратегия игрока Е предписывает положительные вероятности не более чем (л+1) точке из точек касания указанной сферы с множеством СЕ (у) (здесь л — размер­ ность пространства х, у). Значение игры равно радиусу этой сферы (см. пример 11п. 5.5 гл. II).

9.7. Рассмотрим одновременную игру Г (М, /), где М — центр преследования. Обозначим через уу (М), ...,yn+i Щ) точки из множе­ ства С'Е (М), которые входят в спектр оптимальной смешанной стратегии игрока Е в игре Г (М, /), а через у (М) — оптимальную

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

Определение. Траектория у* (t) называется условно-опти­ мальной, если у* (0)=у0,у* (Т—1)=М,у* (Т)=у, (А/) для некоторого

i из чисел 1, ..., л+1.

Для каждого i может существовать несколько условно-опти­ мальных траекторий игрока Е.

Теорема. Пусть T^l и для любого числа е>0 игрок Р к момен­ ту времени Т может гарантировать в-встречу с центром у (7) минимальной сферы, содержащей множество С'Е(у (Т—1)). Тогда

игра Г (х0, Уо, Т) имеет значение у (М, I), е-оптимальная стратегия

игрока Р чистая и совпадает с любой его стратегией, гарантиру­ ющей е/2-встречу с точкой у (Т). Оптимальная стратегия игрока Е смешанная: в течение времени 0< /< Т—1 он должен перемещаться в точку М по любой условно-оптимальной траектории у* (t) и далее с вероятностямири ...,рп+1 {оптимальная стратегия игрока Ев игре

287

Г (М, /)) выбрать одну из условно-оптимальных траекторий, перево­ дящих точку у* (Т—[)=М в точки yt (М), г'=1, ..., и+1, входящие

в спектр оптимальной смешанной стратегии игрока Е в игре Г (М, I).

Доказательство. Обозначим через ы, (•) v, (•) указанные в те­ ореме стратегии, оптимальность которых требуется доказать. Для доказательства теоремы достаточно убедиться в справедливости следующих соотношений:

R(х<ь Уо\ II (•), v, ()) + е>К(х0, Уо, и. (•), v, (•))>

>R(х0, у0; и. (•), v (.))-в,ц ()еР, v (•)бЁ;	(9.8)
Urn R (х0, уй; и, (•), v. (.))=y (M, I).	(9.9)
«-•о

Левая часть неравенства (9.8) следует из определения стратегии и, (•), в силу которого для любой кусочно-программной стратегии

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

R (х0, уо, и (•), v, ())+в>£(хо, уо, и. (•), v, (•)).

Обозначим через JC* (/) траекторию преследователя в ситуации (и. О, v, ()). Тогда

К (х0, уо, и, (•), v. (•))="£ р,р (х* (Т), у, (М))-			(9.10)
(-1
Пусть R — радиус минимальной сферы, содержащей множество
С'Е(М), т. е. R=y (M, I). Тогда R-s/2^p(x*	(T), у,	(M))^R+Е/2
для всех i=l, ... , и + 1, поскольку точка	х* (Г)	принадлежит

е/2-окрестности точки у (А/). Так как £ Pi—1> РС&§, TO и з формулы

(9.10) получаем
Л-е/2<£(х0 , уо, и. (), v# ОХЛ+8/2,	(9.11)

что доказывает (9.9).

Пусть состояния х (Т), у (Г— I) реализовались в ситуации (и, (•),

v ()) и Q (•) — вероятностная мера, индуцированная на множестве СЕ(У(Т— [)). Из оптимальности смешанной стратегии р=(р\, ...,

рП+1) в игре Г {М, I) имеем

* = " l р,р (У (М), У> (М))>7 (У {Т-Г), Г) =

=УеЛГ (у (Т-[),[)>

J p(y\y(T-f)],y)dQ,

(9.12)

288

где у [у (Т— /)] — центр минимальной сферы, содержащей множест­
во С'Е	(у (Т-1)).			поэтому при уеС'Е (у	(Т-1))
Однако р (х (Т), у \у (Т-1)])^Е/2,
имеем	р (х (Т), у)^е/2 + р (у \у (Т-1)], y)^R + e/2.				(9.13)
Из неравенства (9.11)—(9.13) вытекает, что
	&(хо,Уо, и. (),v,Q)>		J	p(x(T),y)dQ-B,	(9.14)
однако
	J	p (x (T), y) dQ=R		(xo, y0; ue (•), v (•)).	(9.15)

Из формул (9.14) и (9.15) получаем правую часть неравенства (9.8). Теорема доказана.

При Т<1 решение игры существенно не отличается от случая 7>/ и теорема сохраняет силу, если вместо С'Е (у0), С'Е (у0) у (М, I),

у (Т—1) рассматривать соответственно СЕ (у0), СЕ (у0), у (М, Т), у0.

При /-*0 диаметр множества С'Е(М) стремится к нулю, что, в свою очередь, вызывает стремление к нулю значения вспомога­ тельной игры Г (М, I). Однако значение этой вспомогательной игры равно значению V, (х0, Уо, Т) игры преследования с задержкой

информации Г (х0, jo, Т) (здесь индекс / означает время задержки

информации). Смешанная оптимальная стратегия игрока Е в Г (М, I), сосредоточивающая свою массу на не более чем л+1 точке из С'Е (М), в пределе сосредоточивает всю массу в одной точке М, т. е. превращается в чистую стратегию. Это вполне согласуется с тем, что при 1-*0 игра Г (х0, у0, Т) превращается в игру с полной

информацией.

Пример 7. Уравнения движения имеют вид

х=и, ||ы||<а; y=v, ||«||<j8, а>р\ x.yeR2.

Пусть время Т удовлетворяет условию Т>р (х0, у0)/(а — р) + 1. Множество достижимости С'Е (уо) = С'Е (у0) и совпадает с кругом радиуса /?/ с центром у0. Значение игры Г (у, I) равно радиусу круга

С'Е(у), т. е. V(y,l) = pl.

Так как величина V (у, I) в данном случае не зависит от у, то любая точка множества СТЕ~1 (у0) может быть центром преследова­ ния М. Оптимальная стратегия игрока Р в игре Г (у, I) заключается

в выборе точки у, а оптимальная стратегия игрока Е — смешанная

289