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

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

системы

(1.7) из

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

, у

. Стратегии и*(х, у, i),

(х,

у, 0 называются оптимальными стратегиями игроков Р и Е.

Установим различие понятий ситуации равновесия в кусочно-

программных и синтезирующих стратегиях. Заметим, что опреде-

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

У, 0> v(x, у, i) невозможно из-за непрямоугольности пространства

ситуаций, т. е. в синтезирующих стратегиях невозможно потребо-

вать выполнения неравенства (1.13) для всех стратегий

(х,

у,

t),

(х,

у,

i), поскольку некоторые пары (и*, v), (и, v*) могут не быть

допустимыми (система уравнений (1.7) в соответствующей ситуации

может не иметь решения вообще или не иметь единственного реше-

ния).

В дальнейшем, если специально не будет оговорено, во всех

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

гий.

Прежде чем перейти к доказательству существования ситуации

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

тельный класс многошаговых игр с полной информацией.

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

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

2.1.

Рассмотрим класс многошаговых игр с полной информаци-

ей,

представляющих собой обобщение игр с полной информацией из

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

R".

Будем обозначать через х е

местоположение (позицию) игрока

а через yeR

— местоположение игрока 2. Пусть для каждых

xeR",

yeR" определены множества U

, V

соответственно, которые

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

странства R". Игра начинается из позиции х

, у

. На 1-м шаге

игроки 1 я 2 выбирают точки х

С/

Хо

и у

При этом выбор

игрока 2 сообщается игроку 1 до выбора им точки

В точках

игроки

и 2 выбирают точки х

и выбор игрока

2 сообщается игроку / перед выбором им точки х

и т. д. На

к-м шаге в позициях х

игроки выбирают

и выбор игрока 2 сообщается игроку / перед выбором им точки

Процесс заканчивается на JV-м шаге выбором x

[/,„_,,

и переходом в состояние x

, y

Семейства множеств U

, V

, xeR

,yeR

предполагаются непре-

рывными в метрике Хаусдорфа по х, у. Это означает, что для

любого

Б>0

найдется такое д>0, что при

|JC—лс

|<^

(\у—у

\<&)

240

(U^=>U

(£/,).=>£/,„;

(V,X=V,.

(V,)

*V„.

Здесь

(V,)

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

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

Лемма.

Пусть

/(х

, /) —

непрерывная

функция на

декартовом

произведении

x V

Тогда если семейства

}, \V

} —

непрерывны

по

Хаусдорфу по

х, у, то

функционалы

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

/eV

x!eV

(x,

y)=min

min/(f,

*eV

?eVy

непрерывны_по

х, у.

Пусть x=(x

, .... x

) и y=(y

, .... y

) — траектории игроков

1 и 2 соответственно, реализовавшиеся в процессе игры. Выигры-

шем игрока 2 является величина

max f(x

)=F(x,y), (2.1)

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

равен

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

Будем предполагать, что данная игра с полной информацией,

т. е. в каждый момент времени (на каждом шаге) игрокам известны

позиции х

, у к и момент времени к+l, а игроку 1, кроме того,

известен выбор

k+i

игрока 2 в этот момент.

Стратегиями игрока 1 являются всевозможные функции

и(х, у, t) такие, что и(х

, к)е

Стратегиями игрока 2 —

всевозможные функции v(x, у, t) такие, что v(x

-\, Ук-и

k)eV

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

смешанных).

Пусть игроки 1 и 2 применяют чистые стратегии и(х, у, t), v(x, у,

t).

В ситуации

(и (•),

v (•)) игра происходит следующим образом. На

1-м шаге игрок 2 из состояния у

переходит в состояние

(х

, у

1) и игрок 1 — из состояния х

в состояние х

и(х

, j>i \) = и(х

v(x

, у

, 1), 1) (поскольку игрок 1 знает выбор игрока 2). На 2-м

шаге игроки переходят в состояния

=^(х1,

2), х

и(х

, у

2) = u(x

v(JC

2),

2) и т. д. На

к-ьл.

шаге игроки

и 2 переходят из

состояний х

yk-i в состояния y

=v(x

.i, ук-и к), х

=и{х

-и

Ук,

u(x

-i, v(x

-i,

Ук-i,

к), к). Таким образом, каждой ситуации (м(),

«(•)) однозначно соответствуют траектории игроков 1 и 2: х=(х

, ...

„., x

) и у=(у

....

), следовательно, и выигрыш К(и(), v()=F(x,

у),

определяемый по формуле (2.1).

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

241

позиций

(хр, j'o)

и продолжительности N, поэтому будем обозначать

ее через Г (х

, у

, N). Для дальнейшего исследования каждую игру

Г(х

, у

, N) удобно отнести к семейству игр Г

(х,

у, Т), зависящих от

параметров л:, у, Т.

2.2.

Справедлив следующий результат, являющийся обобщением

теоремы п. 2.1 гл. IV для конечных игр с полной информацией.

Теорема. В игре Г(х

, у

, N)

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

в чистых стратегиях и

значение

игры V(x

, y

, N)

удовлетворяет

рекуррентному соотношению

V{x

, y

, A:)=max {f(x

, y

), max min V(x, у,

k-1)},

(2.2)

уеГ

Уо

xeU

Xi)

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

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

игры. Пусть N=1. Определим стратегии «*(•), «*(•) игроков в игре

Г(х

j'o,

1) следующим образом:

min f{x, y)=f(u* (х

, у, 1), у), ye

Уо

;

«о*

если max min f(x, y)=f(u* (x

, у*,

1),

у*), то

, y

, l)=j>*. Тогда

еУ

у,

xeV

К(и*(•),

v*())=max{f(x

, y

), max min f{x, у)}

yeV

y<>

xeU

и для любых стратегий

и (•),

v (•)

игроков в игре

(х

, у

, 1) справед-

ливы соотношения

*(«*(.),

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

•*(.))•

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

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

при N^n и докажем ее для

N=n+1,

т. е. для игры Г(х

, у

, п+1).

Рассмотрим семейство игр Г(х, у, и),

xeU

„,

уеУ

Уо

Обозначим

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

•£("£У(-)>

*ху(У)~

У>

У(

У-

) определено соотношениями

(2.2).

Используя непрерывность функции f(x, у) и лемму п. 2.1,

нетрудно доказать непрерывность функции V(x, у, п) по х, у.

Определим стратегии й" (•), v" (•) игроков в игре Г(х

, j'o, и +

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

min V(x, у, п)= F(w"

(х

, у, 1), у, п), уе

У{)

;

если max min V{x, у, и)=

К(й"

(х

, у,

1),

у, и), то v"

, у

, 1)=у,

У*Уу

**V

для хфх

, уфу

функции v

(х, у, 1) и ы"

(х, у, 1) определим

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

242

n+l

(.,

*)=й;

1Л

(., к-\),к=2,...,«+1,

Я+

'(Д)=<,

Г-.А:-1)Д=2

)

...,и+1.

Здесь

л^

— позиции, которые реализовались после 1-го

шага в игре Г(х

, у

, п+1). По построению,

К(й"

(•),

n+l

())=max{/(x

, y

), max min V(x, у,

и)}.

(2.3)

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

игре Г(х

п+1).

Пусть и(х

, у, 1)=х

1г

где j>=»

,,+l

(д:

, 1), и ы^(-) — сужение

стратегии ц() на игру Г

(л:,

у, п),

хе

X(>

Справедливы следующие соотношения:

К(й"

(•),

(Ж max{f(x

, y

), V(x

у,

и)}

=max{f(x

, y

), K(u

(), <*())}<

<max{Ax

,>;

), K(u

(.),

(•))}

*(«(•),

Q).

(2-4)

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

K(u

n+l

(.), S"

0)>*(5"

(•),

•(•))

<2-5)

для любой стратегии «(•) игрока

2 в

игре Г(х

л+1).

Из

соотношений (2.3) — (2.5) следует справедливость утверждения те-

оремы для

N=n+1.

Тем самым доказательство теоремы по индук-

ции закончено.

Рассмотрим теперь игру Г(х

N), которая отличается

от

игры Г(х

, N)

тем,_что

ней сообщает свой выбор игрок

Таким образом, в игре Г (х

N) на каждом шаге к игрок 2 кроме

состояний

л*_1,

ук-\ и шага

знает состояние х

выбранное

игроком

Игрок

1 на

каждом шаге

знает лишь х*-ь

-и

Аналогично, теореме п. 2.5 можно показать, что в

игре

Т(х

, у

, N)

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

чистых стратегиях

значение

игры V (х

, у

, N)

удовлетворяет рекуррентному уравнению

"Р(*о>

Уо-

k)=max{f(x

, y

), min max

V(x,

у,

k-l)},

УеУ

Уа

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

(2.6)

2.3.

Рассмотрим игры Г'(д;

, N) и

Г' (х

N), которые

