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

Задачи принятия решений в технических, политических, экономических системах, в военном деле характеризуются многими факторами, к которым следует отнести структурную сложность управляемой системы, наличие нескольких заинтересованных сторон, динамический характер системных процессов, влияние на процесс управления неконтролируемых факторов различной природы (неопределенность следующего хода оппонента или постановки цели, помехи на каналах связи, погодные условия, и пр.). Процесс поиска решения происходит в условиях столкновения интересов различных групп, что является естественной формой состояния сложной системы. Начало исследований игровых моделей конфликтных ситуаций было положено достаточно давно в работах Дж. фон Неймана, О. Моргенштерна, Р. Айзекса, Г. Оуэна, Н.Н. Воробьева и др. Однако в настоящее время существуют сравнительно мало исследованные направления теории игр, например, дифференциальные игры, в которых функционирование управляемой системы задается с помощью системы дифференциальных уравнений.

Одним из направлений теории игр являются коалиционные игры, которые являются наименее изученными. Коалиционные структуры состоят из нескольких игроков, принимающих решения совместно, при этом между коалициями может существовать конкуренция, либо присутствуют иерархические связи. Первые постановки задач и определения решений для коалиционных игр без учета возмущений были сформулированы в [1,2]. Рассматривались игры с фиксированной коалиционной структурой в условиях неопределенности, для которых были сформулированы определения решения на основе принципов оптимальности по Парето, угроз-контругроз, Бержу, а также доказаны достаточные условия оптимальности [3,4]. Однако следует отметить, что практически все

Решение одной коалиционной игры в программных стратегиях при неопределенности исследования проводились для позиционных игр, которые позволяют учитывать при принятии решения обратную связь. Тем не менее, если по каким-либо причинам (например, из-за помех) эта информация становится недоступной, следует использовать программные управления. Игровые задачи с дифференциальными ограничениями при неопределенности в программных стратегиях ранее практически не изучались, исключение составляют работы [5,6], в которых рассматривалась кооперативная и иерархическая игры.

В данной работе рассматривается антагонистическое взаимодействие двух коалиций с произвольным числом участников при неопределенности в условиях отсутствия обмена информацией между коалициями. Решение строится на множестве программных стратегий. Внутри коалиции отношения между игроками являются доброжелательными, и решение принимается на основе желания максимизировать общий выигрыш коалиции. Подобная кооперация дает возможность использовать для формирования общего критерия свертку Карлина [7]. Для определения решения используется принцип гарантированного результата, который позволяет сформулировать игру в виде максиминной задачи на связанных множествах.

Вывод необходимых условий оптимальности осуществляется с использованием метода штрафов [8-10], позволяющего снять дифференциальные связи и осуществить переход к задаче на максимум. Данный метод является, пожалуй, единственно возможным, так как информационная изолированность коалиций не позволяет использовать другие подходы, например равновесные, к определению решения игры.

В разделе 1 рассматривается постановка задачи и описывается способ сведения исходной максиминной задачи со связанными переменными к обычной задаче на максимум методом штрафов, рассматривается оценка погрешности метода. В разделе 2 приведена теорема о необходимых условиях оптимальности для дифференциальной коалиционной игры в условиях неопределенности. В заключении обобщаются полученные результаты и указываются возможные направления для дальнейших исследований.

1.    Постановка задачи и применение метода штрафных функционалов

Рассмотрим дифференциальную игру N лиц в условиях неопределенности

