Динамические матричные игры. Обоснование применения принципа минимакса в классе чистых комбинированных стратегий

УДК: 518.9

ДИНАМИЧЕСКИЕ МАТРИЧНЫЕ ИГРЫ. ОБОСНОВАНИЕ ПРИМЕНЕНИЯ ПРИНЦИПА МИНИМАКСА В КЛАССЕ ЧИСТЫХ КОМБИНИРОВАННЫХ СТРАТЕГИЙ

Н. Н. Данилов

DYNAMIC MATRIX GAMES. SUBSTANTIATION OF APPLICATION OF MINIMAX PRINCIPLE IN THE CLASS OF PURE COMBINED STRATEGIES

N. N. Danilov

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

Matrix games have rather extensive practical application. As decision-making processes in social and economic and other systems have dynamic nature, there is a necessity of generalization of matrix games class so that time factors were considered. Dynamic matrix games are built in the form of a multistage problem of conflict control. New class of strategies (k-strategies) are introduced. Concepts of optimal pure k-strategies, optimal trajectory and value of game are defined. The use of minimax principle in dynamical matrix games are substantiated. Sufficient condition of existence of unique optimal trajectory is found. Dynamical stability of optimal trajectory is ascertained.

Ключевые слова: матричные игры, принцип минимакса, седловая точка, цена игры, оптимальные стратегии и траектория, динамическая устойчивость.

Keywords: matrix games, minimax principle, saddle point, value of game, optimal strategy and trajectory, dynamical stability.

Пусть переменная t, которую будем называть «временем», принимает лишь дискретные значения: t = 0,1,... Т. Рассмотрим некоторую управляемую систему, изменение состояния которой происходит в дискретные моменты времени t и описывается уравнением

х^) = /‘ (х^ —1), ), и2(0), г = г,.,Т,

из заданного начального состояния

х0 = х

В (1) - (2) х(^) е Я - вектор состояния;

Щ (V) е Я1, и2 (V) е Я2 - векторы управления в

момент V; /1 : Як х Я1 х Я2 ^ Як - вектор-

функция, характеризующая динамические возможности системы.

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

и^) е и1, и2^) е и2, V = 1,...,Т,

где и ^ Я, и2 ^ Я2 - заданные непустые конечные множества.

Соотношения (1) - (3) определяют дискретную систему с двумя управлениями. Будем считать, что выбором управления и1(-) = {и1(1),..., и1(Т)}распоряжается игрок I, а выбором управления и2 (•) = = {и2 (1),..., и2 (Т)} - игрок II.

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

Ц = и1 х...х иТ U2 = и1 х...х иТ . Предполагается, что каждой паре управлений и1 (•), и2 (•)) е Ц х Б'2 соответствует единственная последовательность

х

обозначим символом X(Х0, Т) .

Введем в рассмотрение множество:

G(x(t -1), t) = {x(t) = x(t, x(t -1), ul (t), u 2 (t)) |

c(t — 1) G G(x(t — 2), t — 1), u1(t) G Ul, u2 (t) G U

которое будем называть множеством достижимости V-го уровня, V = 1,...,Т (будем считать, что

G(х(—1), 0) = Х0). Множество

С(х\ Т) = и 0(х^ —!), V) будем называть множеством достижимости системы (1) - (3). Считается, что Х0 е G(Х0, Т) по определению.

