close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Вестник КемГУ
№2
УДК 518.9
Математика
2009
ПРЕДСТАВЛЕНИЕ ДИНАМИЧЕСКОЙ МАТРИЧНОЙ ИГРЫ
В ФОРМЕ ЗАДАЧИ КОНФЛИКТНОГО УПРАВЛЕНИЯ
Н. Н. Данилов
В работе определяется класс динамических матричных игр, описываемых разностными уравнениями,
вдоль траектории которых задана матрица выигрышей игроков. Вводятся новые понятия стратегии, седловой точки и цена игры. Найдено необходимое и достаточное условие оптимальности стратегий.
In the work the class of dynamic matrix games described by the difference equations, along trajectory of which
the payoff matrix of players is set, is defined. New concepts of strategy, saddle point and game price are introduced.
The necessary and sufficient condition of optimality of strategy is found.
Ключевые слова: матричные игры, модель задачи оптимального управления, стратегии, седловая точка,
значение, игра.
решений системы (1)-(2), которую будем называть
траекторией. Множество всех траекторий системы
Исследования поддержаны грантом «РФФИКузбасс» № 07-01-96022
0
(1)-(2) обозначим X ( x , T ).
Целью игрока I является максимизация значения
функции:
В работе определяется класс динамических матричных игр, описываемых разностными уравнениями, вдоль траектории которых задана матрица выигрышей игроков. Вводятся новые понятия стратегии,
седловой точки и цена игры. Найдено необходимое
и достаточное условие оптимальности стратегий.
Пусть переменная t, которую будем называть
«временем», принимает лишь дискретные значения:
t=0,1,…,T. Рассмотрим некоторую управляемую
систему, изменение состояния которой происходит в
дискретные моменты времени t и описывается уравнением
x(t ) =
f t ( x(t − 1), u1 (t ), u2 (t )), t =
1,..., T
(1)
из заданного начального состояния: x 0 = x(0).
(2)
T
H = ∑ θ ( x(t − 1), u1 (t ), u 2 (t )),
(4)
t =1
где θ − функция, предписывающая этому игроку на
каждом шаге (в каждом состоянии x(t)) его выигрыш
в матричной игре:
 a11t
 t
a
h( x(t )) =  21
 ...
 at
 m1
a12t
t
a 22
...
a mt 2
... a1tn 

... a 2t n 
, t = 1,..., T .
... ... 
t 
... a mn

