Тынянский Н.Т., Жуковский В.И. Дифференциальные игры с ненулевой суммой (кооперативный вариант)

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

^{1,

2,...,-V},

игроки которых'сами могут образовать коали-

цию.

Таким образом, изменение позиции {t,x} в кооперативной

дифференциальной игре происходит в соответствии с системой:

x = f(t, х, и), x(t

) = x

{и@Щ,

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

/(«) = {/,(«),•,.., /ЛГ(Й)}.

Именно наличие векторной функции выигрыша и указанные

свойства коалиций всех игроков и вносит большинство трудно-

стей в изучение кооперативных дифференциальных игр. Однако

несколько,облегчает решение то обстоятельство, что игроки час-

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

щих воздействий. В защиту этого Лейтмэн приводит [278]

следующие доводы: во-первых, «так как игроки коопе-

рируются, 'то им нет причины скрывать свои личные решения»,

во-вторых, «задача отыскания оптимального по Парето (см. § 1)

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

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

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

управление дает тот же результат, что и оптимальное позицион-

ное управление». В приведенном выше описании задача отыска-

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

•много общего с теорией оптимального управления с «вектор-

ным целевым функционалом. Поэтому перспективное развитие

последней, на наш взгляд, связано и с развитием теории коопе-

ративных дифференциальных игр (этот факт игнорируется в

большинстве работ по векторной оптимизации динамических

-систем),

В заключение заметим, что часто вызывает возражение раз-

нообразие понятий оптимальности, используемых в кооператив-

ных дифференциальных играх. Можно понять желание исполь-

зовать такой критерий оптимальности, который бы приводил к

одному, «самому лучшему», решению или к нескольким решени-

ям,

эквивалентным в смысле указанного критерия. Однако ко-

оперативные дифференциальные игры настолько разнообразны

-содержательно и по объему доступной информации, что даже их

классификация представляется нелегкой задачей. Поэтому по-

иск универсальных, "не зависящих от дополнительной информа-

ции, «разумных» решений является, на наш взгляд, бесплодным.

Каждое из приведенных далее в настоящем обзоре понятий

•«компромиссного» решения может служить решением лишь для

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

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

информация в каждой конкретной игре. Попутно отметим:

1) В [21] особое внимание уделяется аксиоматическому под-

ходу в определении решения задачи векторной оптимизации —

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

гому».

2) ,Хо [253] провел классификацию задач векторной опти-

мизации динамических систем в зависимости от следующих фак-

торов: а) для системы (1)—непрерывность, дискретность, сто-

хастичность, наличие запаздывания; б) для функций выигрыша

(4) —две или больше двух; в) количество игроков — один, два

или больше двух; г) доступная информация — наличие или от-

сутствие обратной связи.

- Если брать по одному свойству из а), б), в) и г), то получим;

различные классы задач векторной оптимизации. Такой же под-

ход использует Тралл при классификации простейших диффе-

ренциальных игр (в обзорной статье [350] по новым результа-

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

граммирования).

3) В теории игр принято считать кооперативной игрой — иг-

ру в форме характеристической функции [23]. Приве-

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

связано со стремлением учесть систему (1).

Перейдем к краткому содержанию обзора. Первый из ука-

занных выше подходов («скаляризация критериев») к решеник>

кооперативных дифференциальных игр разобран в § 1—§ 8..

Здесь рассматриваются, в основном, необходимые, а в некоторых

случаях, и достаточные условия существования решения, теоре-

мы существования, свойства решений и выделены некоторые

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

де (например, линейно-квадратичные дифференциальные игры)\

Связь между используемыми в § 1—§ 8 решениями коопера-

тивных дифференциальных игр представлена следующей схемой:

У- оптимальность

(%8,п.83)

Л-

оптимальность Ш

}•

Оптимальность

по

Слвитеру