Г = (P.Wdt^.ZMuW ■/ ■  , которая имеет заданную коалиционную структуру Р = {К1лК2}, где К1 = {1,^,к}, К2 = {к + 1,..., N] — коалиции игроков.

Динамика управляемой системы Z описывается обыкновенным векторным дифференциальным уравнением х = /(u(1), ...,u(N\z,x, t),x(t*) =x„te [t*,%],                       (1)

где х 6 Rⁿ — фазовый вектор, набор u ⁽¹⁾ , _,u ^(w) Е R^r — соответствующие управляющие воздействия игроков, z Е R * — неопределенный фактор, R + (I = ., т, г) — евклидово векторное пространство, t * ,% — фиксированные моменты времени начала и окончания игры соответственно.

В качестве программной стратегии 1 -го игрока u®(0 будем рассматривать ограни- ченную измеримую функцию из допустимого множества D^, принимающую значения на множестве U^, то есть u®(t) £ Д, i = 1,N. Ситуация игры представляет собой набор

(и ^{(1) (} ^), — , u ^(w)C )), а неконтролируемый фактор z является точкой множества Z с ' *

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

Jif^C)’ ...^("ЧО^) = Ф;(х ⁽ %)) +

+ 6 7 (u(1)(t), ■ —,u(w)(t), z, x(t), t)dt, i = 1, N, t,

.

где x(t) — решение системы (1).

Рассмотрим ход игры. Будем предполагать, что внутри каждой коалиции информация о стратегиях друг друга доступна игрокам, а информация об управляющих воздействиях игроков другой коалиции является недоступной. На весь период времени [t * ,%] внутри коалиций игроки совместно выбирают свой конкретный набор допустимых стратегий и®(Д то есть здесь предполагается кооперативный вариант взаимодействия. В каждый момент времени на управляемую систему Z независимо от выбора этих стратегий действует некоторая неопределенность z £ Z . При заданном наборе допустимых стратегий u® = u®(t) , i = 1,N , t £ [t * ,%] , и при любых z £ Z строится решение x(t) , t £ [t * ,%] , системы (1). С учетом выбранной фазовой траектории игроки каждой коалиции независимо друг от друга определяют свои выигрыши, считая, что было реализовано «наихудшее» значение неопределенного фактора. Между коалициями отношения строятся на основе конкуренции (антагонистическое взаимодействие).

Внутри коалиций решение принимается совместно, то есть предполагается создание двух «больших коалиций», что позволяет определить оптимальные стратегии игроков каждой коалиции, руководствуясь принципом Парето с учетом неопределенного фактора [5], это позволяет определять функции выигрыша каждой коалиции с помощью взвешенных критериев:

/кХ^ЧО, -^ЧО^) = Е^^^ЧО, ...^("ЧО^),          (3)

/ к₂ (u⁽¹⁾ (•), —, u ^(w) (•), z) = E jU+1 « j / j (u^w 0, —, u ⁽ ® (•), z),             (4)

где > > 0 , s = 1,N , E ?^1 > i = 1 , S 7=?+1 ^a j = 1 .

Тогда гарантированный результат первой коалиции примет вид:

/Ki =

max                    min           min_7£7 /_K (u ⁽¹⁾O, ...

(a^O.—.J^O^D-^ — XD K (м^(к+1)(-),—,M ( ^Q)(-))£D_k+1X — XD Q           ¹

u ^(w) (0,z

а гарантированный результат второй коалиции:

ZK@

(j Cfc+^C ),

max

■ ,M ( ^Q)(-))£D_k+ 1 X_XD_N

min

(M ( ¹⁾(-),-,M ( ^k)(-))£D₁X_XD_k

min_Z £z/K₂ (u ^{(1) (} ^), — ,u (^' (^),z). (6)

Решением игры Г назовем набор {(u ⁽¹⁾ * , — ,u ^(k )* ,u ^(k+1 )* , — ,u ^(w) * ), (/ К ₁,/ К @ )} , включающий в себя стратегии игроков, реализующие равенства (5) и (6), и суммарные выигрыши коалиционных групп.

В связи с недоступностью игрокам информации о стратегиях коалиции противника, стратегии u ⁽¹⁾ * , —, u ^(k) * будем находить, решая задачу (1), (5), действуя с точки зрения первой коалиции. Стратегии u ^(k+1) * , — ,u ^(w) * будем находить, решая аналогичную задачу (1), (6), действуя с точки зрения второй коалиции. Затем вычисляем выигрыши игроков / К₁ и /К ₂ . Найденные неопределенности в первой и второй задаче могут не совпадать.

Для обеспечения существования и единственности решения уравнения (1) будем предполагать:

• 1)    множества U ; , i = 1,N, — выпуклые замкнутые и ограниченные множества, множество Z — замкнуто и ограничено;

• 2)    вектор-функция / непрерывна по всем своим аргументам, удовлетворяет условию Липшица по % в каждой ограниченной области фазового пространства;

• 3)    вектор-функция / при любых t, %, и *-⁷') , у = 1, N, z удовлетворяет условию

X/(u(1), ..., и(^), z, %, t)|| < Z(1 + ||%||), где ||'Н — евклидова норма, Z — некоторая константа.

Далее, предполагаются выполненными следующие условия, которые являются достаточными для применения метода штрафов и формулирования необходимых условий оптимальности [5]:

• 4)    функции и ⁽¹⁾ (-), ...,u ^(W)0 принадлежат ]₂ [t * ,%] — пространству функций с интегрируемым на [t * , %] квадратом, а %(•) принадлежит W 2*¹) — пространству абсолютно непрерывных на [t * , %] функций с производными из ]₂ [t * ,%] ;

• 5)    вектор-функция / линейна по каждому u ^(j) и измерима по t ;