(5)
В (1)-(2) x(t ) ∈ R − вектор состояния;
(θ ( x 0 ) = 0), где m и n конечные числа.
u1 (t ) ∈ R l1 , u 2 (t ) ∈ R l2 − векторы управления в
Так как в разных состояниях x(t) матрица h(x(t))
разная, то в случае необходимости мы будем записывать aijt = aijt ( x(t )). Целью игрока II является ми-
k
момент t;
f t : R k × R l1 × R l2 → R k − вектор-функция, ха-
нимизация значения функции (4).
Определение 1. Стратегией игрока I (II) будем
называть отображение ϕ1 (ϕ 2 ), которое каждому
шагу t и реализуемому на этом шаге состоянию x(t)
ставит в соответствие некоторое допустимое на этом
шаге управление
u1 (t + 1) ∈ U 1t +1 (u 2 (t + 1) ∈ U 2t +1 ) и номер i (j)
выбранной строки (столбца) матрицы h.
Стратегии игроков можно представить так:
рактеризующая динамические возможности системы.
Предполагается, что управляющие параметры
удовлетворяют условиям:
u1 (t ) ∈ U 1t , u 2 (t ) ∈ U 2t , t = 1,..., T ,
(3)
где U ⊂ R , U ⊂ R − заданные непустые
множества.
Соотношения (1)-(3) определяют дискретную
систему с двумя управлениями. Будем считать, что
выбором управления
t
1
l1
t
2
l2
ϕ1 (⋅) = {(u1 (1), i1 ),..., (u1 (T ), iT )},
ϕ 2 (⋅) = {(u 2 (1), j1 ),..., (u 2 (T ), jT )},
где it è jt − номера выбранных в момент t (в со-
u1 (⋅) = {u1 (1),..., u1 (T )}
распоряжается игрок I, а выбором управления
u 2 (⋅) = {u 2 (1),..., u 2 (T )}
стоянии x(t)) строки и столбца матрицы h(x(t))
(t=1,…,T). Множества стратегий игроков обозначим
соответственно Φ 1 è Φ 2 .
Совокупность
– игрок II. Множества допустимых управлений игроков есть соответственно:
U 1 = U 11 × ... × U 1T , U 2 = U 21 × ... × U 2T .
Предполагается, что каждой паре управлений
(u1 (⋅), u 2 (⋅)) ∈ U 1 × U 2 соответствует единственная
последовательность
Γ( x 0 , T ) =
где
∑ (x
∑ (x
0
); Φ 1 , Φ 2 ; H ,
(6)
) − символическое обозначение системы
(1)-(2), назовем многошаговой конечной антагони-
x(⋅) = {x 0 , x(1), ..., x(T )}
39
0
Вестник КемГУ
№2
стической игрой (или коротко – динамической матричной игрой).
Протекание игры Γ( x 0 , T ) можно представить
следующим образом. Игроки выбирают некоторые
стратегии – ϕ1 (⋅) ∈ Φ 1 , ϕ 2 (⋅) ∈ Φ 2 . Далее вычисляется траектория
x(⋅) = x( x 0 , u1 (⋅), u 2 (⋅)) = {x 0 , x(1),..., x(T )} как
решение системы (1)-(2), соответствующее ситуации
(ϕ1 (⋅), ϕ 2 (⋅)). Затем по формуле (4) вычисляется
aitt jt ( x (t )) ≤ aitt jt ( x (t )) ≤ aitt jt ( x (t )),
Из этого определения следует, что если вдоль
траектории x(⋅) = {x 0 , x(1),..., x(T )} в какой-то из
моментов t=1,…,T неравенство (7) не выполняется,
т. е. в статической матричной игре h(x(t)) нет седловой точки, то седловая точка вдоль траектории x(⋅)
не существует.
Множество всех траекторий, вдоль которых существует седловая точка, обозначим символом
Χ ( x 0 , T ) ( Χ ( x 0 , T ) ⊂ Χ( x 0 , T )).
Для фиксированного t неравенство (7) определяет седловую точку (it , j t ) в статической матричной
T
H = H ( x 0 , ϕ1 (⋅), ϕ 2 (⋅)) = K ( x(⋅)) = ∑ aitt jt ,
t =1
где
a
− элемент матрицы h(x(t)), предопределен-
игре h( x (t )). Таким образом, существование седло-
ный стратегиями ϕ1 (⋅) è ϕ 2 (⋅).
Выигрыш игрока II вдоль этой же траектории
равен числу −
вой точки вдоль траектории x (⋅) предполагает существование седловых точек во всех матричных
играх h( x (t )), t = 1,..., T .
Из неравенства (7) получаем: для всех
T
∑a
t =1
t
it jt
.
{i1 ,..., iT } ∈ Ιˆ, { j1 ,..., jT } ∈ Jˆ
В классической теории игр изучаются так называемые матричные игры. С практической точки зрения, матричная игра – это статическая математическая модель, с помощью которой можно определить
оптимальное поведение двух конфликтующих сторон, имеющих противоположные интересы и конечное число стратегий (решений, альтернатив). Матричные игры имеют достаточно широкое применение (см., напр., [1-4]). Поскольку процессы принятия решения в социально-экономических и других
системах имеют динамический характер, то возникает необходимость обобщения класса матричных
игр так, чтобы учитывались временные факторы.
Игра вида (6) и представляет такое обобщение.
В данной статье исследуется вопрос о принципе
оптимальности в игре Γ( x 0 , T ) : как себя должны
вести игроки, чтобы получить как можно большие
выигрыши?
Пусть
игроками
выбраны
управления
u1 (⋅), u 2 (⋅) и вычислена соответствующая им тра-
T
∑a
t =1
T
t =1
t =1
T
t =1
(8)
t t
назовем ценой игры вдоль траектории x (⋅).
Предположим, что Χ ( x 0 , T ) ≠ ∅. Каждой траектории x (⋅) ∈ Χ ( x 0 , T ) соответствует своя седловая
точка (ϕ1 (⋅), ϕ 2 (⋅)). В отличие от статической игры
вида h(x(t)), седловые точки, соответствующие разным траекториям из Χ ( x 0 , T ), вообще говоря, не
обладают свойствами взаимозаменяемости и эквивалентности. Действительно, пусть
~x (⋅), xˆ (⋅) ∈ Χ ( x 0 , T ), а (ϕ~ (⋅), ϕ~ (⋅)), (ϕˆ (⋅), ϕˆ (⋅)) −
1
2
1
2
соответствующие седловые точки. Нельзя утверждать, что пары (ϕ~1 (⋅), ϕˆ 2 (⋅)) è (ϕˆ1 (⋅), ϕ~2 (⋅)) образуют
седловую точку (взаимозаменяемость), так как необязательно траектории
x′(⋅) = x( x 0 , u~1 (⋅), uˆ2 (⋅))
x′′(⋅) = x( x , uˆ1 (⋅), u~2 (⋅))
принадлежат множеству
0
Введем следующие обозначения:
и
Χ ( x , T ) и нельзя утверждать, что
=
Ι {1,...,
=
m}, J {1,..., n};
Ιˆ =Ι
× ... × Ι , Jˆ =
J
×
J.
... ×
2.
T
( x (t )) ≤ ∑ a itt jt ( x (t )) ≤ ∑ a itt jt ( x (t )).
υ ( x 0 , ϕ1 (⋅), ϕ 2 (⋅)) = ∑ ait j ( x (t ))
ϕ1 (⋅) = {(u1 (t ), it ), t = 1,..., T },
ϕ 2 (⋅) = {(u 2 (t ), j t ), t = 1,..., T }.
T
t
it jt
Для x (⋅) ∈ Χ ( x 0 , T ) число
ектория x (⋅) системы (1)-(2). Стратегии, соответствующие
этим
управлениям,
имеют
вид:
Определение
(7)
t = 1,..., T .
выигрыш игрока I вдоль этой траектории x(⋅) :
t
it jt
Математика
2009
0
T
T
t =1
t =1
∑ a~itt ˆjt ( x′(t )) = ∑ aiˆtt ~jt ( x′′(t ))
T
Пару
стратегий
назовем седловой точкой
(ϕ1 (⋅), ϕ 2 (⋅)) ∈ Φ 1 × Φ 2
игры вдоль траектории x (⋅), если существуют такие
(эквивалентность). По этой причине множество всех
седловых точек, соответствующих траекториям из
множества Χ ( x 0 , T ), будем обозначать символом
{i1 ,..., iT } ∈ Ιˆ, { j1 ,..., jT } ∈ Jˆ ,
{i1 ,..., iT } ∈ Ιˆ, { j1 ,..., jT } ∈ Jˆ вы-
Φ (а не Φ1 × Φ 2 , т. к. не все пары из этого множества будут седловыми точками). Из всего сказанного выше следует, что цену игры вдоль траектории
можно представить как функцию
последовательности
что для любых
полняются условия
40
Вестник КемГУ
№2
υ ( x 0 ,⋅) : Φ → R 1 .
гда, когда для любых ϕ1 (⋅) ∈ Φ1 , ϕ 2 (⋅) ∈ Φ 2 выполнены неравенства
υ ( x 0 , φ1 (⋅), φ2* (⋅)) ≤ υ ( x 0 , φ1* (⋅),
(14)
φ2* (⋅)) ≤ υ ( x 0 , φ1* (⋅), φ2 (⋅)).
Доказательство.
Необходимость.
Пусть
(ϕ1* (⋅), ϕ 2* (⋅)) − седловая точка игры Γ( x 0 , T ). По
определению 3,
Введем в рассмотрение два числа:
υ ( x 0 ) = max min υ ( x 0 , ϕ1 (⋅), ϕ 2 (⋅))
ϕ1 (⋅)∈Φ1 ϕ 2 (⋅)∈Φ 2
(9)
- нижняя цена игры Γ( x 0 , T ),
0
0
υ ( x ) = min max υ ( x , ϕ1 (⋅), ϕ 2 (⋅))
ϕ 2 (⋅)∈Φ 2 ϕ1 (⋅)∈Φ1
Математика
2009
(10)
υ ( x 0 , φ1* (⋅), φ2* (⋅)) =
– верхняя цена игры Γ( x 0 , T ) (здесь Φ1 ( Φ 2 ) −
=
множество всех стратегий первого
(второго) игрока,
max min =
υ ( x 0 , φ1 (⋅), φ2 (⋅))
φ1 ( ⋅ )∈Φ1 φ2 ( ⋅ )∈Φ 2
(15)
входящих в Φ ).
=
min max υ ( x 0 , φ1 (⋅), φ2 (⋅))
В дальнейшем, для простоты, будем
предполаφ2 ( ⋅ )∈Φ 2 φ1 ( ⋅ )∈Φ1
гать, что экстремумы в (9) и (10) существуют (в прои внешние экстремумы достигаются на стратегиях
тивном случае, вместо «седловой точки» следует
ϕ1* (⋅), ϕ 2* (⋅).
говорить о « ε - седловой точке»).
Пусть внутренний экстремум в левой части
Стратегии, на которых достигаются внешние
экстремумы в (9) и (10), назовем максиминной и (15) достигается на стратегии ϕ 2′ (⋅) :
минимаксной стратегиями первого и второго игроmax min υ ( x 0 , φ1 (⋅), φ2 (⋅)) =
ков соответственно.
φ1 ( ⋅)∈Φ1 φ2 ( ⋅)∈Φ 2
Можно показать, что в игре Γ( x 0 , T )
= max υ ( x 0 , φ1 (⋅), φ2′ (=
⋅)) υ ( x 0 , φ1* (⋅), φ2′ (⋅)).
max min υ ( x , φ1 (⋅), φ2 (⋅)) ≤
0
φ1 ( ⋅ )∈Φ1 φ2 ( ⋅ )∈Φ 2
≤ min max υ ( x 0 , φ1 (⋅), φ2 (⋅))
φ1 ( ⋅)∈Φ1
Из последнего равенства получаем:
(11)
υ ( x 0 , ϕ1 (⋅), ϕ 2′ (⋅)) ≤ υ ( x 0 , ϕ1* (⋅), ϕ 2′ (⋅))
для всех ϕ1 (⋅) ∈ Φ1 .
φ2 ( ⋅ )∈Φ 2 φ1 ( ⋅ )∈Φ1
и в случае строгого неравенства в (11) максиминная
и минимаксная пары стратегий не являются устойчивыми против индивидуальных отклонений игроков от нее. Напротив, равенство
(16)
Пусть внутренний экстремум в правой части (15)
достигается на стратегии ϕ1′ (⋅) :
min max υ ( x 0 , φ1 (⋅), φ2 (⋅)) =
max min υ ( x 0 , φ1 (⋅), φ2 (⋅)) =
φ1 ( ⋅ )∈Φ1 φ2 ( ⋅ )∈Φ 2
min max υ ( x 0 , φ1 (⋅), φ2 (⋅)),
φ2 ( ⋅)∈Φ 2 φ1 ( ⋅)∈Φ1
(12)
=
φ2 ( ⋅ )∈Φ 2 φ1 ( ⋅ )∈Φ1
Из последнего равенства получаем:
как будет показано ниже, порождает устойчивую
пару стратегий.
Определение 3. Если выполнено равенство (12),
то соответствующие ему максиминную и минимаксную стратегии назовем оптимальными стратегиями (будем обозначать их ϕ1* (⋅) è ϕ 2* (⋅) ) первого
*
2
точкой игры Γ( x 0 , T ), а число
υ ( x 0 ) = υ ( x 0 , ϕ 1* (⋅), ϕ 2* (⋅)) = υ ( x 0 ) = υ ( x 0 ) –
для всех
(13)
ϕ1 (⋅) ∈ Φ1 , ϕ 2 (⋅) ∈ Φ 2 . Отсюда (15), (18):
υ ( x 0 , φ1 (⋅), φ2* (⋅)) ≤
*
2
≤ υ ( x 0 , φ1* (⋅), φ2* (⋅)) ≤ υ ( x 0 , φ1* (⋅), φ2 (⋅))
для всех ϕ1 (⋅) ∈ Φ1 , ϕ 2 (⋅) ∈ Φ 2 .
Достаточность. Пусть выполнены неравенства
(14). Левое неравенство в (14) верно для всех
T
υ(x ) = ∑ a
0
t =1
*
t
it* jt*
(18)
= υ ( x 0 , φ1′(⋅), φ2* (⋅)) ≤ υ ( x 0 , φ1′(⋅), φ2 (⋅))
Пусть x (⋅) = x( x , u (⋅), u (⋅)) − траектория
системы (1)-(2), соответствующая седловой точке
(ϕ1* (⋅), ϕ 2* (⋅)). Тогда цена (13) вычисляется как:
*
1
υ ( x 0 , ϕ1* (⋅), ϕ 2′ (⋅)) = υ ( x 0 , ϕ1′ (⋅), ϕ 2* (⋅)) .
υ ( x 0 , φ1 (⋅), φ2′ (⋅)) ≤ υ ( x 0 , φ1* (⋅), φ2′ (⋅)) =
ценой игры Γ( x , T ).
0
(17)
Применяя (16) и (17), напишем:
0
*
υ ( x 0 , ϕ1′ (⋅), ϕ 2 (⋅)) ≥ υ ( x 0 , ϕ1′ (⋅), ϕ 2* (⋅))
для всех ϕ 2 (⋅) ∈ Φ 2 .
По условию (15):
и второго игроков, пару (ϕ (⋅), ϕ (⋅)) − седловой
*
1
min υ ( x 0 , φ1′(⋅), φ=
υ ( x 0 , φ1′(⋅), φ2* (⋅)).
2 (⋅))
φ2 ( ⋅)∈Φ 2
*
( x (t )),
ϕ1 (⋅) ∈ Φ1 .
*
где ( i t j t ) − седловая точка статической матричной
Поэтому
max υ ( x 0 , ϕ1 (⋅), ϕ 2* (⋅)) ≤ υ ( x 0 , ϕ1* (⋅), ϕ 2* (⋅)).
игры h( x * (t )), t = 1,..., T .
ϕ1 (⋅)∈Φ1
Теорема. Пара стратегий (ϕ1* (⋅), ϕ 2* (⋅)) является
Поскольку для всех
седловой точкой игры Γ( x 0 , T ) тогда и только то41
ϕ 2 (⋅) ∈ Φ 2
(19)
Вестник КемГУ
№2
2009
ве определения оптимальных стратегий игроков в
игре Γ( x 0 , T ).
Соотношения (13) и (14) представляют собой
обобщение принципа минимакса, используемого в
статических матричных играх в качестве правила
выбора оптимальных стратегий.
Из теории матричных игр известно, что если в
игре h(x(t)) нижняя цена не равна верхней цене, то
седловая точка отсутствует. В таких случаях существование оптимальных стратегий достигается путем введения смешанных стратегий. Поэтому естественным является определение и изучение смешанного расширения игры Γ( x 0 , T ). Ввиду ограниченности объема данной статьи, результаты исследования игры Γ( x 0 , T ) в классе смешанных стратегий здесь не приводятся.
min max υ ( x 0 , φ1 (⋅), φ2 (⋅)) ≤
φ2 ( ⋅ )∈Φ 2 φ1 ( ⋅ )∈Φ1
≤ max υ ( x 0 , φ1 (⋅), φ2 (⋅)),
φ1 ( ⋅ )∈Φ1
то, в частности,
min
max υ ( x 0 , φ1 (⋅), φ2 (⋅)) ≤
φ2 ( ⋅ )∈Φ 2 φ1 ( ⋅ )∈Φ1
≤ max υ ( x 0 , φ1 (⋅), φ2* (⋅)).
φ1 ( ⋅ )∈Φ1
Получили (19):
min
max υ ( x 0 , φ1 (⋅), φ2 (⋅)) ≤
φ2 ( ⋅ )∈Φ 2 φ1 ( ⋅ )∈Φ1
≤ υ ( x 0 , φ1* (⋅), φ2* (⋅)).
(20)
Рассмотрим теперь правую часть (14) и, рассуждая аналогично, получаем:
υ ( x 0 , φ1* (⋅), φ2* (⋅)) ≤
≤ max min υ ( x 0 , φ1 (⋅), φ2 (⋅)).
Математика
Литература
1. Нейман, Дж. Теория игр и экономическое поведение / Дж. Нейман, О. Моргенштерн – М.: Наука,
1970. – 707 с.
2. Оуэн, Г. Теория игр / Г. Оуэн. – М.: Мир,
1971. – 230 с.
3. Воробьев, Н. Н. Теория игр. Лекции для экономистов-кибернетиков / Н. Н. Воробьев. – Л.: Издво ЛГУ, 1974. – 160 с.
4. Данилов, Н. Н. Теоретико-игровое моделирование конфликтных ситуаций / Н. Н. Данилов. –
Томск: Изд-во Томск. ун-та, 2005. – 119 с.
5. Данилов, Н. Н. Основы математической теории оптимальных процессов / Н. Н. Данилов,
В. В. Мешечкин. – Кемерово: Кузбассвузиздат,
2004. – 219 с.
(21)
φ1 ( ⋅ )∈Φ1 φ2 ( ⋅ )∈Φ 2
Сравнение (20) и (21) показывает, что
min max υ ( x 0 , φ1 (⋅), φ2 (⋅)) ≤
φ2 ( ⋅ )∈Φ 2 φ1 ( ⋅ )∈Φ1
≤ max min υ ( x 0 , φ1 (⋅), φ2 (⋅)).
φ1 ( ⋅ )∈Φ1 φ2 ( ⋅ )∈Φ 2
Но всегда справедливо неравенство (11), так что
в последнем соотношении имеет место строгое равенство, следовательно, (ϕ1* (⋅), ϕ 2* (⋅)) − седловая
точка игры Γ( x 0 , T ). Теорема доказана.
Неравенство (14) наглядно показывает устойчивость пары стратегий (ϕ1* (⋅), ϕ 2* (⋅)) против индивидуальных отклонений игроков: игрок, выбравший
другую стратегию (при условии, что противник
придерживается стратегии «со звездочкой»), наказывает разве что себя. Поскольку неравенство (14)
более соответствует свойству седловой точки, чем
определение 3, то его можно использовать в качест-
Рецензент – В. Я. Карташов – д-р техн. наук,
профессор, ГОУ ВПО «Кемеровский государственный университет».
42
Документ
Категория
Без категории
Просмотров
5
Размер файла
186 Кб
Теги
игры, матричное, конфликтной, управления, представление, задачи, формы, динамическое
1/--страниц
Пожаловаться на содержимое документа