Петросян Л.А. и др. Теория игр
Подождите немного. Документ загружается.
ляет осуществить попятную рекуррентную процедуру нахождения
значения игры и оптимальных стратегий игроков. Действительно,
пусть значения всех подыгр T
z
длиной
l(z)^k—
1
известны и равны
v(z),
пусть Г,, — некоторая подыгра длины
1(у)
= к. Тогда если
уеХ
1г
то v(y) определяется по формуле (3.3), если
же
уеХ
2
,
то v(y)
находится по формуле (3.4). При этом значения функции v(z)
в формулах (3.3), (3.4) известны, поскольку соответствующие подыг-
ры имеют длину не более чем
fe—
1. Эти же формулы указывают
способ построения оптимальных стратегий игроков. Действитель-
но,
если
уеХ
и
то игрок 1 (максимизирующий) должен выбрать
в точке у вершину
zeF
y
,
для которой значение следующей подыгры
максимально. Если
жеуеХ
2
,
то игрок 2 (минимизирующий) должен
выбрать позицию
zeF
y
,
для которой значение следующей подыгры
минимально.
В случае, когда выборы игроков в антагонистической многоша-
говой игре чередуются (поочередная игра), уравнения (3.3), (3.4)
могут быть записаны в виде одного уравнения. Действительно,
рассмотрим подагру Г, и пусть, для определенности,
хеХ
х
.
Тогда
в следующей позиции ходит игрок 2 или эта позиция является (игра
поочередная) окончательной, т. е. F
x
с Х
2
\J X
3
. Поэтому можно
записать
v
(x)=max
v
(у),
xeX
t
;
(3.6)
yeF
x
v(y)=mmv(z),yeF
x
czX
2
[jX
z
. (3.7)
zeFy
Подставляя (3.7) в (3.6), получаем
v(х)=max [min
v(z)],
xeX
v
(3.8)
yeF
x
zeF
y
Если
хеХ
2
,
то аналогично имеем
v
(x)=min [max
v
(z)].
(3.9)
yeF
x
zeF
y
Уравнения (3.8), (3.9) эквивалентны и должны рассматриваться
с начальным условием
« (х)
|,
6
^
2
=Н
1
(х).
3.4. Теорема п.
2.1,
рассматриваемая применительно к антагони-
стическим поочередным многошаговым играм, позволяет утверж-
дать существование ситуации равновесия в «шахматах», «шашках»,
в классе чистых стратегий, а уравнения (3.8), (3.9) показывают путь
для нахождения значения игры. Вместе с тем очевидно, что никогда
в обозримом будущем решение указанных функциональных уравне-
ний для нахождения значения игры и оптимальных стратегий не
будет реализовано на ЭВМ и мы так и не узнаем, может ли
190
какой-либо игрок «белый» или «черный» гарантировать победу
в любой партии или всегда возможна «ничья»? Однако в шахматах
и шашках делаются небезуспешные попытки построения прибли-
женно оптимальных решений путем создания программ, думающих
на несколько шагов вперед, и использования всевозможных (полу-
ченных, как правило, эмпирическим путем) функций оценки текущих
позиций. Такой подход возможен и при исследовании общих ан-
тагонистических многошаговых игр с полной информацией. После-
довательное итерирование оценочных функций на несколько шагов
вперед может привести к желательным результатам.
§ 4. СТРАТЕГИИ НАКАЗАНИЯ
4.1.
В п. 2.1 доказано существование ситуации абсолютного
равновесия (по Нэшу) в многошаговых играх с полной информаци-
ей на конечном древовидном графе. В то же время при исследова-
нии конкретных игр этого класса можно обнаружить целое семейст-
во ситуаций равновесия, сужения которых необязательно являются
ситуациями равновесия во всех подаграх исходной игры. К числу
таких ситуаций равновесия относятся равновесия в стратегиях нака-
зания. Проиллюстрируем это понятие на примере.
Пример 5. Пусть игра Г происходит на графе, изображенном на
рис.
19. Множество N={1, 2} состоит из двух игроков. Как и в при-
мере п. 2.2, на рис. 19 кружками изображены вершины, состав-
ляющие множество Х
и
квадратиками — множество Х
2
. Вершины
графа перенумерованы двойными индексами, дуги — одинарными.
Нетрудно убедиться в том, что ситуация
и\
=
{\,
1, 2, 2, 2), и*
2
=
{\,
1) является абсолютно равновесной в игре Г. При этом выигрыши
игроков равны 8 и 2 единиц соответственно. Рассмотрим теперь
ситуацию й
1
=
(2,
1, 2, 1, 2), й
2
=
(2,
2). В этой ситуации выигрыши
игроков равны соответственно 10
и 1, тем самым игрок 1 получает
больше, чем в ситуации (и
и
и'
2
).
Ситуация (t/j,
Й
2
)
является равно-
весной в игре Г, но не является
абсолютно равновесной. Действи-
тельно, в подагре Г
х 4
сужение
стратегии Л
х
диктует игроку
1
вы-
бор левой дуги, что не является
для него оптимальным в позиции
1.4. Такое действие игрока 1 в по-
зиции 1.4 можно интерпретиро-
вать как угрозу «наказания» игро-
ка 2, если он отклонится от жела-
тельного для игрока 1 выбора ду-
ги 2 в позиции 2.2, лишив тем
о
ш»
(?)
it)
am
w
191
самым игрока
1
максимального выигрыша
10
единиц. Однако
по
существу такую угрозу «наказания» едва
ли
следует считать дейст-
венной, поскольку наказывающий (игрок
1) при
этом
сам
может
потерять
в
выигрыше пять единиц (действуя не оптимально
в Г\ J.
4.2.
Дадим строгое определение стратегий наказания.
Для
про-
стоты ограничимся случаем неантагонистической игры двух
лиц.
Пусть задана неантагонистическая многошаговая игра двух
лиц
r
=
<U
v
U
2
,K
v
K
2
).
С игрой
Г
свяжем
две
антагонистические игры
Г
2
и Г
2
следующим
образом. Игра
Г
х
— это антагонистическая игра, построенная
на
основе игры
Г, в
которой игрок
2
играет против игрока
1, т. е.
К
2
=—К
1
. Игра
Г
2
— это антагонистическая игра, построенная
на
основе игры
Г, в
которой игрок
1
играет против игрока
2, т. е.
К
1
=
—К
2
-
Графы
игр Г
15
Г,, Г и
множества стратегий
в них
совпадают. Обозначим через (и\
х
,
и
21
)
и
(и'
п
,
и'
22
)
ситуации абсолют-
ного равновесия
в
играх
1\ и Г
2
соответственно. Пусть
T
ix
, Г
2х
—
подыгры
игр Г\, Г
2
;
v
t
(x), v
2
(x)— значения этих подыгр. Тогда
ситуации {(и'ц)
х
, (u
2i
)
x
}
и
{(и*
п
)
х
,
(«и)*} являются равновесными
в играх
Г
и
, Гг*
соответственно
и
v
1
(x)=K
x
((u*
n
)
x
,
(и*
21
)
х
),
«
2
(х)=^((
М
;
2
)
1
,(и
22
)
1
).
Рассмотрим произвольную пару
(u
v
u
2
)
стратегий
в
игре
Г.
Разумеется,
эта
пара стратегий является таковой
и в
играх
Г
и
Г,.
Пусть Z=(x
0
=z
0
,
z
v
.... zi)
— путь, реализуемый в ситуации
(u
v
и
2
).
Определение.
Стратегия
й
х
(-)
называется стратегией
нака-
зания
игрока
1,
если:
й
х
(z*)=z
k+
,
для
z
k
6
Z(]X
t
, (4.1)
"i (у)
= Щг(У)
Для
yeX
v
уфг.
Стратегия
й
2
(*)
называется стратегией наказания игрока
2,
если:
й
2
(z
k
)=г
к+1
дпяг
к
е
Zf]X
2
, (4.2)
"2 (У) = "2i
(У)
Для у
е
Х
2
,
у фZ.
4.3.
Из
определения стратегий наказания сразу получаем следу-
ющие свойства:
1°.
^(2i(-)), u
2
(-))=^(z,),
^(u^-),
u
2
(-)) =
H
2
(z,).
2°.
Пусть один
из
игроков, например игрок
1,
использует страте-
гию
!<!
(•
)>
Для которой позиция
z
k
eZf]X
x
является первой в пути
Z,
где
иД-)
диктует выбор следующей позиции
t
z'
k+u
отличной
от
выбора, диктуемого стратегией
и^), т. е.
z'
k+
i^z
k+i
. Тогда
из
192
определения наказывающей стратегии
й
2
(•) следует, что
*!(«!(),
й
2
(-)Х«>1Ы- (4-3)
Аналогично, если игрок 2 использует стратегию ы
2
(")
лля
которой
позиция
z
k
eZ(~]X
2
является первой в пути Z, где и
2
(') диктует
выбор следующей позиции
z'
k+u
отличной от диктуемой стратегией
й
2
('),
т. е.
z'lc+i^Zk+i,
то из определения наказывающей стратегии
йл
(•) следует, что
^(SiOWO)^**)- (4-4)
Отсюда, в частности, получаем следующую теорему.
Теорема. Пусть
(2
Х
(•), и
2
()) —
ситуация
в стратегиях нака-
зания.
Для
равновесности ситуации
(ы
1
(-), м
2
('))
достаточно,
что-
бы
для всех fc=0, 1, ..., /—1
выполнялись неравенства
КЛйЛ-Х
u
2
(-))>
Vl
(z
k
), (4.5)
#
2
("i(
-
), u
2
(-))>v
2
(z
k
),
где
z
0
, z
1(
.... z
t
—
путь,
реализовавшийся
в
ситуации
(й^
(•), и
2
(•)).
4.4.
Пусть и'ц(-) и Ми(') — оптимальные стратегии игроков
1 и 2 во вспомогательных антагонистических играх Г
1
и Г
2
соответ-
ственно и Z =
{z
0
,
z
lf
.... z,}—путь, соответствующий ситуации
(и'ц
(•),
Ии
(•
^Предположим, что стратегии наказания t^ (•) и й
2
(•)
таковы, что м
1
(г
л
) = м1,(5
л
) для
z
k
eZf]X
t
и й
2
(г*) = Ы22&) для
z
k
eZf]X
2
.
Тогда ситуация («].(•)» й
2
(-)) образует ситуацию равно-
весия по Нашу в стратегиях наказания. Для доказательства этого
утверждения достаточно показать, что
К, («;,(•), t4())=*i(2i(-), 5
2
(-))>«i&), (4-6)
K
2
(UnC),
и
22
(-))=К
2
{й
1
{-), й
2
(-))>*2&)>
fc=0, l,
.../-1,
и воспользоваться теоремой п. 4.3. Неравенства (4.6) следуют из
оптимальности стратегий м1
]
(-)им
22
(')
в
играх Г\ и Г
2
соответст-
венно, обоснование предлагаем в качестве упражнения. Таким об-
разом, получена следующая теорема.
Теорема. В игре Г всегда существует ситуация равновесия
в
стратегиях
наказания,
при этом выигрыши
в
этой ситуации равны
^|(
м
п(")>
м
22('))> где м*,(-) и
и\
2
{')
—
оптимальные стратегии
иг-
роков 1 и 2 во
вспомогательных антагонистических
играх Г
х
и Г
2
соответственно.
193
Смысл стратегий наказания заключается в том, что игрок заста-
вляет партнера придерживаться определенного пути в игре (опреде-
ленных выборов), используя постоянную угрозу переключения на
стратегию, оптимальную в антагонистической игре против партне-
ра. Множество ситуаций равновесия в классе стратегий наказания
достаточно представительно, однако эти стратегии не следует счи-
тать очень «хорошими», поскольку, наказывая партнера, игрок
может еще сильнее наказать самого себя.
§ 5. ИЕРАРХИЧЕСКИЕ ИГРЫ
Важнейшим подклассом неантагонистических многошаговых
игр являются иерархические игры. Иерархические игры моделируют
конфликтно управляемые системы с иерархической структурой. Та-
кая структура определяется последовательностью уровней управле-
ния, следующих друг за другом в порядке определенного приорите-
та. В математической постановке иерархические игры классифици-
руются по числу уровней и характеру вертикальных связей. Про-
стейшей из них является двухуровневая система, схема которой
изображена на рис. 20.
5.1.
Двухуровневая конфликтно управляемая система функци-
онирует следующим образом. Управляющий (координирующий)
центр А
0
, находящийся в первом уровне иерархии, выбирает вектор
u=(u
1
,...,
м„)
из заданного множества управлений U, где u
t
— управ-
ляющее воздействие центра на подчиненные ему подразделения Д,
/=1,
2, ..., п, находящиеся на втором уровне иерархии. В свою
очередь, Д, i= 1, ..., и, выбирают управления «,е Г,(и,), где Vi(u,) —
множество управлений подразделения Д, предопределенное управ-
лением и центра А
0
. Таким образом, управляющий центр имеет
право первого хода и может ограничивать возможности подчинен-
ных ему подразделений, направляя их действия в нужное русло.
Цель центра А
0
заключается в максимизации по и функционала
К
0
(и,
v
u
..., «„), а подразделения Д, /= 1,..., п, обладая собственными
целями, стремятся максимизировать по
v, функционалы
A,
(u„ v,).
5.2. Формализуем эту задачу как беско-
алиционную игру Г(л+1)-го лица (админи-
стративного центра А
0
и производственных
подразделений B
it
.... В„) в нормальной
форме.
Пусть игрок А
0
выбирает вектор ueU,
где
U={u
=
{u
v
.... u„):Ui>0, UteR
1
, /=1, ..., n,
194
Рис. 20
— множество стратегий игрока А
0
в игре Г. Вектор щ будем ин-
терпретировать как набор ресурсов / наименований, выделяемых
центром А
0
для i'-го производственного подразделения.
Пусть в исходной задаче п. 5.1 каждый из игроков Д, зная выбор
А
0
,
выбирает вектор v
t
e
Vi(ui),
где
VAud^faelfivtA^Ut+a,, v,>0}. (5.1)
Вектор v, интерпретируется как производственная программа 1-го
производственного подразделения по различным видам продукции;
A
t
— производственная или технологическая матрица i-ro произ-
водственного подразделения (4,^0);
<х
(
— вектор наличных ресурсов
г-го производственного подразделения (<х,^0).
Под стратегиями игрока Д в игре Г будем понимать множество
функций
»,(•)>
ставящих в соответствие каждому элементу
ы,:
(ы
1(
...,
«,, .... м„)е
Uвектор
»,(ы
;
)е
V
t
(ui).
Множество таких функций
будем обозначать через
V„
i=l, ..., п.
Определим функции выигрышей игроков в игре Г. Для игрока А
0
функция выигрыша имеет вид
л
Ко(и,
«!(•), ...,«»(•))= Е *
»'("')>
где в,>0, a
t
eR
m
— фиксированный вектор, /=1, ..., л;
a
(
Vi(Ui)
— ска-
лярное произведение векторов а, и
к,(и
(
).
Функцию выигрыша игрока
Д полагаем равной
Ki(u, V^), ..., V
n
()) = CiV,(u,),
где с,>0, Cje.R
m
— фиксированный вектор, i=l, ..., и.
Таким образом, игра Г имеет вид Г=(С/, V
v
....
F„,
K
0
, K
v
.... .£„).
5.3.
Построим ситуацию равновесия по Нэшу в игре Г.
Пусть
ю,*(м
(
)е
Vt(u,)
— решение задачи параметрического линей-
ного программирования (параметром является вектор ц)
max
С/
«
г
=с,
«*
(«О,
i=
1,
..., л, (5.2)
t)(eK,(uj)
195
а
и*
£ U
— решение задачи
max K
0
(и, v\(•), ...,
v'„(.)).
(5.3)
lieU
Для простоты предполагаем, что максимумы в (5.2) и (5.3)
достигаются. Заметим, что (5.3) — задача нелинейного програм-
мирования с существенно разрывной целевой функцией (максимиза-
ция ведется по и, a v'(u,), вообще говоря, — разрывные функции
параметра и,). Покажем, что точка (и*, «[(•), ...,
v*
n
())
является
ситуацией равновесия в игре Г. Действительно,
К
0
(и*.
v\0, ..., v*())>K
0
(u,
.;(.),
..., «JO), ue U.
Далее, при всех /=
1,
..., п справедливо неравенство
К,(и*.
«!(•), ...,
v'„())
= c
t
v'i(u')^Ci
«,(«*)
=
=K
t
(u*,
•!(.),
..., «*-i(), «<(•), «*+i(), -.,
v'„())
для любой
»,(•)£
V
t
.
Таким образом, никому из игроков А
0
, В
х
, ....
В
и
невыгодно в одностороннем порядке отклоняться от ситуации
(и*.
«!(•), -ч ««(•))>
т
-
е
-
она
является равновесной. Заметим, что эта
ситуация также устойчива против отклонения от нее любой ко-
алиции Sc{B
l
,....
В„},
поскольку выигрыш K
t
i-ro
игрока не зависит
от стратегий vj(),je{l,
...,
n},j¥=i.
§ 6. ИЕРАРХИЧЕСКИЕ ИГРЫ (КООПЕРАТИВНЫЙ ВАРИАНТ)
В этом параграфе рассматривается кооперативный вариант ряда
простейших иерархических игр (в том числе игры, определенной
в п. 5.1, 5.2). Строятся характеристические функции и исследуются
условия существования непустого С-ядра.
6.1.
Исходя из содержательного смысла задачи п. 5.1, 5.2 и с ис-
пользованием стратегией, образующих равновесие по Нэшу, для
каждой коалиции
S<=.N=
{А
0
, B
v
.... В„}
определим
ее
гарантирован-
ный доход
v (S)
следующим образом:
' 0, если S=
{A
0
};
(6.1)
£ с/»?(0), если Л
0
#Я (6.2)
v(S)=i IBieS
max £
(cii+Ct)
v*(ud,
если А
0
еS, (6.3)
{«el/: £ «i=*}
i-BjeS
» i:BeS
196
где
v*(u,),
i= 1,..., и — решение задачи параметрического линейного
программирования (5.2).
Равенство (6.1) имеет место, поскольку коалиция {B
lt
..., В„}
может добиться получения нулевого выигрыша игроком А
0
, выби-
рая все v,=0, 2 =
1,
..., л; равенство (6.2) справедливо, так как игрок
А
0
всегда может гарантировать для S выигрыш не более чем (6.2),
направляя каждому Де5 нулевой ресурс; равенство (6.3) имеет
место, поскольку коалиция S, содержащая в своем составе А
0
,
всегда может обеспечить распределение всего ресурса только между
своими членами.
Пусть S — произвольная коалиция, содержащая А
0
. Обозначим
через и=(и\, ...,
и'„)
вектор, доставляющий максимум в задаче
нелинейного программирования (6.3) (для
i'.BrfS
выполнено усло-
вие И(=0). Тогда для любой коалиции
S<zS,
5фА
0
,
А
0
еS
справед-
ливо следующее выражение:
£ (а,+
С
,К(и?)^ I (а,+с,)„;(«?)=
I-.BJBS
i:B
t
eS
= I (a,+c,K(«J)+ £ (а,+с,)«;(0).
i-.BieS i:BieS\S
Пусть S, RcN, Sf]R=0 и
А
0
еБфА
0
.
Тогда
А
0
фЯ.
Принимая во
внимание условия а
(
^0, с,^0, «
(
>0, /=1, ..., п, имеем
i:B
t
eS\jR i:BieS[jR
= £ (a
i
+c
i
)v'
i
(ud+ E (а,+сО«*(0) =
i-.BjeS i.BjeR
=v(S)+v(R)4>. £ a,v'(0)>v(S)+v(R),
UBjeR
где £ a,-i>*(0)>0— прибыль центра А
0
от «нефинансируемых»
i:BieR . .
предприятий. В случаях A
0
fS\jR или S=A
0
фR неравенство
v(S[jR)>v(S)+v(R) очевидно.
Таким образом, функция v(S), определяемая (6.1) — (6.3), супер-
аддитивна и можно рассмотреть кооперативную игру
({А
0
,
В
х
, ....
В„},
v) в форме характеристической функции v.
6.2. Рассмотрим (и+ 1)-мерный вектор
я
£
=
(£а,ь'(й
(
), с,v\(й,), ...,
с„г'„(щ)),
(6.4)
/-1
197
где u = u
N
. Вектор £ является дележом, поскольку выполнены следу-
ющие сотношения:
fc—0
i-1
л
2){
o
=I>.
e
?(Ui)>0=«0*o).
^=c,«;(«i)>c,i;*(0)=i;(5(), /=1, ..., п.
Напомним условие принадлежности дележа С-ядру. Согласно
теореме п. 10.1 гл. III необходимым и достаточным условием
принадлежности дележа (£
0
, £
t
, ...,
£„)
С-ядру является выполнение
неравенства
Е&>«(5) (6.5)
ieS
для всех коалиций Scz{A
0
, В
х
, ....
В„}.
Выведем условие, при котором дележ £' принадлежит С-ядру.
Если S={A
0
], либо Se^, ..., В„}, то условие (6.5) выполнено,
поскольку
£
0
=2>^(".)>0=*({Л
0
}),
i-l
Х&= Е<^&)> I c,*;(o)=
e
(s).
/Е5 i-.BjeS i-.BidS
Если i4
0
e5/^
0
, то условие (6.5) можно записать в виде
^а^(йд+ £ с
(
«*(йО=
f:2»,eS i:B,-6S (:Л(#£ i:B,6S
Следовательно, дележ (6.4) принадлежит С-ядру, если для всех
S:A
0
eSвыполнено неравенство
£ а,«;(й,)> £ (a,+c
f
) [«'("О-v.'("Л-
Заметим, что в данном случае мы определили характеристичес-
кую функцию игры, используя выигрыш в ситуации равновесия по
198
Нэшу, и величина v(N)=ma.x £ (a,+ci)v'(u), вообще говоря, мень-
»
<-1
ше максимального суммарного выигрыша всех игроков, равного
max max X(
a
*+
C
*H
ueU v
k
eV
k(u
0 \_
кш1
J
(в этом отличие от принятого в
гл.
III определения характеристичес-
кой функции).
6.3.
Характеристическую функцию игры можно построить
и обычным способом, а именно: для каждой коалиции S определить
ее как значение антагонистической игры между этой коалицией
и коалицией остальных игроков N\S. Построим теперь характери-
стическую функцию именно таким образом. При этом несколько
обобщим предыдущую задачу, введя в рассмотрение произвольные
функции выигрышей участников игры.
Как и ранее, будем предполагать, что центр А
0
распределяет
ресурсы между подразделениями
B
lt
....
В„,
которые используют эти
ресурсы для производства продукции. Выигрыши управляющего
центра А
0
и «производственных» подразделений Б
1
,...,
В„
зависят от
продукции, производимой B
t
, ....
В„.
Вектор ресурсов, имеющийся
в распоряжении центра А
0
, обозначим через Ь. Центр (игрок) А
0
выбирает систему и векторов и=(ц
1
, ....
и
п
)
из множества
я
U={u=(u
1
, ...,
Un):u
k
>0,
и
к
ев!, £ы*«$6, к=Т7п}.
*-i
Здесь и
к
интерпретируется как вектор ресурса, выделяемый центром
А
0
производственному подразделению В
к
. Возможности предпри-
ятия (игрока) В
к
определяются ресурсом
и
к
,
получаемым от А
0
, т. е.
предприятие В
к
выбирает свою производственную программу х
к
из
множества B
k
(u
k
)<zfT неотрицательных векторов. Будем предпола-
гать,
что множества В
к
(и
к
) при всех щ содержат нулевой вектор
и монотонно возрастают по включению, т. е. из и
к
>и
к
следует
В
к
{и'
к
)
•=>В
к
(и
к
),
кроме того, выполнено условие В
к
(0) = 0 (невозмож-
ность производства при отсутствии ресурсов).
Пусть x=(x
lt
.... х
п
). Выигрыш игрока А
0
определяется с помо-
щью неотрицательной функции /
0
(х)^0, а выигрыши игроков В
к
по-
лагаем равными
1
к
(х
к
)^0,
к=\, ..., п (выигрыш игрока В
к
зависит
199