отличаются от игр Г(х

, у

, N) и Г(х

, у

, N) соответственно лишь

видом функции выигрыша. Предположим, что

этих играх выиг-

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

243

нем шаге игры, т. е. р (%,

Тогда утверждение теоремы п. 2.2 и ее

следствие сохраняют силу и вместо рекуррентных уравнений (2.2),

(2.6) справедливы уравнения

V'{x, у, fc)=max min

V'(xf,

у', к-I),

/eV

x-<=U

l,...,N,V'(x,y,0)=p(x,y); (2.7)

V'{x, y, A;)=min max

V'(xf,

y', k-l),

3ieU

/eV

k=l, ..., N, V'(x. у, 0)=p(x, у) (2.8)

Пример З. Рассмотрим дискретную игру преследования, в кото-

рой множества U

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

в точке х, а множества

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

у(а>Р).

Это соответствует игре, в которой игрок 2 (убегающий)

перемещается на плоскости со скоростью, не превосходящей /?,

а игрок 1 (преследователь) — со скоростью, не превосходящей а.

Скорость преследователя превосходит скорость убегающего, и иг-

рок

ходит

вторым.

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

«простое преследование» с дискриминацией убегающего игрока.

Игра продолжается N шагов, и выигрыш игрока 2 равен расстоя-

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

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

пользуя функциональное уравнение (2.7).

Имеем

V{x, у, l)=max min

(х',

/). (2.9)

/еГ

x!eU

Так как U

и V, — круги с центрами в х и у и радиусами а и

/?,

то,

если

-=iVy,

имеем V(x, у, 1)=0, если же

j>V

то V(x, у, 1)=

р{х, y)+fl — a=p(x, y) —

(a—p

)

(см. пример 8 п. 2.6 гл. П). Таким

образом,

ГО,

если

-=>V

т. е. р(х, у)-(а~Р)<

У[рС>У

)

\р(х,у)-(а-Р),еслии

фУ

или, что то же самое,

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,

(x',

y')

— {m — 1)

(a -

/?)]}

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