(§7Г

Слабо

зффектиЬое

решение §6

Оптимальность по Парето

(Я)

Решение Наша

для

ар-

Нитражнои

схемы

Среднеквадратич-

ное решение (§2)

Оптимальные страте-

гии угроз (i3,n.3,jf).

Лексикографически

оптимальное

реше-

ние (§-.-•)

Абсолютно кооператибное решение 1$5)

Собственно

эффтпиЬюе

решениеШ.Ш)

А&г.~л.-отно оптимальное решение (i5,n.5.if

Изложению второго подхода, предложенного Л. А. Петрося-

ном, посвящен § 9. Такой способ отыскивания решения коопера-

тивных дифференциальных игр, по нашему мнению, весьма пер-

спективен и имеет глубокий игровой смысл. В § 9 излагаются

основные результаты Л. А. Петросяна и Н, Н. Данилова, опуб-

ликованные до 1978 г.

Третий подход затрагивается в п. 10.9 и 10.10 из § 10. Ма-

териал десятого параграфа следует рассматривать как попытку

одного из авторов настоящего обзора применить математичес-

кую формализацию дифференциальной игры, предложенную-*

Н. Н. Красовским, к построению некоторых подходов к нахож-

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

В § 11—§ 12 кратко излагаются результаты, касающиеся

следующих разделов теории кооперативных дифференциальных:

игр:

антагонистические игры с векторными функциями выигры-

ша (§ 11) (параграф написан 3. Варга), многошаговые игры

(§ 12, п. 12.1), игры с запаздыванием времени (§ 12, п. 12.2) и

стохастические игры (§ 12, п. 12.3).

Приложения к задачам механики управляемых систем и

экономики отнесены в § 13. И, наконец, в § 14 приведен ряд за-

дач,

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

рии кооперативных дифференциальных игр.

Далее приняты следующие обозначения: ^—-евклидово

^-мерное пространство с нормой j| • ||; векторы (столбцы)»

x = {xi. ...,x

)£R

, и={щ,

...,им),

£R

(m =

'Zm

= {«i, ...>Ш

} (i

eK={h, ..., i

}), F = {F

, ..., F

], Ф=

IV JV

i==l i=-l

=-П-Л-

*-v

"*+-' *" •'

-v)

;

шТ

ИХ

сверху

означает операцию транспонирования; €

—

не принадлежит;

соМ- выпуклая замкнутая оболочка множества М; в случае

скалярной функции W вектор-столбец ^

{~г~~>

•

• •» х

-}"

аналогично определяется --; если векторы /-•={/-•,/

} и

•а/1

а/1 а/1

дх

а/

а/,

_ax, дх

dxj -

а = {а

, ..., a

}>b = {b

..., b

}

означает a

{

>bi (i= 1,..., r); (a, b) — скалярное произведение

векторов; IntA—Л— внутренние точки множества Л.

§ 1. Оптимальность по Парето

Здесь (в п. 1.2) приведены леммы, на основе которых в

п. 1.3 и п. 1.4 формулируются необходимые и достаточные усло-

вия оптимальности по Парето решения игры (1)

—

(4).

В п. 1.3

х = {х

, х

}, то Ц:

.выделены следующие подходы

отысканию необходимых усло-

вий: изопериметрический

(п. а)),

градиентный

(п, в»,

сведение

к линейной связке

(п. г)),

максиминный

(п. д)). В п. 1.4

отдель-

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

случае программных

(п.

а)) и

позиционных

(п. б))

управлений. Теоремам существо-

вания посвящен

п. 1.5,

линейно-квадратичным дифференциаль-

ным играм

—

п.

1.6.

Вопросы, связанные

принципом оптималь-

ности, отнесены

в п. 1.7.

1.1. Определение. Предполагаем,

что

позиция

{t,x}

коопера-

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

возрастанием вре-

мени

Щи, Т],

согласно системе

x=f(t, х, и), x(t

) = x

* (10)

