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

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

Согласно определению, гарантированные выигрыши всех

игроков при использовании ими какого-либо набора позицион-

ных управлений U не могут «улучшать» сразу для всех игроков.

выигрыши при оптимальном по Парето наборе U

Установим достаточные условия оптимальности по Парето.

Утверждение. Набор позиционных управлений U

опти-

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

(42) —

(43),

если существуют

постоянные аг>0, i"= 1,...,

/V,

такие, что

min У

aiO;

(.л;

[7\ t

, х

, £/"])=-

= max min V

а-Ф*

(x [T, t

, x

, U]). (45)

Доказательство от противного: пусть для набора позицион-

ных управлений U

выполнено условие (45) и U

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

по Парето. Тогда существует набор позиционных управлений

U* такой, что система неравенств, из которых по крайней мере

одно строгое

ттФ^хуГ,

, x

, и*])>Ф

{х \Т, *

U"}),

i =

\,...,N,

(46)

-n.i

совместна для хотя бы одного из движений х [t, t

, x

, /У

]>.

t£.[to>

Т], системы (10), порожденных набором U

из позиции

, х

}. Умножая обе части каждого г-го неравенства в (46) на.

ai и складывая, получим

min

2 ММ* Г» t

, х

, С/*])>2а

тШФ,(^1-Г. *о>

*о>

U*])>

х{\

»-i i=»i *Ы

N -V

>2o;i0i(x[r, t

, x

\)>min^

(xlT, t

, x

])

= max min У, aiOi (x [T, t

, x

, U]).

U x\-\ fTi

Получаем противоречивое неравенство.

Приведем ряд других определений решения кооперативной

дифференциальной игры.

10.3.

Оптимальность по Слейтеру, Набор позиционных управ-

лений U

назовем оптимальным по Слейтеру для игры (10),.

(42) —

(43),

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

U такого, чтобы была совместна система строгих неравенств.-

т1пФ

(;с[7\ *

, x

, С/1)>

Ф,

(JC

> x

\),

i=\,...,N,

xl\

для хотя бы одного из движений x[t,t

, x

] системы (10)

(порожденных U

из позиции {t

}).

73v

Согласно определению, наборы позиционных управлений, оп-

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

по Слейтеру, обратное, вообще говоря, неверно.

Аналогично предыдущей теореме устанавливается справед-

ливость следующего утверждения:

набор позиционных управлений U

оптимален по Слейтеру

для игры (10),

(42)

—(43),

если существуют постоянные <xi^0,

—1,...,

N, не все равные нулю и такие, что

N N

min 2

(•*•

Р\

*о» JCoi

max min

i®t

(

*о» •*<»

Щ)-

•*м fZ\ с/ -«-11 Д

10.4.

Среднеквадратичное решение. Набор позиционных

управлений V

назовем среднеквадратичным для игры (10)

(42) —

(43),

если

т1птахУГФ!-Ф

(л:[:7\ t

, x

U])Y

= тах2 [Ф]-ФЛх[Т, t

, x

U<])]\

•здесь Ф* = тахтахФ

(х[Г, t

, x

, U\).

Утверждение. Среднеквадратичный набор позицион-

ных управлений для игры (10), (42)

— (43)

оптимален по Паре-

то,

(а, следовательно, и по Слейтеру).

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

если набор U

не оптимален по Парето, то существует набор

позиционных управлений U* такой, что система неравенства, из

которых, по крайней мере, одно строгое,

min

(х

[Т,

, x

U*])

Фi

(х

[T,

, x

\),i

„.„ /V,

jfl-l

совместна. Но тогда и

maxj—Ф

(л;17\ t

, x

и*\)]<—Ф

{х[Т

, x

, U

х[-]

'ИЛИ

0<тах[Ф;

—

(л:[7\

, ^

,£/*I)]«&J-©

(jc[7

, x

, U

\).

x\-\

Так как

Ф^-®

{x\T,

, x

U*])>0,

то

max Щ-Ф^хф,

, и*])\у=т&х\Ф1-Ф

(х\Т, t

, x

U*])f.

Поэтому

тах!Ф;-Ф

(х|Г, t

, x

, £/*])1

<[Ф*

—

ФД.*;17\

, x

U'\)\\

x\-\

причем, хотя бы одно неравенство строгое. Суммируя по

и используя свойства операций max, получаем

•74

minmax2l®;-®i("I^. 'о.

*о,^])1

=тахУК-Ф

(х[Г, t

, x

U<\)\>>

>2тах1Ф;—Ф

(.х[Г, t

, x

U*])]

T-=I

-*•[•!

>тахУ

Щ-Ф

(х-[Т, t

, x

U*])\*,

то есть

тШтахУ 1Ф*—Ф

(л*1Г, t

, x

U\)\

и х[] Д

>max2№-

M*l7\ 'o> x»

U*\)\

•«•I-i i-i

Но это неравенство противоречиво. Утверждение доказано.

10.5.

Арбитражное решение Нэша. Здесь для сокращения за-

писи предполагаем, что в игре участвуют только два игрока

(i=l, 2), тогда и={и

}

где щ управляющее воздействие i-ro

игрока. Пусть наряду с ограничениями а) и б) имеет место

условие седловой точки для маленькой игры [83]: для всякой

возможной позиции {t, x} при любом выборе вектора s£R

су-

ществуют

«1*

и и

* такие, что

f(t, х, и\, th)<s

f{t, х, и\, u*

)*£s

f(t, x, a

tQ. (47)

Тогда существуют J83J максиминные стратегии U\ й U\\

Ф° = тахтшФ

(л:1Г, t

, *

,^]) = ттФДл:[7\ t

, x

,U°.\)

= l, 2).

x\-\ x\-\

Определение. .Набор позиционных управлений U

назовем

арбитражным решением Нэша игры (10), (42)-(43)

= l, 2),

если

тахтШФ(л:[Г, t

, x

,U]) = minb(x[T, t

\),

x[\ x[-]

здесь

(x) =

[Ф

(JC)

- Ф?1

•

[Ф

(х)

—

Ф§].

Имеет место следующее утверждение: при

•mln<J>i(xlT,t

,U°\)>$l (i=l,2) (48)

арбитражное решение Нэша игры (10), (42)

—

(43) (1—1, 2)

оптимально по Парето (и, следовательно, по Слейтеру).

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

не опти-

мально по Парето. Тогда существует набор стратегий U*, что

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

т1пФ-(-*Р\ t

, х^иЦ^Ф^хХТ, t

, x

U«\) (/ =

2).

совместна. Но тогда и

min[Oi(jctr, i

, х

> ^*I)-Ф?1>Ф.

(•*].-">

№])-l!>0

(i —

1,2).

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

тельных функций равен произведению их минимумов, получаем

противоречивое неравенство

щтФ(х\Т

, x

, .У*]).-=ш1п1Ф

(.*р\

,'x

У*])-Ф?1Х

xl-l jfi-i

Хтт[Ф

(х[Т, t

, и*])-Ф

2}>\Ф

(х\Т, t

, x

, £/«!)-©ft x

x[-\

X№*(-*P\ t

, x

, и

\)~Ф°

\>штФ(х[Т, t

\) =

= тахтщФ(.х:[Г, t

, x

, U]).

U x

Утверждение доказано.

Заметим, что аналогичным путем можно определить лекси-

кографически оптимальное, абсолютно кооперативное и Л-опти-

мальное решения. В этом случае также справедлива схема

включения понятий оптимальности, приведенная на стр. 14.

10.6.

Существование. Существование указанных четырех ре-

шений кооперативной дифференциальной игры (10), (42)

—

(43)

устанавливает

Теорема. Если имеют место ограничения а)—б), то су-

ществуют оптимальный по Парето, оптимальный по Слейтеру,

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

(10),

(42) —

(43), а при выполнении а)—б),

(47) —

(48)—ар-

битражное решение Нэша.

Доказательство основывается на теореме существования

седловой точки антагонистической дифференциальной игры [83].

В самом деле, представив систему (10) в виде x=f(t

x,u)-\-0-v

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

вида (47) и ограничения а) имеют место. Тогда, если плата

антагонистической дифференциальной игры есть Ф(х[Т]) и

функция Ф(х) непрерывна, то в такой игре существует [83]

максиминная стратегия U

т!пФ(л;[Г, t

, х

])

= max min

(.к [7\ t

, U\).

«-"М

и ли

.Существование U° и доказывает теорему, т. к. непрерывность

•функции Ф(х) следует во всех четырех случаях из непрерыв

теру (ai>0,

^_ai>0j,

в случае среднеквадратичных

дюсти функций Ф^х), i =

l,...,

(х)=^а

(х) при оты-

екании оптимальных по Парето (ai>0)> оптимальных по С лей-

наборов

•позиционных управлений

(х)= — 2 [Ф?

—

(х)]

и для арби-

тражного решения Нэша

Ф{х)

[Ф

(х) —

\-[Ф

(х)

—

Ф°

10.7.

Характеристическая функция игры. Пусть в игре (10),

'•(42)

—(43)

несколько игроков объединяются

—

образуют коали-

цию

/^—{1,

2 А/}. Позиционное управление коалиции

(t,

x) = {u

(t,

x),...,

(t, x)}

GK,

m=\,...,

k),

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

Ф-г(*)=2

/(*)-

je*

Тогда наибольший гарантированный выигрыш коалиции К

игре (10), (42)-(43) определится равенством

у(К) = тахттФ

(х[Т, t

, х

, и

]) = ттФ

(х[Т, t

, x

, UU).

х[-\ х\-\

Числа

v (К)

можно интерпретировать как выигрыши, которые

коалиции К могут обеспечить (за счет использования набора по-

зиционных управлений U$?), не прибегая к переговорам с дру-

гими участниками игры. Функция v(K), определенная для лю-

бых возможных коалиций К, является [23] характеристической

функцией игры (10),

(42) —

(43).

Тогда сама кооперативная диф-

ференциальная игра может быть задана [23] как

Г= ((10), (42)-(43), #-->>,

тде

3^—

{К\,

•. •,

Ке} —

множество возможных коалиций. Важным

•результатом для теории кооперативных дифференциальных игр

является

Теорема. Пусть выполнены ограничения а)—б) и для вся-

ких возможных коалиций К№ и позиции {t, x] при любом выбо-

ре вектора sGR

s'f(t, х, tt

, u

)<s

f{t, x, if

, и'^Х

<s'f(t, x, u

ti*

)

(49)

{U>N\K—управляющие

воздействия игроков, не входящих в К).

Тогда какова бы ни была начальная позиция {t

, х

} существует

характеристическая функция игры (10), (42)-(43).

Факт существования следует из теоремы 18.1 в [83, стр. 76J,

если заметить, что для каждой коалиции К дифференциальная

антагонистическая игра

x = f(t, х, и

ик\к),

ХКО]

АГ

(50)

1к(хЩ,

<t<T) = <b

(x\T\)

имеет оптимальную максиминную стратегию U

°.

Отметим, что ограничительное требование (49) можно опус-

тить,

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

рать смешанные стратегии [83]. Именно, если выполнены огра-

ничения а), б) из п. 1, то существует оптимальная максиминная

смешанная стратегия Ок° такая, что

v(K)= maxmin<].V(x[7\ t

, x

, D

])=

т'тФ

(х[Т,

, x

U°

])~

Здесь существование U°

является следствием существования

седловой точки антагонистической дифференциальной игры (50)

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

Супераддитивность функций v(K) устанавливает

Утверждение. Для двух коалиций К\ и Кч таких, что

К\

К2

—

0' имеет место

^(^iU^

)>^(/<i)+^№).

Для доказательства заметим, что

= max min

{Ф^

(я [7\ t

, x

, U

•_>,])-{-

К2

(х\Т,

, x

, U

, Щ)} =

тШ

{ФкАх[Т,

, x

U%,

£/JJ) +

К2

(х\Т,

, x

, и%,и°])}>т\п{Ф

К1

(х[Т, t

, x

, U

])

,{х[Т,

, x

, U

])}.

Здесь использован

ТОТ

факт, что набор позиционных управле-

ний

={U

L/y—оптимальная максиминная стратегия в игре

(50) {К=К\[}К^. Последнее неравенство справедливо для лю-

бых наборов позиционных управлений

={U

Кя

}. Заменим

стоящий справа минимум суммы на сумму минимумов:

т1п{Ф*Дл[7\ *

, JC

, U

-7*

J) +

Ф-,

(JC

[7\ t

, x

, U

.\)}>

>ттФ

К1

(х[Т, t

, x

, U

£/*,])

JC[-\

+ ттФ

Лх\Т> t

, x

, U

]).

•*+]

Согласно лемме 6.2. из [83], каждое из множеств движений:

x[t, t

, XQ, U

], l=\, 2, содержит все движения x[t, t

, JC

UKA',поэтому

ттФ

.(х\Т,

, x

, U

])>min<£

{x[T,

, x

, U

x\.\

\.\

l l

(Z=l, 2).

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

v(Ki[]К2)>т'тФ

К1

(х[Т, t

, x

, и

К1

]) + т1пФ^(х{Т, t

, x

]),

x\.\

.*-[•]

справедливое для любых движений x[t, t

, x

, Ux

], t

<sCt<cT

2), а значит и для движений, порожденных оптимальной;

максиминной стратегией U

в (50) при K=Kt. Поэтому имеет

место

v(K

[)K

)>v(K

) + v(K2).

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

функции v(K), если она существует. Последнее гарантируется

[83] в случае позиционных управлений выполнением требова-

ний а)—б) и (49) (предыдущая теорема), в случае.смешанных

стратегий — достаточно лишь ограничений а)—б). Для практи-

ческого нахождения характеристической функции игры можно-

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

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

мой).

Отметим, что способам отыскания характеристической функ-

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

статьи С. В. Чистякова

[164],

Хизачи и Харунори [252] и цикл

работ С. Л. Скеруса и И. П. Ячаускаса [139—143]. Причем, ес-

ли в [164] и [252] нахождение характеристической функции сво-

дится к задаче максимина, то в [139—143] характеристическая

функция определяется через ситуации равновесия, выбранные

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

ние этих результатов будет проведено в обзоре, посвященном?

коалиционным дифференциальным играм).

10.8.

Дележи. Далее в этом параграфе, не оговаривая особо,

предполагаем, что выполнены требования а)—б) и (49). Пе-

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

щих дележ игры (10), (42)

—

(43). Именно набор позиционных

управлений Us, реализующий дележ [24] игры (10), (42)

—

(43),.

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

min<-Di (.*[7V

> x

, U«\)>v(i), i = l, .. .,N,

•*[•]

N N

тахпипУ! Ф

(х[Г, t

, x

U])

= mm ^^

(JJC

[7",

, x

Us])

= v.

79-

Чтобы набор позиционных управлений

реализовал дележ

:игры-

(10),

(42) —(43)

достаточно, чтобы

®t(x[T,

, х

U*])

'—i)(i)-\-a.i,

= l, .. .,N, для

любых движений системы (10),

-порожденных

из

позиции {t

, x

} набором позиционных управле-

ний

£/*,

причем

ai>0

2ai =

—

2^(-

i=l

Этот факт устанавливается непосредственно проверкой выпол-

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

дионных управлений, реализующих дележ игры

(10),

(42)

—(43).

В классической кооперативной теории

игр

важнейшей зада-

чей является нахождение «справедливых» дележей.

Это

может

быть

[23]

элемент С-ядра, &-ядра, решение

по

Нейману-Мор-

генштерну, вектор Шепли

любой другой дележ, рекомендуе-

мый игрокам кооперативной теорией игр. Причем 'Некоторые

из

них, например, £-ядро, /г-ядро, вектор Шепли, всегда существуют.

Две дифференциальные игры вида

(10) —(И)

функциями

выигрыша

(

J- и lf\

= \, .. .,N,

называются стратегически

эквивалентными, если существуют постоянные

а>0 и b

i==1,

.--.,./V, такие,

что для

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

действий

u\t\

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

/f)

(а[•])--=

alf

]

(#[•])

•\-b

i =

\,...,

Облегчает нахождение «справедливых» дележей

тот

факт,

•что

при

выполнении требований

а)—

б)

(49) дифференциальная

игра (10),

(42) —(43)

стратегически эквивалентна

[24]

диффе

ренциальной игре

в 0—1

редуцированной форме,

т. е. игр

х =

/у,х,а

1г

...,ин),

x[i

]

ufiPn

(x\t]/i

<t<T)^

(x\T\)

*=-l,

...,N,

для которой

v(i) = m&xmm&

(x[T,

£/i])

i = \, ...,N,

t/i

jr[-l

= maxmin2

^(-*

;

I-

*o» Jc

,C/])

= l.

x[.\ fZ

Доказательство следует

из

[24], если положить

-l>i=-a®i-|-6i, i

= l, ...,N, где

= ^ ,

i>t

)

МЬ1

исключаем случай

-о

=2 ^

—

аддитивно-

—2» (о

i=1

i —1

сти характеристической функции,

т. к.

тогда возможен лишь

один дележ

(1),

.,,

{N)}).

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

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

в п. 10.9

утверждение,

где

следует положить

/.$•=--*,

(г)-feci,

ai>0

и ^

—

{sum}

(0-

1=1

i-=l

10.9.

Достаточные условия. Итак, пусть игроки, используя

характеристическую функцию, выбрали некоторый дележ I

{/i-,...,

}- Так как мы

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

дифференциальную игру

без

побочных платежей,

то

возникает

задача определения набора позиционных управлений

«до-

ставляющих»

моменту окончания 'игры

каждому игроку

выигрыш, равный соответствующей компоненте вектора

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

ний

-^-us(t,

х), для

которого имеют место равенства

<&i(x[T,

хо, ив])=1

{

е, t=l,...,

N, где x[t, t

, x

£/*], *о<*<-

\~Дви-

жения системы

(10),

порожденные набором

из

позиции

{to,

Один

из

возможных подходов

решению поставленной

за-

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

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

рецептами теории

динамического программирования.

Утверждение. Если удалось найти непрерывно диффе-

ренцируемые функции

(t, х),

непрерывные функции

^i (t)

и набор позиционных управлений

-+-u

(t,x)

такие,

что

функ-

ции u

(t,x)

области ^

</<Г являются решением системы

алгебраических уравнений:

dzi(t,

х)

d{epsilon}

(t, х)

дх

f(t,x

+ ^

(t) =

i = l....,N, (51)

кроме того,

(Т,

(Г, t

£/«))

Ф-

(х

(Г,

Хо,

С/*)),

(52)

\Mp

(t)dt

,Xo)-lf,

= \, ,...,N,

то набор позиционных управлений

U*+u

(t,

реализует дележ

игры

(10),

(42) — (43),

т. е.

(*[7\*

.*о.^*1)==/*

' =

-•

...,N.

Для доказательства, следуя

[83],

рассмотрим обобщенные

движения

(t), которые являются решениями уравнения

кон-

тингенциях x

(t)£f(t,

(t)),

x(t

) =

. Здесь символом

f(t, x)

обозначена выпуклая оболочка множества векторов f{t,x,u),

получающаяся, когда вектор

и£Р

пробегает все

те

значения

и-\

при которых выполняются равенства (51). Производная сложной

функции

e°.(t)

= e

(t,

(t)),

согласно общему правилу

[83],

имеет

вид

6-4150

e?(*)—-

дх

•«•(-)+--f

Тогда из (51) при почти всех

^6[/

7*3

ё?(0 +

(0 = 0. *-==!• •••'-

Интегрируя последние равенства в пределах от t

до 7\

получаем

-о

С другой стороны, с учетом (52),

0 = *

(T,x4T))-*tfo*Xo) +

*i{h>x

)-lf=Q

(T))-lf*

для любых обобщенных движений

(t),

-*ct<cT.

Неконструктивные движения x\t,t

,Uz] системы (10) >.

порожденные набором стратегий № из позиции {t

, х

}, содер-

жатся в множестве обобщенных движений {x^(t)} = {x^(t, t

£/*)}•

Поэтому из последнего равенства получаем:

(x[T,t

,Uz]) =

r?,

г=1, ...,7V.

Замечание. Если функция выигрыша /-го игрока имеет

вид

(Fi

непрерывны и липшицевы по х), то утверждение также

имеет место с заменой условий (51) на

i!L.4-

d&i

дх

^x,u)+F

{t,x,tt)-\-^

(t)

= \,

...,N.

Приведем простой иллюстрирующий -пример дифференциаль-

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

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

лизующего вектор Шепли.

Пример. Рассмотрим дифференциальную игру, изменение-

позиций которой происходит согласно уравнению

х = щ+щ, jc[0].==2, (53)'

где xeR

, u&R

и a

6[-liO]

2). Функции выигрыша иг-

роков определены функционалами

2 2

= s[x

dt» I

= 2

[

\xdt, (54>

6 о

т. е. момент окончания игры

Под движением x[t] систе-

мы (53) будем понимать просто ее решение. Нетрудно найти.

характеристическую функцию

«о(1)=8,

т>(2)=4,

*>(1,2)

32.

Определим вектор Шепли {<p

ср

}

по формулам из [89]