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

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

УДК 519.3:518.12

ДИФФЕРЕНЦИАЛЬНЫЕ ИГРЫ С НЕНУЛЕВОЙ СУММОЙ

(КООПЕРАТИВНЫЙ ВАРИАНТ)

Н. Т.

Тынянский,

В. И. Жуковский

Введени е

Рамки и цель обзора. К настоящему времени в теории

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

ных игр с ненулевой суммой) сложились следующие четыре

основные направления исследований: бескоалиционные, коопе-

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

ческие динамические системы. Обзор теории и приложений

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

проведен в

[151].

Настоящая работа является продолжением

[151] и охватывает результаты по кооперативным дифферен-

циальным играм. Иерархические динамические системы и ко-

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

реть особо.

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

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

ные в РЖ «Математика» до 1977 г. и, частично, опубликован-

ные в 1978 году. Причем не включены статьи., посвященные

кооперативным (не дифференциальным) играм. Здесь основные

результаты и направления дальнейшего развития рассмотрены

в основополагающей работе Н.Н. Воробьева [23] и серии статей

Э. Вилкаса [19—21]. Обзоры состояния теории кооперативных

игр в [8, 179, 294, 295]. Мы также почти не касаемся задачи

векторной оптимизации, отсылая к обзорам [7, 9, 21, 62, 109,

227] (библиография, доведенная до 1975 г. и содержащая бо-

лее 400 названий, приведена в [370]).

Вопросы векторной оптимизации динамических систем (крат-

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

монографии [135]) рассматриваются лишь в той мере, в кото-

рой имеет или, по нашему мнению, может в перспективе иметь

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

этом затрагиваются, в основном, публикации после 1974 г. За-

метим, что библиография работ по дифференциальным играм,

содержащая 1303 названия и охватывающая публикации с 1968

по 1976 г., выпущена Уральским научным центром АН СССР

[58].

Цель настоящего обзора

—

дать общее представление о ре-

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

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

ния, либр как метод решения прикладных задач кибернетики.

Определение игры. Подробное описание дифференциаль-

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

обзора (§ 1 из [151]). Здесь мы напомним лишь некоторые

общие положения. Именно, пусть позиция {t, х) игры /V лиц

(целое число N^2) изменяется при возрастании времени t

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

X = f(t, X, tl

. . ., U

)- (1)

Фиксирована начальная позиция {t

, х

), причем t

= Const >0 и

•х(-о)—

-Ко-

(2)

Здесь x£R

ufcR™

—

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

игрока

= 1,.,., /V). В зависимости от информированности

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

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

Если i-й игрок формирует «свое» управляющее воздействие

в-виде только функции времени щ(1) на всю продолжитель-

ность-игры, то щ{Ц —программное управление t-ro игрока.

В случае,' когда i-й игрок конструирует «свое» управляющее

воздействие

'виде функции;щ

(t,

х), зависящей уже от позиции

{t, х}, то Ui(t, х)—позиционное управление i-ro игрока. Заме-

тим;

что Vii^Ui) означает множество программных (позицион-

ных)'

-управлений i-го игрока. Далее в каждом конкретном

случае указываются ограничения на функции Ui(t), u,i(t,x) я

f(i;xyu

...\ u

). Они таковы, что существует единственное и

продолжимое на весь интервал игры решение 'x'(t)"-системы

(

1)-— (2)

при любом наборе управлений всех игроков (про-

граммных или позиционных).

Особо выделен случай формализации решений (движений)

системы (1)

—

(2),

предложенной Н. Н. Красовским [83].

Здесь управляющие воздействия t-го игрока отождествляются

с любыми функциями Ui(t, x)eQi — компакту в

R™L

Существо-

вание решений

(1) — (2)

здесь достигается

не

введением допол-

нительных ограничений на характер функций u

{t, x), а путем

иного определения этих решений (подробно см. § 10, п. 10.1).

В,

пространстве позиций {t, х} задано терминальное, .много-

образие М, и момент окончания игры T>t

характеризуется

условием первого «попадания» позиции {t, x(t)} на множе-

ство М:

{т

уХ

(Т)}ем. (-3)

Отметим, что во многих приложениях, особенно экономи.ческих

(§ 13, п. 13.2), отсутствуют ограничения на правый конец

траектории x(t): множество M—{t, x\t

—

T, x£R

} (требование.

(3) выполняется автоматически). Далее предполагаем,., .если

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

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

