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

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

для игрока Е:

ri=s„

s^fa-k^, i=l, 2,

||„||<1;

(8,7)

?.(0) = ??,А(0)=^?,г

(

(0) =

г?,

(0)=sl i=

2; а, 0, fc

£)

fc,>0. (8.8)

Здесь q=(qi, q

) и r=(ri, r

)— местоположение на плоскости

игроков 1 и 2 соответственно; p=(pi,p

)us=(si,

)

— их импульсы;

, к

—

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

ты трения.

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

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

=Vfo.

(Г)-г, (T)]

(Т)-г

(Г)]

В плоскости q=(qi, q

) множество достижимости С\ (q°, p°)

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

Т представляет собой круг (см. упр. 18) радиуса

{T)=j^~

kpT

T-\)

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

a(q

,T) = q°+p

-^-.

Аналогично, множество СЕ(Г°, S°) представляет собой круг

радиуса

ЛИ7)=^(е"*

£Г

+^Г-1)

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

1-е"**"

b(r°,S°, Т) =

Г°+—

5°.

кв

Для величины priq

P°>

r°, s°), определяемой соотношением

(5.1),

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

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

\\q—r\\.

280

Отсюда (см. формулу (2.10)) имеем

Рт

(Я,

Р. г, 5)=шах {0,

\\а (q,

р, Т)-Ь (г, s,

T)\\

-(R

(T)-R

(Г))}

=max

НЛ*-"'"^-"^-?-