(«—/01=

y'sVy

xfeU

=max

[0,

max

{0,

(x,

- (a -

0)}

- (m -1) (a -

ft)]

=max[0, p(x, y)~m(a~P)],

что и требовалось доказать.

Если V(x

, у

, т)=р(х

)-т(а-р),

т. е. р(х

.у

—т(а—р)>0, то оптимальная стратегия игрока 2 диктует ему

выбирать на

к-ъл

шаге игры точку у

пересечения линии центров х

-i

с границей

наиболее удаленную от x*_i. Здесь х

-.i

— позиции игроков после

(к—

1)-го шага, к=1, ..., N. Опти-

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

диктует ему на к-м шаге игры выбирать

точку из множества

наиболее близкую к точке у

. Если оба

игрока действуют оптимально, то последовательность выбранных

точек х

, x

.... x

, y

...,

лежит на прямой, проходящей через

. Если V(x

, y

, т)=0, то оптимальная стратегия игрока

2 произвольна, а игрока 1 — та же. При этом после некоторого

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

н&чя-

уеГ

Ук

xeU

ная с (к+ 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,

(t)eV,

где U, V

—

компактные мно-

245

жества евклидовых пространств R и R соответственно, te[0, со).

Пусть выполнены все требования п. 16.

Определение. Обозначим через С'

(х

) множество точек xsR",

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

u(t)eU,

переводящее точку х

в х за время t, т. е. x(t

)

х (t

+t)=x. Множество С'

(х

) называется множеством достижи-

мости игрока Р из начального состояния х

за время t.

Аналогично определяется множество достижимости

С'

(уо)

иг-

рока Е за время t из начального состояния у

Предположим, что функции /, g таковы, что множества до-

стижимости С'р (х

), С'

{уо)

игроков Р и Е соответственно удовлет-

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

1) С'р (х

), С'

(у

) определены при всяких х

, te[0, со)

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

2) отображение С'