• 6)    функции F ; строго вогнуты по соответствующему u ^(j) , удовлетворяют условию Липшица по % и совокупности управлений и ⁽⁷⁾ , у = 1, N, и измеримы по t ;

• 7)    вектор-функция / и функции Ф ; , F j , i = 1,N , непрерывно дифференцируемы по % , ограничены вместе со своими производными по % и и ⁽⁷⁾ , у = 1, N, при любых ограниченных (и ⁽¹⁾0 , ..., u^Q,%(•)) ;

• 8)    вектор-функция / и функции F ; измеримы и ограничены по z .

Будем решать задачу с точки зрения первой коалиции, для второй результат формулируется аналогично. Для снятия дифференциальных связей (1) введем целевой функционал со штрафом:

F/u^C), ...,u ^(k) (•),%(•),') =            min           min_zez

/хДи^ЧО,—U^C^z) — (7)

^^^^^в

■ '66 (%(t)—/(u ⁽¹⁾ (t),...,u⁽^^       dtd(dz x du ^(k+1) x . x du ^(w) ),

где ' > 0 — параметр штрафа, d(dz x du ^(k+1) x ... x du ^(w) ) - мера Лебега, заданная на множестве Z x D ? ₊₁ x .x D_N . Получим семейство максиминных задач

Й(Я) =      max      _(и ⁽¹⁾ (-), .,u ^(k) (■),%(■),'),                     (8)

х(-),м(1)(-).....м(к)(0

где максимум берется по всем абсолютно непрерывным функциям %(•) , производные которых принадлежат множествам ]₂[t * ,%] , и по управлениям и ⁽¹⁾0 , ..., u ^(k0 ) 6 ]₂[t * ,%] .

Теорема 1. Решение задачи (7), (8) существует, и имеет место равенство limP(')= lim      max      _(u(1)C), ...,u(k)0,%(•),') =/;1, h^j          h^jfij,u,'1)ijr..X1')(j причем для достаточно больших ' имеет место оценка погрешности

F ² ] ²

Доказательство аналогично [6], отметим лишь некоторые особенности.

Существование решения доказывается подобно [8]. Введем множество

P = U(u ⁽¹⁾ (•).....u ^(k) (•), x(-))| x(t) e ' ( ,%(•) e W₂ ⁽¹⁾ [t * ,%],u ⁽0 (t) eU_iC ' ( ,u®(0 e L₂[t * ,%],

1 = 1, N, % (t) = /(u ⁽¹⁾,... , u ^(N) , z, %, t), %(t * ) = % * , t e [t * , %], z e Z}.

Так как функционалы /i, 1 = 1, k , удовлетворяют условию Липшица по % и совокупности управлений u ^(A) , j = 1,N, то для любого вектора (й ⁽¹⁾ (•),.,u ^(k)O ,%C)) e P, u®(t) e U i c ' ( , u ⁽ⁱ⁾Q ) e L₂ [t * ,%], 1 = k + 1, N, и z e Z будем иметь:

[/^(u^C), .,u ^k -x,u ?<-x, .,u ^(N) (^),z) — J_{K 1} (u ⁽¹⁾ (^), ...,u⁽?-(0,u⁽?⁺¹40, .,u ^(N) (^),z)| <

< L I rXu (-) — u ^(A) (^)X s₂ + Hx(-) — %(^)H t (i) I, 7-1                       ^{2                     2}

где L — максимальная константа Липшица, k — число игроков первой коалиции.

Пусть p s @ = Hu(^) — й(^)Н — метрика в L₂ , p t (i) = 11%С) — %(^)Н — метрика в ^ 2 ⁽¹⁾ . Тогда