ia[']Q%),

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

i-ro

игрока имеет

вид,

/i(tt[.])--=cDi(7\ „(Г)) + ^(*, Л(7), ti\t\)dt, i = \, ...,N.{11)

.Предполагаем,

что

выполнены ограничения

из п. 2

введения.

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

все N

игроков совместно выбирают набор управ-

ляющих воздействий и—{и\,

..., u

} с

целью достичь

моменту

окончания игры

возможно большего выигрыша

для

каждого

игрока. Пусть

при

выборе набора управляющих воздействий

иг-

роки основываются

на

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

1896 году Парето [311].

литературе встречаются следующие

три определения:

набор управляющих воздействий u

[-,\&U оптимален^по

Па-

рето

для

игры (10)— (11), если

a) система неравенств,

из

которых

по

крайней мере одно

строгое,

1МЛ)>1Ли

1\)> '=--• ....М ' •

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

л ДО;

b) если для любого набора управляющих воздействий иЩ

либо существует индекс /6{Ь

2,...,

N}, такой, что

'/(я

Н)>/у(я['1).

либо выполнены равенства Л(м

Н)—-Л(и[-р- i=l,..., N;

c) если

из

выполнения

для

некоторого набора управляющих

воздействий и\-\6% условия

•..;•

/-(а[.1)>/,(а

М),

i=l,...,N,

следует, что

/|(«[-])=Л(»

[-1). *-=-.,...,#.

Все три определения а), Ь), с) оптимального по Парето на-

бора управляющих воздействий u

[t] эквивалентны; ., причем

иногда используются и другие названия: эффективный по Паре-

то,

эффективный, недоминируемый и неулучшаемый. Нами

приведены все три определения, так как иногда в работах, по-

священных оптимальности по Парето, следуют лишь определе-

нию а), хотя использование Ь) или с) в некоторых случаях на-

много сокращает и упрощает доказательство результатов.

Оптимальным по Парето решениям в играх (10)

—

(11) по-

священы докторские диссертации Ори

[248],

Юричек [259] и

Салама

[329].

В случае антагонистической дифференциальной игры (игры

двух лиц с платой I =

—

) любой набор управляющих

воздействий и

[•]--—{#*

{•], и

\-]} 6%Х% является оптимальным

по Парето решением. Этот же факт справедлив для любой

дифференциальной игры (10)-(11) с постоянной суммой

(2/iH-l)==Const, Yul-ieil).

В.

В. Подиновскчй в [121] ввел понятие внешне

устойчивого множества решений, оптимальных по Парето: мно-

жество оптимальных по Парето наборов управляющих воздейст-

вий 9К называется внешне устойчивым, если для любого набора

управляющих воздействий и\-\&% существует оптимальный по

Парето набор #

[-]{in}9tt такой, что

Л(а

['1)>ЛИ-1)-

h...,N.

Условия внешней устойчивости в случае недифференциаль-

ных игр в [121, § 2.4]. Для дифференциальных игр эти вопросы,

по-видимому, не рассматривались.

Подмножеством оптимальных по Парето решений являются

собственно эффективные решения, введенные в

[236].

Набор

управляющих воздействий u°[t] называется собственно эффек-

тивным (по Джеффри) для игры (10) — (И), если набор u°[t]

является оптимальным по Парето и существует c-=Const>0

•такая, что для всех

2,...,

N и наборов управляющих воз-

действий

и[.]е<Ы,

для которых 1{{и[-])>1

г{№[•]),

при некото-

ром /б{1, 2,.. ., N} выполнено неравенство

Ii(ttl-])-It(tt

l-l)<c(Ij(tt

l\)-Ij(ul-])).

Множество собственно эффективных наборов обозначим ^

В &

не входят оптимальные по Парето наборы u

[t], такие,

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

[t] может быть сделано сколь угодно большим, по сравнению

с уменьшением выигрышей остальных игроков. Сужение мно-

жества № оптимальных по Парето наборов до ^

не столь зна-

чительно. Так, если

y£U—

замкнутому выпуклому множеству в

•R

, а функции Ii(y) непрерывны и вогнуты по у, то

[236]:

7(^

)с/(^>)с77^),