•(•

.!±^4t!_,t^±5t!V

(

)

а Р

В частности, условий а>/?, — >— достаточно, чтобы для любых

начальных состояний q, p, r, s нашлось отвечающее им Т, при

котором р

(q,

р, г, s)=0.

Функция р

(q,

р, г, s) удовлетворяет дифференциально-экстре-

мальному уравнению (6.1) в области П =

{(^,

р, г, s, J):p

(q, p,

г,

^)>0}.

Действительно, в области

С1

существуют непрерывные

частные производные

ЗГ*

dqi 8pi дг-, Э«,-

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

Зр v (

? ,

Р 1

Р 1 \

8Т

ы\ \

5г

Р'

' J

-pm&x £ - «i-amin £ — и,=0. (8.11)

И<1 ,„, Ss

|u|<i (., dpi

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

следующими формулами:

«,= -

dPi

,, (8.12)

ару /эру

W \8pJ

/=1,2. (8.13)

VUi/

281

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

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

др Л [dp dp dp Зр \

дТ £[ \8q

дп dp, ds

)

Вычисляя частные производные (8.10), убеждаемся, что функция

Рт (Я> Р>

> •?)

в области 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 и начальное

местоположение у

убегающего Е. При /<<<Г игрок Р в каждый

момент / знает свое состояние х (t), время t и состояние у (t

— I)

игрока Е в момент /—/. Игрок Е в каждый момент времени t знает

свое состояние у (/), состояние противника х (/) и время t. Его

выигрыш равен расстоянию между игроками в момент времени Т,

выигрыш игрока Р равен выигрышу Е с обратным знаком (игра

антагонистическая). Обозначим эту игру Г (х

уо,

Т).

Определение. Под

кусочно-программной

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

v ()

игрока

будем понимать пару

{т, Ь), где т —разбиение

отрезка

времени

[О, 7]

конечным

числом точек 0^ti<...<t

=T и

—

отоб-

ражение,

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

(t,)

ставит

соот-

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

v (<)

игрока

Enpute[t

до-

определение. Под

кусочно-программной

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

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

произвольное

разбиение отрезка времени [0, 7] конечным числом точек

0^t\<t'

<...<t'

=T,

а —

отображение,

которое

каждому состоя-

ннчо

(*1)> У

{u~h> t't при /<f) ставит в

соответствие

отрезок

измеримого программного управления

и (/)

игрока

Р при te[t'

i+i

Для f',</

отображение

а каждому

состоянию

х (/',), у

, t\ ставит

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

и (/) игрока Р при

te[t'u 'i+i)-

Множества всех кусочно-программных чистых стратегий игро-

ков Р и Е будем обозначать соответственно через Р и Е.

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

x=f(x,u),

usl/cR?, xeR",

y=g

(У.

v), veVcR

, yeR". (9.1)

Полагаем выполненными все условия, обеспечивающие существова-

ние и единственность решения системы (9.1) для любой пары изме-

римых программных управлений и

(i),

v (i) при заданных начальных

условиях

Хо,

Уо-

Это гарантирует существование единственного ре-

шения системы (9.1) в случае использования игроками Р и Е кусоч-

но-программных стратегий 'и QeP,

()еЕ при заданных началь-

ных условиях х

Уо-

Таким образом, в любой ситуации (ы (•), v (•))

при заданных начальных условиях х

, у

функция выигрыша игрока

283

Е определяется однозначно

(*о,

у* и О, v ()) = р (х (7), у (7)), (9.2)

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

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

9.3.

Можно на простейших примерах показать, что в рассмат-

риваемой игре Г (х

, у

Т)

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

всех чисел е>0. Поэтому для построения ситуаций равновесия

воспользуемся подходом, предложенным Ф. Нейманом и О. Мор-

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

ей [47]. Расширим пространства стратегий игроков Р и Е до так

называемых

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

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

управления на каждом шаге.

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

для Р\х=и, ||и||<а,

для E:y=v, ||«Kl, (9.3)

a>p>0, x.yeR

, u.veR

Выигрыш игрока Е равен р (х (7), у (7)), где х (t), у (t) — реше-

ние системы (9.3) при начальных условиях х (t

)=x

, у (t

)=y

. Иг-

рок Р в течение игры знает лишь начальное состояние у

против-

ника, а игрок Е имеет полную информацию о состоянии игрока

Р(1=Т).

Пусть v (х, у, t) — некоторая кусочно-программная стратегия

игрока Е. Для каждой стратегии v существует стратегия и (х, t)

игрока Р, использующая только информацию о начальном положе-

нии игрока Е, своем текущем положении и времени, прошедшем

с момента начала игры, гарантирующая выигрыш р (х (7), у (7))<е

для 7>р (jc

)1(а—Р).

Действительно, пусть и* (х, у, t) — страте-

гия игрока Р в игре с полной информацией, имеющая следующую

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

t„

осуществляется погонное пресле-

дование игрока Е, а при *„ < /< Г точка х (t) сохраняется в некоторой

е-окрестности убегающей точки. Такая стратегия в игре с полной

информацией может быть легкоописана аналитически (см. пример

4 п. 8.1). Построим траектории х

(t),

у (/) движения игроков в ситу-

ации

(и*

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

уо>

Для этого

достаточно проинтегрировать систему

х=и* (х, у, t), х (t

)=x

y=Z (x, у, t), у (h)=y

. (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), х (t

)=x

(9.6)

независимо от движения игрока Е. Пусть х (/) — траектория, полу-

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

точких (Г) иу

и направим движение игрока Епо прямой [х (7),>>

]

в направлении от точки х (Г) с максимальной скоростью. Очевид-

но,

что такое движение игрока Е обеспечивает расстояние между

ним и точкой х (Т) большее или равное /?Г. Обозначим построен-

ную таким образ_ом стратегию игрока Е через 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<t

<...<t

=Tи

d-отображение,

ставящее

в со-

285

ответствие состоянию

х (f

;

), у

(t,

—

t),

t, при

состоянию

х (/,),

Уо,

tj при

t,^l

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

ц, (•),

сосредоточенное

на

конечном

числе измеримых

программных управлений

и (t) при t e

Аналогично под

СКПСП

игрока

будем понимать пару

v ()={о,

с},

где а —

произвольное разбиение отрезка времени

[О,

конечным

числом точек

ti<t

--<t,= Tu

с-отображение,

ставящее

соот-

ветствие состоянию х (О, у (t\), t\

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

v, (•),

сосредоточенное

на

конечном

числе измеримых

программных

управлений

v (t)

при

f e[f„

1+!

СКПСП игроковр и Е будем обозна-

чать соответственно через F и

ИГ

(ср.

со «стратегиями поведения» п.

8.3 гл. IV).

Каждая пара СКПСП ц (•), v (•) индуцирует распределение веро-

ятностей на пространстве траекторий х (/), х (0)=JC

; у (f), у (0)=j>

Поэтому под выигрышем R

(х

;

(•), v (•)) в СКПСП будем

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

(х

; и (•), v (•)),

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

рые индуцируются СКПСП ц (•), v (•). Определив пространства

стратегий Р, Ё и выигрыш К, мы определили смешанное расшире-

ние Г (х

уо,

Т) игры Г (х

уо,

Т).

9.5.

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

(x) и С/

(у)

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

достижимости игроков Р и Е из начальных состояний х и у в мо-

мент времени Т, а через

СЕ

(у)

— выпуклую оболочку множества

С"Е

(у).

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

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

(у, Т)= min max p (£, п).

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

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

содержащей множество С\

(у).

Отсюда получаем, что эта точка

единственна. В то же время существуют по крайней мере две точки

касания множества

СЕ

(у) с минимальной содержащей его сферой,

которые совпадают с точками у.

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

) игрока Е при

0</<Г. При перемещении игрока Е вдоль этой траектории вели-

чина у (у (/),

Т—

0 изменяется, меняется также и точка у. Пусть

у (t) — траектория точки у, соответствующая траектории у (/). На-

зовем точку MeCl~'

(уо) центром

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

если

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

у'еС^Чуо)

286

9.6. Рассмотрим вспомогательную одновременную антагони-

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

СЕ

(у).

Преследователь выбирает некоторую точку

£еС

(у),

а убе-

гающий — точку

e С|

(у).

Выбор совершается одновременно, и иг-

рок Р при выборе точки £ не знает выбора

г\

игрока Е, и наоборот.

Игрок Е получает выигрыш р

(<!;,

п). Обозначим значение этой игры

через V

(у,

Т), чтобы подчеркнуть зависимость значения игры от

параметров у и Т, которые определяют множества стратегий

\ (у)

СЕ

(у) игроков Р и Е. Игру в нормальной форме запишем следу-

ющим образом:

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

Множество стратегий минимизирующего игрока Р выпукло,

функция р(у', у") также выпукла по своим аргументам и непрерыв-

на. Для таких игр мы можем применить теорему п. 5.5 гл. П.

Поэтому в игре Г (у, Т) существует ситуация равновесия в смешан-

ных стратегиях. Оптимальная стратегия игрока Р чистая, а оп-

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

ятность не более чем (л+1) точке из множества С

(у), причем

(у,

Т)=у (у, Т). Оптимальная стратегия игрока Р в игре Г (у, Т)

заключается в выборе центра минимальной сферы у, содержащей

множество

СЕ

(у)-

Оптимальная стратегия игрока Е предписывает

положительные вероятности не более чем (л+1) точке из точек

касания указанной сферы с множеством С

(у) (здесь л — размер-

ность пространства х, у). Значение игры равно радиусу этой сферы

(см.

пример 11п. 5.5 гл. II).

9.7. Рассмотрим одновременную игру Г (М, /), где М — центр

преследования. Обозначим через у

(М), ...,y

+i Щ) точки из множе-

ства

С'Е

(М), которые входят в спектр оптимальной смешанной

стратегии игрока Е в игре Г (М, /), а через у (М) — оптимальную

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

Определение. Траектория у* (t) называется условно-опти-

мальной,

если

у* (0)=у

,у* (Т—1)=М,у* (Т)=у, (А/) для

некоторого

i из

чисел

1, ..., л+1.

Для каждого i может существовать несколько условно-опти-

мальных траекторий игрока Е.

Теорема. Пусть T^l и для

любого

числа е>0 игрок Р к момен-

ту времени Т может

гарантировать

в-встречу с центром у (7)

минимальной сферы,

содержащей

множество С'

(у

(Т—1)).

Тогда

игра

Г (х

Уо,

Т)

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

у (М,

I),

е-оптимальная

стратегия

игрока Р чистая и

совпадает

с любой его

стратегией,

гарантиру-

ющей

е/2-встречу

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

смешанная:

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

0< /<

Т—1

он должен перемещаться

в точку М

по любой условно-оптимальной траектории

у* (t) и

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

...,р

п+1

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

Ев

игре

287

Г (М, /))

выбрать

одну

из

условно-оптимальных

траекторий,

перево-

дящих точку у* (Т—[)=М в точки y

(М), г'=1, ..., и+1, входящие

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

смешанной

стратегии

игрока

игре

Г (М, I).

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

ы,

(•) v, (•) указанные в те-

ореме стратегии, оптимальность которых требуется доказать. Для

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

следующих соотношений:

R(х<ь

Уо\

(•), v, ())

е>К(х

Уо,

и. (•), v, (•))>

>R(х

;

и. (•), v

(.))-в,ц

()еР, v (•)бЁ; (9.8)

Urn R

(х

;

и, (•), v.

(.))=y

(M,

I).

(9.9)

«-•о

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

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

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

(х

уо,

и (•), v, ())+в>£(хо,

уо,

и. (•), v, (•)).

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

JC*

(/) траекторию преследователя в ситуации

(и.

О, v, ()). Тогда

(х

уо,

и, (•), v.

(•))="£

р,р (х* (Т), у,

(М))-

(9.10)

(-1

Пусть R — радиус минимальной сферы, содержащей множество

С'

(М), т. е. R=y (M, I). Тогда R-s/2^p(x* (T), у,

(M))^R+Е/2

для всех i=l, ... , и +

поскольку точка х* (Г) принадлежит

е/2-окрестности точки у (А/). Так как £

Pi—1>

РС&§,

TO из

формулы

(9.10) получаем

Л-е/2<£(х

уо,

и. (), v

ОХЛ+8/2, (9.11)

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

Пусть состояния х (Т), у

(Г—

реализовались в ситуации (и, (•),

())

Q (•) — вероятностная мера, индуцированная на множестве

СЕ(У(Т—

[)).

Из оптимальности смешанной стратегии р=(р\, ...,

П+1

)

в игре Г {М,

имеем

*="l р,р

(У

(М),

У>

(М))>7

(У

{Т-Г),

Г) =

=УеЛГ

(у (Т-[),[)> J p(y\y(T-f)],y)dQ, (9.12)

288

где у

[у

(Т—

/)]

— центр минимальной сферы, содержащей множест-

во С

(у (Т-1)).

Однако р (х (Т), у \у (Т-1)])^Е/2, поэтому при уеС'

(у (Т-1))

имеем

р (х (Т), у)^е/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,

;

(•),

v (•)). (9.15)

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

Теорема доказана.

При Т<1 решение игры существенно не отличается от случая

7>/

и теорема сохраняет силу, если вместо

С'

(у

С'

(у

)

у (М, I),

(Т—1)

рассматривать соответственно С

(у

у (М, Т), у

При /-*0 диаметр множества

С'

(М)

стремится к нулю, что,

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

тельной игры Г (М,

I).

Однако значение этой вспомогательной игры

равно значению

(х

Уо,

Т) игры преследования с задержкой

информации Г (х

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

информации). Смешанная оптимальная стратегия игрока Е в Г (М,

I),

сосредоточивающая свою массу на не более чем л+1 точке из

С'

(М), в пределе сосредоточивает всю массу в одной точке М, т. е.

превращается в чистую стратегию. Это вполне согласуется с тем,

что при 1-*0 игра Г (х

, у

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

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

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

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

Пусть время Т удовлетворяет условию Т>р (х

)/(а

— р) +

Множество достижимости

С'

(уо)

С'

(у

)

и совпадает с кругом

радиуса

/?/

с центром у

. Значение игры Г (у,

равно радиусу круга

С'

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

Так как величина V

(у,

I) в данном случае не зависит от у, то

любая точка множества

(у

)

может быть центром преследова-

ния М. Оптимальная стратегия игрока Р в игре Г (у,

заключается

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

289