Необходимо заметить, что к выполнению (3) или 'к противопо-

ложному требованию {Т, _х(Т)}$М .сводятся,, соответственно,

задачи поимки или убегания © дифференциальных .. играх';";;.?.

несколькими преследователями и убегающими. В этом, важнрк

и трудном классе задач теории дифференциальных, игр" й'на-

стоящему времени получены важные результаты (М.С. Габ-

риелян [28—31]; П. Б. Гусятников [51—53]; С. В. Лутмаиов

[87—88];

Е. Ф. Мищенко, М. С. Никольский, Н. Сатимов [100—

101];

Б. Н. Пшеничный

[129];

Б. Б. Рихсиев

[131];

С. И.'Тал-

линский

[149];

Ф. Л. Черноусько, А. А. Мел.икян [158, гл.

VIII];

А. А. Чикрий [159—163]; работы, не включенные в данный

перечень, указаны в [151]). Рассмотрение этого .на-

правления' представляет самостоятельный интерес

и, поэтому

здесь не затрагивается. Частичный обзор применения прямого

метода Л. С Понтрягина к указанным играм имеется в работе

Е. Ф. Мищенко, М. С Никольского и Н. Сатимова

[100],

Где

излагаются и новые фундаментальные исследования /авторой.

Вернемся к дифференциальной игре нескольких лиц. Кроме

(1)

—

(3), для каждого i'-того игрока определена функция 'вы-

игрыша, заданная функционалом

IiiUi,..., u

) = ®