где черта сверху означает замыкание множества. Наборы управ-

2—4150

ляющих воздействий, удовлетворяющие (12) (см. п. 1.2), явля-

ются собственно эффективными для игры (10)

—

(И).

Ряд других понятий решения игры (10)

—

(11), уточняющих

или обобщающих оптимальность по Парето, собран в § 3 гл. VIII

монографии В. В* Хоменюка

[154].

1.2. Леммы. Приведем леммы, которые, в большинстве слу-

чаев,

служат основанием для получения достаточных (§ 1,

п. 1.4) и необходимых (§ 1, п. 1.3) условий оптимальности по Па-

рето.

Заранее оговоримся, что мы не стремились выяснить прео-

ритет авторов приводимых лемм. В круглых скобках лишь по-

мещены «координаты», где можно найти как полное доказатель-

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

личным задачам нелинейного программирования. Леммы 1, 2, 3.

устанавливают достаточные условия.

Лемма 1 ([236]). Если при некоторых

ац

= Const>0 (i =

= l,...,iV)

N N

2ai/i(

H)—- max _,V^H)> 02)

то набор управляющих воздействий u

[t] оптимален, по Парето<

для игры (10)

—

(11).

Доказательство от противного: пусть u

[t] из (12) не опти-

мален по Парето. Тогда существует такой набор управляющих

воздействий u*[t], что Л(и*[-])>Л(ы

'[-]),

i—1,..

.,/V, причем

хотя бы одно неравенство строгое. Умножая каждое £-е из не-

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

2«*л(й*1-])>2^л[а

1-1),

i = l i=-l

что противоречит (12).

На случай неотрицательных ai лемма 1 может быть обобще-

на (Э. Вчлкас [21]) следующим образом:

Если а!>0,..., a

>0, a

m+1

= 0,..., a.v = 0, то положим

(

т т 1

«•[•1:2 Vy

("*!•])-=

max 2°/М*Н) -

/=i -+le^y=i J

для произвольных [xk>0

= m-\-\,.. ,,N) пусть

N N

max 2 M* («*[•]) = 2 M*(a

[-])-

«*[-le^

k-^~r

i k^+i

Тогда и

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

Парето для игры

(10) —

(11).

Лемма 2 ([278]). Если при некоторых ai>0, £=

1,...,А7»

>0, для любого набора

u\t]^u

\t\

(т. е. иЩ^=и

Щ на

подмножестве из \t

Т] ненулевой меры) управляющих воздей-

ствий

JV N

аП

Н)>2

*<«Н). (13)

то набор управляющих воздействий u

[t] оптимален по Парето

для игры (10) — (И).

Доказательство получаем из определения Ь) (стр. 16) опти-

мальности по Парето, так как из (13) следует существование

хотя бы одного индекса /{in}{l, 2,.. .,

/V},

для которого

М"

[-])>/Ди[-]).

Следует отметить, что результаты леммы 2 можно найти в

[74].

Эти леммы показывают, что выбор оптимального по Парето

решения в известном смысле эквивалентен указанию «весов»

для каждого критерия. Леммы позволяют находить оптималь-

ные по Парето наборы м

[/] путем решения задачи оптималь-

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

[126].

Лемма 3 ([122]). Если существуют индекс

/--{1,

2, ..., /V}

и {N—1)—действительное число {гк\кф]\ k=\, 2, . ..,

/V},

такие, что и^Щ будет единственным максимумом /j(«[•]) для

всех u[t], таких, что

Ik(u[-])>r