(х

) непрерывно по совокупности аргументов

в метрике Хаусдорфа, т. е. для любых е>0, х

еЛ", te[0, со) суще-

ствует такое <5>0, что если \t—t'\<5, р (х

, х'

)<8, то р* (С.рХ

С'Р

(х

))<8. То же выполняется для С'

(у

Напомним, что метрика Хаусдорфа р* в пространстве компакт-

ных подмножеств R" задается так:

р*

(А, В)

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

аеА

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

ЬвВ

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

ния Г (х

, >>о, Т) с предписанной продолжительностью, где х

— начальные позиции игроков Р и Е соответственно, а Г —

продолжительность игры. Игра Г (х

, у

, Т) протекает следующим

образом. Игроки Р я Е в момент времени

начинают переме-

щаться из позиций х

, уо в соответствии с выбранными кусочно-

программными стратегиями. В момент времени t=T игра закан-

чивается, при этом игрок Е получает от игрока Р выигрыш, равный

р (х (7), у (7)) (см. п. 1.8). В каждый момент времени te[0, 7] игры

246

Г (х

, у

, Т) обоим игрокам известны момент времени t, своя

позиция и позиция противника. Обозначим через Р (х

, t

, t) (Е (у

, 0) множество траекторий системы (3.1) ((3.2)), исходящих из

точки х

(уо)

и определенных на интервале [/„, t].

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

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

Г (х

, jo, Т) игры Г? (х

, уо, Т), i =

2, 3.

Игра Г* (х

, уо, Т) протекает следующим образом. На 1-м шаге

игрок Е, находясь в позиции у

, выбирает у

из множества С

(у

а игрок Р, находясь в позиции х

и зная выбор у

игрока Е на этом

шаге, выбирает точку х

е С

(х

). На к-м шаге, к=2, 3, ..., 2", игрок

Е, зная позицию игрока Р x

_-i) и свою позицию

Ук-1еСв(Ук-г), выбирает точку Ук^С

{у

-\). Игрок Р, зная х*-ь

Ук-и У к, выбирает х

еС

(x*_i). На 2"-м шаге игра заканчивается,

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

{Т) —

х„,

(Т)=у

„.

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

, у

из

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

{у

-\) можно трактовать как

выбор ими соответствующих траекторий из множеств Р (х

(к—1)8, к§), Е (у

, (к—1)6, к5), оканчивающихся в точках х

в момент t=к8 (или выбор управлений и (•), v (•) на

[(к—

kb~\,

которым эти траектории соответствуют согласно (3.1), (3.2)).

Игра ГI (х

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

, у

, Т) тем, что на

к-м шаге игрок Р выбирает х

еС

(x*_i), зная х

а игрок Е,

зная, кроме того, х

, выбирает y

-i)-

Игра Г' (х

Уо,

Т) отличается от игры Г| (х

, у

, Т) тем, что на

2"-м шаге игрок Р выбирает х

„еС

„_,), после чего игра закан-

чивается и игрок Е получает выигрыш р (х (Г), у (Т—8)), где

х (T)=Xg. у (Т-8)=у

„

3.3.

Лемма. В играхTf (x

, y

, T), /=1, 2, 3, существуют ситу-

ации

равновесия при всех

Ха,

уо,

Т<

оо

и значение игры Val Г? (х

уо,

Т)

есть непрерывная функция х

, у

R".

При всяком

выполняется

неравенство

Val Tf (х

, уо, TKVal Г^ (х

, у

, Т), Т=2"8. (3.3)

247

Доказательство. Игры rf (х

Уо,

Т), i=\, 2, 3, принадлежат

классу многошаговых игр, определенных в § 2. Существование

ситуации равновесия в играх Г

(х

уо,

Т) и непрерывность функций

Val rf (jc

, y

, Т) по х

, у

непосредственно следует из теоремы п. 2.2

и ее следствия. Для значений игр Tf (х

, у

, T), i—\, 2 справедливы

рекуррентные уравнения

Val Г? (хо,

Уо,

Т)= max min Val rf (x, у, T-S),

Val Г^ (x

, y

, T) = min max Val Г| (x, у, T-S)

(

XQ>

„ед

при начальном условии Val rf (x, y, 0)=Val Г* (x, у, 0)=р (x, у).

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

ливости неравенства (3.3).

3.4.

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

Val rf» (х

, у

, 7)<Val rf»+' (x

, y

, T),

Val Г

J-

, уо, Г» Val rf»+' (х

, у

, Т),

где8

=*Т/2

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

венств. Второе неравенство доказывается аналогично. Во избежание

громоздкости обозначений будем далее полагать

С?

(уЬ=С*£ (у,),

С*

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

Val rf»+»

(XQ,

уо, Т) = max min

п+1 л+1

,,.С <у

) х,еС ty

max min Val rf»+' (x

, y

, T-28„+

H+l Л+1

frj) x