Пусть в каждой точке х = х(^ (V = 1,...,Т) множества достижимости О(х0,Т) системы (1) - (3) определена матрица выигрышей игрока I:

' а11(х(г)) а12(х(г)) . . а1п (х(г))''

Кх

ч ат1(х(г)) ат2(х(г)) . . атп (х(г))у

(к(х0) = ||0| - т * «-матрица с нулевыми эле-

ментами, где т и п конечные числа). Целью игрока I является максимизация значения функции

Н

г=1

где I = {/'г, г = 1,..., ТЬ 3 = Ц, г = 1,..., Т} - последовательность чистых стратегий игроков, выбираемых ими в матричных играх Ъ(х(г)), г = 1,...,Т . Целью игрока II является минимизация значения функции (5).

Определение 1. Чистой комбинированной стратегией (чистой к-стратегией) игрока I (II) будем

называть отображение (р1 (ф2), которое каждому

шагу г и реализуемому на этом шаге состоянию х

ставит в соответствие номер /г () выбранной

строки (столбца) матрицы к(х(г)) некоторое допустимое на этом шаге управление

и1 (г +1) є и[+1 (и2 (г +1) є иі1+1).

к-Стратегии игроков можно представить так:

= {(U1(1), /1), -,(и1(Т), /Т)},

^0 = {

где /г и - номера выбранных в момент г (в состоянии х(г)) строки и столбца матрицы к(х(ґ))(г = 1,...,Т). Множества стратегий игроков обозначим соответственно Ф1 и Ф2.

Совокупность

Г

где (х0, Т) - символическое обозначение си-

стемы (1) - (2), назовем многошаговой конечной антагонистической игрой (или коротко - динамической матричной игрой).

Протекание игры Г (х0, Т) можно представить следующим образом. Игроки выбирают некоторые стратегии (р1() єФ1, ^2(0 єФ 2. Далее

вычисляется траектория

х(-) = х(-, х0, щ (•), и2 (•)) = {х0, х(1),..., х(Т)}

как решение системы (1) - (2), соответствующее ситуации (и1 (•), и2 (•)). Затем по формуле (5) вычисляется выигрыш игрока I вдоль этой траектории х():

К(х°, (ц (•), (Р2 ()) = Н(х(-Х1,3) = I аи, (х(г)),

г=1

где К, - номера строк и столбцов матрицы

И(Х(V)) , предписанные к-стратегиями ^0, (р2() . Выигрыш игрока II вдоль той же траектории равен

Т

числу - Е ачн (Х(>)).

V=1

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

Пусть игроками выбраны управления и1 (•),

Щ2 ( ) и вычислена соответствующая им траектория Х (•) системы (1) - (2). к-Стратегии соответствующие этим управлениям имеют вид:

^0 = X К Xt = и-Т }

(р2() = {(Щ2(*X ЛX t = и. Т}.

Введем следующие обозначения:

М = {1,...,т}, N = {1,...,п};

М = Мх...хМ, N = #х...х#.

'------V---' '----V----'

Т Т

Определение 2. Последовательность {(К, jt), V = 1,. ., Т} назовем седловой точкой вдоль траектории Х (•), если для любых

{/1,..., 1Т } е А/, {j1,...,]Т } е N выполняются ус-

ловия:

а‘ч1(Х (t)) ^ ац(Х ц)) ^ а-и]1 (Х (t)),

V = 1,...,Т.

Из этого определения следует, что если вдоль траектории Х

не существует.

Множество всех траекторий, вдоль которых существует седловая точка, обозначим символом

X(х 0, Т) (X(х0, Т) с X(х0, Т)).

Для фиксированного V неравенство (8) определяет седловую точку (К, jt) в статической матричной игре Н(Х (V)). Из неравенства (8) получаем: для

всех {/;,...,ц}еМ, ц,..., jT}еN

Е ай, (Х()) ^Е а»и (Х(1)) ^

t=1 t=1

Е %, (Х()).

г=1

Для Х (•) е X(Хо, Т) , число

Т

и

V=1

назовем ценой вдоль траектории Х(•) .

Предположим, что X(Х0, Т) ^ 0 . Каждой

траектории Х (•) е X(х0, Т) соответствует своя

седловая точка {(К, jt), 1 = 1,. Т}. В отличие от статической игры вида h(x(t)), седловые точки, соответствующие разным траекториям из X(Хо, Т),

вообще говоря, не обладают свойствами взаимозаменяемости и эквивалентности. Действительно,

пусть ~(-Х Х(0 е X(xо, Т), а

(<ф (•), ф2 (•)) - соответствующие этим траекториям

стратегии. Нельзя утверждать, что пары { (К, ) } и

{ (^, jt) } образуют седловую точку (невзаимозаме-няемость), так как необязательно траектории х'(-) = х(^, х0, и1(^), г/2 (•)) и

х”(-) = х(^, Х0, Щ (•), и2 (•)) принадлежат множеству X (xо, Т) и нельзя утверждать, что

Еа

t=; t=;

(неэквивалентность).

В общем случае факт «непрямоугольности» множества

Ф1 хф2 = {(ф (•),ф2(•)) | Х(-,х0,Щ (•),Щ (•)) е X(х0,Т)}

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

(ф1 (•), ф2 (•)) еФ1 х Ф2 (причем отклонение понимается как от (и1 (•), и2 (•)), так и от (I, У)) (см. (6)). Это делает бессмысленным применение правила максимина (минимакса) в игре (7) как принципа оптимальности.

Множество Ф1 х Ф2 будет «прямоугольным», а применение принципа максимина содержательным в том случае, если множество X(Х0, Т) будет состоять только из одного элемента, т. е. в игре Г(Х0, Т) будет реализована лишь одна траектория,

вдоль которой существует седловая точка (см. определение 2).

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

Г(Х°, Т) , вытекающая из ее особенностей как

многошаговой матричной игры в классе к-стратегий.

Установлено, что предложенная процедура порождает единственную реализуемую траекторию из

множества X(x0, T) , которая соответствует единственной седловой точке (в классе к-стратегий) в игре Г(x0, T) . Таким образом, в данной работе строго обоснована состоятельность (правомочность) применения правила минимакса (максимина) как принципа оптимального поведения в динамической матричной игре.

Цену игры вдоль траектории можно представить как функцию и(x0, •) : Ф1 х Ф2 ^ R1 (или

и(x°,0: X(x0,T) ^ R1).

Введем в рассмотрение два числа:

и

й(-)еФ1 Р»2 0еФ 2

- нижняя цена игры Г (x0, T) ,

u

%ОеФ 2 Р>2 0еФ2

- верхняя цена игры Г(x0, T) .

Так как множества Ф1 и Ф2 конечные, то экстремумы в (9) и (10) существуют.

к-Стратегии, на которых достигаются внешние экстремумы в (9) и (10), назовем максиминной и минимаксной к-стратегиями первого и второго игроков соответственно.

Можно показать, что в игре Г(x0, T) max min и(x0, pQ, р20) ^

Р0еФ1 Р2 0еФ 2

< min max и

Р20ЕФ 2 Р20еФ 2

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

max min и(x0, pQ, р20) =

Р0еФ1 Р2 0еФ 2

= min max и

Р2 0еФ2 Р>2 0еФ2

порождает устойчивую пару к-стратегий.

Определение 3. Если выполнено равенство (12), то соответствующие ему максиминную и минимаксную к-стратегии назовем оптимальными к-

стратегиями (будем обозначать их рх (•) и р2 (•)) первого и второго игроков, число

и(x0) = и(x“, р* (•),

- ценой игры Г(x0, T) , а пару (р (•), р2 (•) ) будем называть седловой точкой игры Г(x0, T) .

Пусть x*(•) = x(-, x0, и* (•), м2 (•)) - траектория системы (1) - (2), соответствующая седловой

2 / \ ^ / \

точке (ф (•), ф2 (•)). Тогда цена (13) игры Г(Х°, Т) вычисляется так:

и( х 0) = Еatгt* &(Х* ^ ^

V=1

где (К jt ) - седловая точка статической матричной игры Щ(х (V)), V = 1,.,Т.

Для упрощения дальнейших выкладок примем следующие условия:

все матрицы Щ(х), х е G(Х0, Т) , имеют одну и ту же размерность т х п;

для любых V = 1,...,Т мощности множеств

и (и2) одни и те же и равны соответственно ^(г) (т. е. эти множества содержат q и г допустимых значений управляющих параметров).

Любой точке Х^) е G(Х^ — 1), V) и паре

множеств , и2+ соответствуют (в силу системы (1)) q • г точек x(г +1) е G(х(г), V +1). Поэтому мощность множества G(Х^), V +1) равна

(Я • г )t+1.

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

^(0 = {и^1 (1), и^),..., икТ(Т)},

и2()={u2l(1), u22(1),•••, и2Т (Т)Ь

где ик (г) є и'г, и2г (г) є и 2.

Паре управлений (и1(-Х и2(0) =

= {(и1к1(1) ^чт...^(T), и2Т (Т))} соответствует траектория

х(0 = х(% x0, U1(•), и2 ( )) =

= {х0, хад

где

хк,1‘ (г)=х (г, х,-1ІМ (г -1), и1‘ (г), и (г)) є G(x(г -1), г).

Для траектории (14) последовательность {хк'-1І'-1(г -1),..., хк1І1(1)} будем называть предысторией точки хк,1‘ (г) и будем писать:

хк,І‘ (г) = хк,І‘ (г) хк'-1Іг-1 (г -1),..., хкА (1).

В дальнейшем, для удобства, цену игры А будем обозначать символом уаІЛ.

Рис. 1. Соответствие уровневых матриц фазовому дереву игры

Для доказательства существования оптимальных к-стратегий в игре Г(Х0, Т) построим на каждом шаге 1 (V = 1,..., Т) рекуррентное семейство (уровневых) матричных игр и определим их цены:

V(х(г) хкІ (г -1),..., хкІ (1)) = уаІ

уаІИ

V?(х(г)І х(г-1),хкІ(г-2),...,хкІ(1)) = уаІ V(х(г)| хкІ(г-1),...,хкІ(1))||

Кг-1

Ц*-Т

V‘ (x(t) I x(t -1),..., x(1)) = val VU (x(t) | x(t -1),..., x(2), xkl (1)) ||

В соответствии с мощностью множества допустимости г-го уровня G(х(г -1), г) , существует

(д • г)г чисел вида (15), (д • г)г-1 чисел вида (16) и т. д., д • г чисел вида (17) и одно число вида (18).

Последовательность (15) - (18) для каждого фиксированного 1(1 = 1,..., Т) представляет собой систему упорядоченных чисел (цен уровневых матриц), предписанных к вершинам дерева, соответствующего развернутой в фазовом пространстве форме игры. Фрагмент такого дерева (при 1 = 1, 2, 3) приведен на рис. 1.

Лемма 1. Пусть Вк1 = Ъкк - система из

/ тхп

д • г т х п - матричных игр, имеющих седловые точки в чистых стратегиях, к = 1,., g, І = 1,..., г .

уаІВкІ

Тогда в q x r - матричной игре

суще-

ствует седловая точка в чистых стратегиях.

Доказательство. Нижнюю и верхнюю цены

игры

B =

valB

можно представить в виде:

k = 1,..., q.

и далее:

min (valB )< max (valB ), k = 1,..., q ,

l k

l = 1,..., r .

Следовательно, для любой фиксированной пары k и l выполняется неравенство:

min

l i j 1 k i j 1

Так как игра Bkl имеет седловую точку, то (19) можно переписать в виде:

min

l j i j k i j j

Предположим, что внешние экстремумы в (20) достигаются при l = l и k = k . Тогда для всех k = 1,..., q и l = 1,..., r

k l

v(B) = max min (val B ) = max min

k=l,..., q l=l,..., r k=l,..., q l=1,..., r

(max min bkl = min max bkl),

i=l,...,m j=l,...,n j j=l,...,n i=l,...,m j

v (B) = min max (valBkl )=min max

l=l,..., r k=l,..., q l=l,..., r k=l,..., q

i =1,...,m 1=;,...,n j i=;,...,n i=l,...,m j

Предположим, что v(B') ^ v (B) . Так как v(B) ^ v (B) всегда, то наше предположение сводится к неравенству v(B) < v (B).

Из неравенства

max min

k l k l

следует:

min (valBkI )< min min (valBkI),

kl

min max b < max min a

j i j i j

и, в частности,

min max bf < max min ak 1.

j i j г j

Последнее неравенство означает, что

v(Bk2 ) < v(Bel) .

Полученное противоречие говорит о несостоятельности нашего предположения и на самом деле

справедливо равенство v(B) = v (B) . Лемма доказана.

Лемма 2. Если во всех играх h(x), x £ G(x0, T) существуют седловые точки в чистых стратегиях, то существуют все цены (15) - (18) и соответствующие им седловые точки в чистых стратегиях.

Справедливость этого утверждения непосредственно вытекает из леммы 1.

Теорема 1. Если во всех играх h(x),

x £ G(x0, T) существуют седловые точки в чистых стратегиях, то в динамической матричной игре Г(x0, T) существует единственная седловая точка

* / \ * / \

(р, (•), р2 (•)), единственная оптимальная (в

смысле принципа минимакса) траектория x (•) и цена игры в чистых к-стратегиях, вычисляемая по формуле:

val Г(x0, T) = La-, (x (')),

t=1

где { (it jt) , t = 1,..., T } - седловая точка вдоль

траектории x * (•).

Доказательство. На каждом шаге t(t = 1,..., T), последовательно применяя в матричных играх

h(x), x £ G(x(t -1), t),

V (x(t )| (t - 1),..., x“ (1)^| qxr ,

k = 1,..., q , l = 1,..., r ;

VU(.x(t^x(t-1),..., x(2), xkl(1))|| qxr

k = 1,..., q, l = 1,..., r, принцип минимакса, получаем число

V‘(x(t^ x(t-1),..., x(1)) - итоговую цену семей-

qy-r

qr

qr

ства матричных игр ^уровня дерева игры (в фазовом пространстве (см. рис. 1)), которая, согласно лемме

2, существует.

Предысторию точки х(*) = Х (V), соответствующую числу V*(х(*) | х(* — 1),..., х(1)) , обозначим Х*(V — 1),..., Х*(1), Хо, т. е.

х*(0 = х*(7)| х*(V — 1),..., х*(1).

Седловую точку т х п - матричной игры Щ(х*(V)), обозначим (/* j*t ) (по условию теоремы она существует).

По построению последовательности (15) - (18) и исходя из леммы 2, последовательность

{ (/* jt) , V = 1,..., Т } является седловой точкой вдоль траектории Х*(•)= { Х0, Х *(1),..., Х*(Т) }, а цена игры Г(Х0, Т) равна:

val

Г( x", T)- У a,, (x- (t)).

t=1 t t

Допустимые управления, соответствующие траектории Х* (•), обозначим (и* (•), Щ (•)) = = { (щ^), и2(1)), V = 1,..., Т }. Оптимальные стратегии игроков в игре Г(Х0, Т) имеют вид:

фгО=СК 1 = и.Т}, Ф2Г() =

= {(u2(t), h ), t = T },

' / \ / G ' 1

(У (x* (t), T -1) - система (1), определенная на отрезке [t, T], 0;[t, T] и Ф2[t, T] - сужение множеств Ф; и Ф2на отрезке [t, T],

H[t, T]- УЦт, (x(т))).

r=t

Определение 4. Будем говорить, что оптимальная (в смысле принципа минимакса) траектория

x* (•) игры Г(x0, T) динамически устойчива, если

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

1) во всех играх Г( x * (t), T -1),

t = G, 1,..., T существуют цены в чистых

к-стратегиях;

t-1

2) Е а.Г .Г (Х * (т)) + уа/ Г(х * (V), Т — V) =

Т=1

= уа/ Г

Теорема 2. Пусть во всех играх Щ(х), Х е G(Х0, Т) существуют седловые точки в чистых стратегиях. Тогда оптимальная (в смысле принципа минимакса) траектория игры Г(Х0, Т) динамически устойчива.

Доказательство. Выполнение первого условия определения 4 следует из теоремы 1. Покажем выполнения равенства

- (10) и утверждение теоремы 1, можно записать:

V—1

Za.,,(x * (т))+ max min

гт!т р1єФ11, T ] р2єФ 2 ft, T ]

а траектория x * (•) = x(-, x°, u[(•),..., u*2 (•)) оптимальна в смысле принципа минимакса. Теорема доказана.

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

цены игры Г(x0, T) .

В теории игр достаточно примеров, когда принципы оптимальности, определяющие наилучшие исходы (решения) статических игр, будучи примененными в динамических играх, оказываются несостоятельными во времени, т. е. динамически неустойчивыми (см., напр., [4] - [6]).

Для определения принципа динамической устойчивости в игре Г(x0, T) , как обобщения принципа оптимальности Р. Беллмана из теории оптимального управления, погрузим ее в семейство

{Г(x*(t),T-1) , t = 0,1,..., T } аналогичных игр,

определенных вдоль оптимальной траектории x (•). Текущая игра

Г( x-(t), T -1 )= (L (x' (t), T -1);

Ф.Р, T],Ф,[t, T], H[t, T])

отличается от исходной игры Г(x°, T) только начальным состоянием и продолжительностью

т=;

T

v( x “, рр P2) = У au (x *(t)).

Так как условие 1 определения 4 выполнено, то max min v(x0, р, р2) = min

рєФ; tt, T ] р2єФ2 t, T ] р2єФ2 [t, T]

max v(x0, р, р2).

рєФі [,,T ] v

Следовательно, равенство (22) можно переписать в виде:

t-1

У a,, (x * (т)) + max min

ті (і, ,...,iT )єМ[t, T ] (1i,..., j. )є.% T ]

т(x(т)) = (x*(t)),

r=t t=1

где M[t,T] = Mx...xM, iN[t,T] = Л/'x...xN .

4-----V------' 4-----V-----'

T-t T-t

Отсюда, с учетом справедливости условия 1 определения 4, получаем:

t=1

max min

(it ^.^ hT )єM tt ,T ] ( j1,..., jT ^N tt,T ]

У ah . (x(r)) = min max

r (1і,...,jT)єЛТtt,T] (і,,...,t)єМtt,T]

r=t

Tah] т (^

r=t

Следовательно,

=У aiift (x*(t)).

mir (x *(t ^ t -') = У ^ j(x(r)).

r=t

Подставляя выражения для val Г(x* (t),

T -1) и val Г(x0, T) в (21), получаем тождество.

Теорема доказана.

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

Литература

1. Данилов, Н. Н. Представление динамической матричной игры в форме задачи конфликтного управления / Н. Н. Данилов // Вестник КемГУ. -2009. - Вып. 2 (38).

2. Оуэн, Г. Теория игр / Г. Оуэн. - М.: Мир,

1971.

3. Воробьев, Н. Н. Теория игр. Лекции для экономистов-кибернетиков / Н. Н. Воробьев. - Л.: Изд-во ЛГУ, 1974.

4. Петросян, Л. А. Устойчивость решений в дифференциальных играх со многими участниками / Л. А. Петросян // Вестник ЛГУ. - 1977. - № 19.

5. Петросян, Л. А. Кооперативные дифференциальные игры и их приложения / Л. А. Петросян, Н. Н. Данилов. - Томск: Изд-во ТГУ, 1985.

6. Данилов, Н. Н. Кооперативное поведение в динамических системах со многими управлениями / Н. Н. Данилов. - Томск: Изд-во ТГПУ, 2008. - 232 с.

т=,