{кфу,к~\,...,Щ,

то набор управляющих воздействий u

[t] оптимален по Парето

для игры (10) — (11).

Требование единственности сильно ограничивает возможность

использования леммы 3 при построении оптимальных по Парето

управляющих воздействий. Это ограничение снято в следующей

лемме, устанавливающей необходимые и достаточные условия.

Этот результат получен В. В. Подиновским в 1971 г.

[121].

Лемма 4 ([95]). Для того чтобы набор управляющих воз-

действий u

[t] являлся оптимальным по Парето для игры (10)

—

(11),

необходимо и достаточно существование такого /V-вектора

•

г=

-К...,М.

что

max 2Л{«1-1)-=2Л(а

М). (14)

Необходимость. Пусть не существует вектора г, при

котором и

Щ есть решение задачи (14). Тогда найдутся посто-

янные rl = I

[-]) (k =

l,...,N)

такие, что (г^^,...,^})

2-М«*[-])= max

2Л(а[-])>2

аП

1-1).

i = l

Ци[-])>г

i-=l i=-4

Отсюда /i(tt* [-\)>Ii(и

[-\), i=l,.. .,Nf причем хотя бы одно

из неравенств строгое. Получили противоречие, так как и

оптимально по Парето.

Достаточность. Пусть и

—

решение задачи (14), т. е.

существует /V-вектор г такой, что /i(«

[-])>ri

l,...,N)

N JV

и 2 ^г (^ 1*1) =

max

'Sj'iC^l'l)- Пусть к

[^не оптимально по

Парето для игры

(10)

—(11).

Тогда существует набор и*Щ, для

которого выполнена система неравенств, из которых, по край-

ней мере, одно строгое, /*(«*[•])>Л (&"[•]). i = \,..., N. ОТСЮ-

ДА

да I

(u*[-])>r

1,....N,

и 2^(

*1-])>2Л(и

1-]), что

i=l 1=1

противоречит (14).

Необходимые и достаточные условия существования опти-

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

множества {1, 2,.. .,А/} на подмножества и к оптимизации ли-

нейной комбинации функций выигрыша на каждом из подмно-

жеств, получены В. В. Гороховиком [238] (см. также [42]).

Именно, пусть на множестве Uc.R

определены /V функций

/Ц'Й),

..., IN

{и),

и множество Y = {y\y£R

; у<1 (и), аф) стро-

го выпукло сверху, т. е. для любых y

z& и ag(0, 1) сущест-

вует £6У такое, что | >

az-\-(\

—

а)

у, где а > Ь, a, b£R

озна-

чает a

>bi (i=\,...,N) и афЬ. В этом случае точка и

оптимальна по Парето для {Л(я)».

•

.,IN{U)}

тогда и только

тогда, когда существуют упорядоченное разбиение ji,...,?k

(&</V) множества

{1,

.2,.. .,'N} и числа ai>0,

s = \,.. .,k, для которых

)

= maxL

(u),

s£\,...,k,

u£U

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

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

потребовать выполнения условия А из [42]. Это условие А фор-

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

любом ненулевом неотрицательном векторе №R

, множество

точек, на которых линейная функция

Ь,

Х'у

достигает максиму-

ма на У, принадлежит линейному многообразию вида {у

|Уг

С{

для всех £, таких, что ^

.>()},

где

c-i

—Const.

Строгая выпуклость

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

вания Л.

В.

В.'Гороховик отметил, что справедливость достаточности

условий приведенной выше теоремы из [238] доказана в [42]

без предположения о строгой выпуклости сверху для У или

условия

(последние нужны лишь при доказательстве необхо-

димости). Поэтому результат

Э.

Вилкаса (стр.

18)

является

частным случаем достаточной части утверждения из [238] (мно-

жество

{!,...,

Щ разбивается на два подмножества

{!,...,

т}

и {m-+l,...,/V}).

Приведем леммы 5—7, которые доставляют .необходимые

условия оптимальности

по

Парето. Лемма

непосредственно

следует из результата Ю. Б. Гермейера [32].

Лемма

Если набор управляющих воздействий

\t\

оптимален по Парето для игры (10) —(11), причем /i («"[•])>

для всех i

2, ..., N, то

существуют такие ai>0,

i =

...,N,

чт0

i=l

max min ai/i («[•])

min ai/"i(#

[•]).

(15)

«[•Ig<^-=i,...,.v i=i,...,.v

При доказательстве положим ai—-Л//i («"[•]). Согласно опре-

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

ляющих воздействий существует индекс /6{Ь

...,N},

такой,

что

И-1)</у(И

[-1)

а;/

(и[.])<а;/Да

1^)

т1п^Л(и

[.])==1.

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

min а*/; (к[.])< min аТ/

(и

[-]),

откуда, нормализовав а**, получаем (15).

Следует отметить, что лемма

позволяет при формулировке

необходимых условий оптимальности

по

Парето привлечь ре-

зультаты по максиминным (специальным) задачам, полученные

на основе принципа максимума

Л. С.

Понтрягина

[126].

Этот

факт,

сожалению, как правило, остается

стороне

много-

численных работах по оптимизации динамических систем

век-

торным целевым функционалом.

Лемма

([121]). Если набор управляющих воздействий

[t] оптимален по Парето для игры (10)

—

(11), то для каждо-

го индекса

/б{1,...,

iV}

существует N—1 действительное число

Гь.

(k¥=j,

k=l,.

N) такое, что

/,(a»H)

.max/

(a[.I)

при ограничениях

h{u[-\)>r

{k=^j,

k=\,

...,N).

Лемма 7 ([74]). Пусть множество 1(и[-]) = {1\{и[•]),...

...,///(«[•]} выпукло, когда набор управляющих воздействий

и\-\^%, пробегает все допустимые значения. В этом случае,

если it

[t\ оптимально по Парето для игры (10)— (И), то

найдутся постоянные ai>0,

...,N,

^ja

>0> такие, что

.•--=1

(^\-])

= m^:

У*ilt(иI-])-

i-1 «M6^ i-1

Следующий способ построения «свертки» критериев пред-

ложен В. В. Подиновским [121J:

Лемма 8. Если функция ср(Л,

...,IN)

является строго

возрастающей по каждому аргументу, то набор управляющих

воздействий

[-\£%,

реализующий максимум функционала

ц>(1

(«[•]),..., 1м(и\-])), оптимален по Парето для игры

(Ю)-(П),

т.е.

Ф(А(«"[•]). ...,/.у(й

[.1)) = тах

(/-(й[-1), ...,I

(u\-])).

Предположим противное: пусть набор управляющих воз-

действий и

Щ, обращающий функционал

(/i

(и

[•])»...

(и

[

•

]))

в максимум на %, не оптимален по Парето для

игры

(10) — (11).

Тогда существует набор

и*{•]£%,

такой, что

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

Л(«*[-1)>Л(я

[-1).

i-Ь

...,N,

из которых, по крайней мере, одно строгое. Пользуясь свой-

ством функции ф, можно записать цепочку неравенств:

<p(/i<«

H)- ...,/.у(й

[•!))<

<Ф(Л("*[•])•

h(u

[-])> ...,Ы«

И))<---

...<Ф(А(»*[•]), ...,/*_! (а* И). /.v(tt

H))<

<Ф(/

(и*[•!),. ..,/.v(^[-l))>

так что

(Л («"[•]), ..../^(«

[-1))<Ф(/1(й*['1)> ...,/лг(й*

[•]))•

Однако последнее неравенство не доожет выполняться, так как

набор управляющих воздействий u"[t] реализует максимум

функционала

Ф(Л

(«[•]). -.., /.v (к

[•]))•

Из леммы 8, в частности, следует лемма 1, где ф-=2аг/

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

игре (Ю)

—

(11) может не существовать. Такой пример построен

в статье Лозера и Вольза

[275].

Приведем его.

Пример

[275].

Пусть система (10) имеет вид