eC (*,)

^ max max

Л+1 Л+1

^(P

еС

min min Val rf»+» (x

, y

Т-2д

я+1

л+1 л+1

eC (

= max min Val rf"+' (x

T-5„).

n n

eC (

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

248

Val Tf»+

(хо,

Уо,

7)2* max min ...

n л

y^C

(y,,) *

C (xj

max min p (x

„, y

„)=\al Г?" (x

Уо,

7")-

n n

3.5.

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

, yo^R", T<ao

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

пределов:

lim Val Г?»

(хо,

уо,

Т)

\ш Val Г|-

(хо,

Уо,

Т),

в-»оо

я-»со

Г/

це<5

=Г/2

Доказательство. Фиксируем некоторое л>0. Пусть и (•),

v (•) — пара стратегий в игре Г*" (х

, >

, 7). Эта пара является

таковой и в игре Г

з"

(хо,

уо,

7). Пусть в ситуации и (•), v (•) реализует-

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

, х{, ..., х

„, у

, у

..., у

„. Обозначим

функции выигрышей в играх Г

" (х

Уй,

Т), Г|" (х

, у

, 7) соответст-

венно через К

(и (•), v ()) = р (х

„,

„),

(и (•), v ())=р (х

„,

„_^.

Тогда

(и (•), * ()Х*

(« (•),

«;

())+р

{у

2П

{

„).

В силу произвольности и (•), v (•) отсюда имеем:

Val Г|»

(х„,

л, ГК Val Г|» (х

7) +

+ max max р (у, у

). (3.4)

Пусть у\

$С

£ (у

о),

тогда Cj

*" (y\

) с Cj(y

). Запишем неравенст-

во (3.4) для игр с начальным состоянием х

, yfy. Учитывая пре-

дыдущее включение, получим

Val П» (х

, у\\ 7)<Val Г|» (х

, у\», Т) +

+ max max p (у, у

). (3.5)

уеСЦу^ у'еСЬ(у)

Из определения игр Tf" (х

, у

, Т) и Г|"(х

, у

, Т) вытекает

равенство

249