(T,

х(Т))-{-

^Fi(t, x, u

..., tiN-)dt,

i=\,...,N,

(4)

определенном на множестве возможных реализаций решений

x(t),

<£<:7\ системы (1) —(2) при наборе програм-

мных управлений u{t) = {Ui(t),..., u

(t)} (или позиционных

управлений u(t, x) = {u

(t,

x),...,

(t, x)}); в (4) также

= ti

(t) (или u

= u

(t, х)).

Далее для сокращения записи приняты обозначения

/МО при tt

{t)&i

[[

(t,

(t))

при

{t,

х)

е%.

Обозначим множество всех таких функций «*[•] через

°Ui\

точка

•в скобках

('[*])

означает, что время i пробегает все значения

от t

до Т. Обычно предполагается, что функции Ф

-, F

{

в (4)

непрерывны и Фг(^, х) определены для {t, x}£M, а используемые

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

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

[151].

Цель i-ro игрока

—

подходящим выбором «своего» управ-

ляющего воздействия щ[']&Ы{ добиться возможно большего

выигрыша, т. е. значения функции выигрыша /„• к моменту Т

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

Однако сказанного выше недостаточно, чтобы определить

решение игры

—

набор управляющих воздействий "*[•]•=

^{".*[•]•

•• •»

.рг*[•

]}--"^i доставляющий «хороший» выигрыш

всем N игрокам. Здесь следует [151] привлечь кон-

цепции оптимальности, используемые в теории игр

[19—21,

23].

В предыдущей части обзора

[151],

где рассматривались беско-

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

честве такой концепции использовалась равновесность по Нэшу.

Именно, равновесное решение определялось с помощью нера-

венств (см. стр. 15):

Л(и*М1|аЛ-])<Л(«*[-1).

^1.-.-

-V. (

)

для любых щ[-]&и*. Из определения (5) следует, что один

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

равновесное решение, не улучшает, но может и «ухудшить»

свой выигрыш. Однако несколько игроков (больше одного),

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

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

ные выигрыши по сравнению с равновесными (за счет совмест-

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

Пример. Приведем пример достаточно общей дифферен-

циальной игры четырех лиц, в которой первые три игрока за

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

вают свои выигрыши, по сравнению с бескоалиционным вари-

антом игры.

Итак, пусть изменение позиции {t, x) в игре четырех лиц

происходит в соответствии с дифференциальным уравнением

x = A{t)x + 2

*» x(0) =

||-ХоII-7-= 0,

(6)

k-i

а функция выигрыша /-го игрока определена функционалом

/,(«!,

, щ,

щ)

= х'

(Г)

(T)

\х?{t)M

(t) x(t)- ]£а'

\м

(/—-1,

2,3.4). (7)

Здесь xeR

, u

£R

;

= Const>0; лхл-матрицы

A(t) я M

{t)

непрерывны,

Ci постоянны; матрицы Ci

я M

(i)

симметричны;

позиционные управления г-го игрока ограничим функциями вида

(t, x)^Pi(t)

х,

где матрицы

{l)

непрерывны

при

t&[О,

Т\.

Из }151] следует справедливость утверждения: если

-система дифференциальных уравнений

0i+-0i

A+^Q

+ A'+_>k e.+TWi—2

i =

k=i

J L

=- J

ft--»-.

с граничными условиями

9,(Г)

С, (.-

1,2,3,4)

имеет решение

0(£)

{0-

(t), G

(£), ЭзСО» 94(0}» продолжимое

на интервал [О, Г], то для игры

(6) —(7)

равновесное решение

((5) существует

имеет

вид

u](t, х)

6i{t)

(/=1,2, 3, 4).

Выигрыш t-ro игрока при этом равновесном решении удовлет-

воряет условию /i

(и*

[ •

•—-

JCQ0

(0)

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

ного решения получены приемом J63]

помощью функций

ei(£, x) = x

(t)x,

при этом справедливы условия

g ]'(АХ.+

Ut+JtU)(А

х)\+ р. + л'Л!

|Л

—

-^~2\и^/хА^\

£]'(Ах^2К(^

)) + Р +

/«-.1

u J

\ А.=-1 /

H-x'/Wix—

К(*» *)1

'=-0- s

(r,

•JC)

=JC/,C

JC,

при всех xe^

, *{in}[0. Г1.

Утверждение. Если матрицы 6-(.0

—0г(*)-

02(О--6з(О»

-sW~

i(«) невырождены при всех ^б[0, 7"],

то

позиционные

управления

u^t, x) = -j[Q

(t) + Q

(t)]x,

(t, х)

1[0

9з(О]^.

(8)

M*' х) = тЫ*) + M*)l*

+ *L +

tfMjX-

таковы, что

Jj (й\\щ)>1 j

{и*)

(У—-1,

2, 3;

{tti,

из})-

Для .доказательства введем позиционные управления iij{i,x)^

[Lj(t)'-\-BjXt)]x,

где матрицы L

}

-(t) определим ниже. Пока

предполагаем, что Lj(t) непрерывны при ^6[0, Г]. Обозначим

через х

(t)

решение системы (6) при

Uj^Zj^LjiQ + Qjitftx (/ =

1,2,3),

=u*^

(t)x.

Если удастся выбрать Lj(t) таким образом, чтобы выполнялось

неравенство

|г з

Ш]'

Ax-Jr2{L

+B„bx +

|_ -=-1

-2 ^\L'

-\-Q

][L

]x~x'b\x>0, (/ =

1,2,3)

(9>

• •

m=l

при всех

^6[0,

Г], x£JR

, \\.х\\фО, то приведенное утверждение

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

делах от 0 до Т вдоль решения х

{t)

системы (6), получим

(II

II-9-0)

(Т, х (Т))-в.

(0,

) + j {*'

(f)'M

(t)

i(/)-2

»m (*>

* (*>)-

m=*l

~-[u4{t,-x{t))Y}dt>0.

Но

(0,

)

JciGy

(0)

.л:

= /

(fcf

[. ]),

в j (Г, *

(Г))

= х'

(Т)

х(Т) = х'

(Г)

CjX (T).

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

(й

[-1,/7

[.1,й

[.1,

:-1-1)>/

(Й*Н)

(у—1,2,з),

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

Итак, остается показать, что при выполнении требований;

утверждения матрицы Ху(^) можно выбрать таким образом,

чтобы выполнялись неравенства (9), Прежде всего отметим*

что соотношения (9) имеют место, если (||

JC||

.--*.•())

зз

IGTI'S

mX —

x'^ (im6

).x>0

от—1 m—1

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

вий равновесности, включающих; ограничения на функцию

Ej(t, х), ее производные -и u*(t,x)). С учетом tj(t,x) =

±=x

Qj(i)x, получа ем, что последнее" неравенство выполнено*

если при

-7-=

квадратичные формы

x'Hj(t)x>0 (у =-1-2-3),

где

-=(е

—е

+-1

(е

-0

-(9

-е

)-з+1з(81-е

)--2-'^

.-(е

—е

)А+~-(02~е^

/71=1

=(0

—01)

-h ii

so+(е

—е

) -о+z

(е

)

2 -£••

m-1

Непосредственной подстановкой можно убедиться, что для

А =4

(62

63-26-),

l(6

-4-6

—

), 1

—

+ е

"2О

все матрицы 7/

. преобразуются к одному и тому же виду

=-1[(0

—е

)2+(0

-е

(0з—б

)

(;

1,2,3).

'Тогда, в силу невырожденности и симметричности- матрш

—Gy

(in,

= l, 2,3;

tn^j),

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

x'Hj(t)x>0 (7 =

1,2,3)

при всех te[0, T], x£R

, || х ||---Q<

Подстановка найденных _

в ti

= [L

-\-bj\x приводит к пози-

ционным управлениям (8).

• В заключение отметим, что вопрос «улучшаемости» равно-

весных выигрышей игроков (выигрышей при равновесном ре-

шении) рассматривался рядом авторов [320, 230, 64], ему по-

священа глава VIII монографии В. В. Хоменюка

[154].

Эти.

результаты приведены в

[151].

Однако ставилась задача.

«улучшения» выигрыша всех /V игроков. В приведенном.

примере, составленном В. И. Жуковским, показано, что возмож-

но увеличение выигрыша части игроков (не всех), если только-

они имеют возможность совместного выбора . управляющих.

воздействий. Отсюда уже следует правомочность и желатель-

ность «союзов» (коалиций) игроков

ов

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

с ненулевой суммой.

Подходы к отысканию решений. Отличие рассматривае-

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

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

редь,

в том, что побочные платежи, как правило, не разрешены

(нет трансферабельности выигрышей). Например, в задачах

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

момент окончания игры до точки, являющейся .для Него-целе-'

гвой, и поэтому не может делиться и передаваться другим участ-

никам игры. -, -

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

чениями их функций выигрыша ев' момент окончания игры и

перераспределение выигрышей не происходит.

Поэтому выделим три подхода к отысканию «хороших» ре-

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

Первый, «прямой» путь: использование ряда понятий опти-

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

обходимости максимизации (или минимизации) некоторой

.функции <p(jb--.>

j'jv).

Вид ф;(/

..., I

) конкретизируется в

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

неров и от наличия возможности совместного выбора управля-

ющих воздействий всеми или частью игроков. Различным

способам скаляризации функции выигрыша в статических (не

дифференциальных) задачах векторной оптимизации посвящены

работы Ю. Б. Гермейера [32, 33], В. В. Гороховика [35—37,

238],

В. В. Гороховика и Ф. М. Кирилловой [42], В. М. Илыше-

ва [72], Б. С. Метева и И. П. Попчева [94] и других. Разрабо-

таны подходы к свертыванию функций выигрыша в один кри-

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

можно.найти в статье Э. Вилкаса [21], а также, частично, в

монографиях Н. Н. Воробьева [24], Б. Г. Миркина [99],

Р. Д. Льюса, X. Райфа [89]. Заметим, наконец, что овертьива-

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

(в выпуклом случае) и достаточных условий оптимальности, а

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

Затем уже решается задача отыскания набора управляю-

щих -воздействий «*[-]{in}-2/, реализующих этот максимум (или

минимум). Найденное в результате u*[t] представляет решение

игры. Такой подход, как правило, применяется в работах по

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

случае оптимальности по Парето (§ 1), по Слейтеру (§ 7),

арбитражной схемы Нэша (§ 3), в задаче о сделке (§ 3, п. 5),

при отыскании среднеквадратичного решения (§ 2). В некото-

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

стемы неравенств для выигрышей игроков. Здесь опять-таки

решение дифференциальной игры u*[-\W находится из усло-

вий реализации этой системы неравенств. Такой путь исполь-

зуется в п. 10 из § 10 при отыскании наборов управляющих

.воздействий, реализующих С-ядро игры.

Применение «прямого» подхода связано с теорией игр (-не

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

ности (функции <p(/i,..., I

) или системы неравенств, которым

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

/ь...,

IN). Далее уже применяется математи-

ческий аппарат либо теории оптимального управления, либо.

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

циальных игр двух лиц с нулевой суммой).

;Ю

Совершенно новый и» несомненно, перспективный подхо

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

в случае терминальных функций выигрыша (в (4) Fi = 0

i = 1, ...,N) предложен Л. А. Петросяном [ИЗ]. Здесь исполь

зуется множество достижимости С

(х

) системы

(1)

—(2),

т. е

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

, в которые может попасть решение х (t.

•системы (1) —(2) в момент t = T при всевозможном переборе

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

it(t).

На множестве дости-

жимости С

(х

) выделяются точки, в которых реализуется

«хороший» выигрыш (оптимальный по Парето, НМ-решение

или С-ядро). Оказалось, что для специального вида (функций)

выигрыша эти точки с «хорошими» выигрышами обладают специ-

фическими геометрическими свойствами. Так, оптимальные

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

жимости, которые получаются операцией ортогонального проек-

тирования на него выпуклой оболочки целевых точек. Сущест-

вование НМ-решения и его совпадение с оптимальными по

Парето выигрышами игроков имеет место, если граничные точки

множества достижимости не пересекаются с точками из С

которые коалиции из N~-i игроков (£—1,...,Л7) могут себе

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

(1)

—(2) против i-то игрока с платой

— р

(х(Т),у)

(у£С

(х

-а

—евклидово расстояние между точками х(Т) и у). Более

подробное изложение результатов Л. А. Петросяна и его уче-

гника Н. Н. Данилова проводится в § 9.

Третий «обходной» подход: с помощью характеристической

функции игры (она IB дифференциальных играх, как правило,

существует) найти «хороший» дележ для всех игроков, т. е.

числовые значения функций выигрыша, удовлетворяющие той

или иной концепции оптимальности. Это могут быть [23] эле-

менты С-ядра, НМ-решения, .-г-ядра, вектор Шепли и другие.

Практическое определение их (после того, как найдена харак-

теристическая функция игры) уже задача теории игр (не диф-

ференциальных) и в некоторых случаях .решена до конца (век-

тор Шепли). Пусть

ji*,...,

* — найденный таким образом

дележ. Тогда возникает задача отыскания набора управляющих

воздействий «*[•] =

{щ

*'[•],...,

* [

•

]}

6-2/,

реализующих этот

дележ, т. е. u*[t] должно являться решением следующей систе-

.мы уравнений

Ii*=Ii(ui,..., u

), i—l,..., N,

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

(1) —

(2) и a[-]{in}

2/. Такой подход вызывает

трудности именно IB части нахождения u*[t], однако нами IB

•§ 10 п. 9 предложен один частный прием решения, основанный

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

Во всех трех приведенных подходах используются понятия

;из теории кооперативных (не дифференциальных) игр. Эконо-

мический характер- приложений, дифференциальных, -игр

,(;1)

—

(4) "'(§ 13 п.^ 13.2) вызвал ряд новых понятий:., угрожающие

стратегии

[276],

стратегии .наказания;

[-290]

и конкуренции

[276],

динамические соглашения'[276]. ,

.Коалиционная и кооперативная игры. Под коалицией

JK понимается множество игроков K={h,Л ... ^

}£{->2-

• •

" N}*

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

-воздействия коалиции ик={щ

, . •., tii

}£%i

X •-

•

X .%#=--%••>

(Здесь и далее множество,игроков и соответствующую коали-

цию будем обозначать одной буквой, например, К). Функция.

выигрыша коалиции в некоторых случаях векторная:

1к

{-7i

> • • •>/%•}»

я'Ё

некоторых

—

сумма функций выигрыша членов коалиций:

-€*•

Разбиение множества всех игроков {1,2, ...,/V} на непере-

секающиеся коалиции Ки Ki, ..., К

приводит к возникнове-

нию коалиционной» структуры ^ игры.'

При фиксированной коалиционной- структуре 5

, коалицион-

ную дифференциальную игру можно задать следующим образом:

изменение позиции {t,,x} игры происходит, согласно системе

x = f(t, х, u

...,Ujc

x(t

) = x

I' ]€%?>

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

есть IK] (ИЛИ

IKI),/r

= l,

...,т.

Таким образом, фактически приходим

к .бескоалиционной дифференциальной игре т лиц [151 ...

в.

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

Особенность этой «бескоалиционной» игры в том, что в случае

ijcj, г = \, ...,/%, каждый «игрок» (коалиция) имеет векторную

функцию выигрыша. В случае же IK], r

=--=!,...,т,

полученная

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

вой части обзора [151] бескоалиционных дифференциальных

игр.

Рассмотрению коалиционных дифференциальных игр.

авторы предполагают посвятить отдельный обзор.

Предположим, что в дифференциальной игре все игроки объ-

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

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

u[-]^°U,

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

Пусть полученная при этом одна коалиция {1,

2,...,

N}, вклю-

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

ми.

Во-первых, как и в обычной коалиционной дифференциаль-

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

игроков (как в случае векторной функции выигрыша

(1)

Во-

вторых, учитываются и интересы любых подмножеств А"-—