|/;1(u(1)(^), .,u(k)(^),u(k+1)(^), .,u(N)(^),z) — JK1(u(1)(^), ...,u(k)(0,u(k+1)(0, .,u(N)(^),z)| < < L (kpL@ + pt(i)) < Lkp, где p — метрика в Lk x ^2(1), равная сумме метрик L2 и ^2(1) и, в силу свойств целевых функционалов и множеств допустимых стратегий игроков, получим min           min/к (u(1)(^), .,u(N)(^),z) * + Lkp.

Также аналогично [9] имеем оценку

'      6      6

., u ^(N) (t),z, %(t), t)| ² dtp(dz x du^t- ^k+1"⁾ x ... x du ^(N) ) >

AMp(Z x D k+1 x .xDn)p², где M — положительная константа. Таким образом, получаем оценку погрешности E(') = _(u ⁽¹⁾ (0 u ^(k) (•),%(•),')—/^ < Lkp —'Md(ZxD k+1 x ^xD_N)p².

Найдем максимум функции -(p) = Lkp — AMp(Z x D k ₊₁ x ... x D_N)p ² , получим точку kL

p * = ——-— -----—.

2'Md(Z x D_k+1 x ... x D_n)

Отсюда при p = p * получаем искомую оценку погрешности. Следовательно, для сходимости метода достаточно выполнения условия ' ^ ^ . Теорема доказана.

Для сведения функционал

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

W(u ⁽¹⁾ (0, ..^u^'O/xO'), z,',v) = z

^^^^^в

—{

6     (min[0,/_{K i} (u ⁽¹⁾C ), .,u ^(N) (^),z) — z]) ² ^(dz x du ^(k+1) x ...x du ^(N) ) —

—'6     6 (%(t) —/(u ⁽¹⁾ (t), .,u ^(N) (t),z,%(t), t)) dtp(dz x du ^(k+1) x . x du ^(N^ ).

Получаем задачу:

W(A,v) =          max         W(uⁿ⁾C),... .u^'C^xO, z,', v).      (10)

(M⁽¹ ) (•).....м^(к) (O.xO^L K xtto

-j

Теорема 2. Решение задачи (9), (10) существует, и имеет место равенство lim W(',v) = lim           max          W(u(1)C), ...,u(k)(-),x(-),z,',{)=/; .

h,v^j             h,v^j(_M(i)(.) _M№(.),_x(.))6.LKxt₂^{(1)                                              1}

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

2.    Необходимые условия оптимальности

Теорема 3. Для того чтобы ситуация (u⁽¹⁾* (•),., u^(k)*(^)) 6 D₁ x ..xD? была оптимальной в задаче (1), (5) при соответствующих траекториях %*(•), необходимо существование такой измеримой функции р(^⁽?⁺¹⁾(-), ...,u^(w)(0,z) > 0, что

• 6    p^1"1)0 “(")(-)z)d(:z x du(k+1) x ■ :u ^1=1

ZxDk+1x_xDN а также не равных нулю одновременно чисел 9 > 0 и вектор-функции ограниченной вариации ^(u(k+1)0),..., u(w)0), z/) таких, что

• 1)    при любом фиксированном z6Z и наборе (u^(k+1)(t), .,u^(w)(t)) 6 U_k+1 x .x U_k вектор-функция ^(u^(k+1)(^),..,u^(w)0),z/) удовлетворяет уравнению

^(u(k+1)(t), ..,u(w)(t),z, t) = —9 p(u(k+1)C), .,u(w)(^),z) x k x V ^^-TUu^^), .,u(k)*(t),u(k+1)(t), .,u(w)(t),z,x*(t), t )-OX i^1                                                 r

— (OX^(u⁽¹⁾*(t), ., u^(k)*(t), u^(k+1)(t), ., u^(w)(t), z, X*(t), t )) ^(u^(k+1)(t), ., u^(w)(t), z, t)

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

k

^(u(k+1)(^), , u^)(;), z, %) = 9 p(u(k+1)C), ...^(мУ >;^-Ф;(%*(9) ); OX i=1

Заключение

В статье было представлено решение задачи антагонистического взаимодействия двух коалиций игроков в условиях неопределенности, которая была формализована как максиминная задача на связанных множествах. С использованием метода штрафов данная игра была редуцирована к задаче на максимум, что позволило сформулировать для нее необходимые условия оптимальности. В дальнейшем планируется исследование других видов игр, сочетающих в себе коалиционные структуры и другие виды взаимодействия, например, коалиционно-иерархическое.