Замечание 3
. Игра (3), (4) является матричной и поэтому имеет
конечное множество равновесий по Нэшу. В достаточном условии те-
оремы 4 можно потребовать выполнения лишь одного из равенств
p
=
μ
или
q
=
λ
, так как другое в этом случае обязано выполнять-
ся.
Докажем это. Пусть для определенности
q
=
λ
. Тогда по усло-
вию дополняющей нежесткости
(
8
j
)(
p
T
B
−
u
)
j
q
j
= 0
заключаем, что
max
q
2
Σ
q
p Bq
=
u .
(5)
Оптимизация (3) эквивалентна поиску максимума функции Лагран-
жа задачи (3), т.е. [5]
p
T
(
A
+
B
)
q
−
u
+ (
ue
T
−
p
T
B
)
q
≡
p
T
Aq
→
max
p
2
Σ
p
.
Так как решение этой задачи есть точка
p
, то вместе с (5) это доказы-
вает равновесность пары стратегий
(
p , q
)
в исходной игре. По теоре-
ме 1 и необходимому условию из теоремы 4 заключаем, что
p
=
μ
.
Алгоритм поиска равновесия.
В соответствии с теоремами 3, 4 и
замечанием 3 предлагается использовать следующую многошаговую
схему поиска равновесия.
Этап
0. Один из игроков, пусть это игрок 2, первым выбирает одну
из своих смешанных стратегий
q
0
2
Σ
q
и сообщает ее игроку 1.
Этап
1. Оба игрока, начиная с игрока 1, поочередно выбирают
свои оптимальные (в текущих ситуациях) стратегии в игре (3), (4) и
сообщают их партнеру. По достижении некоторой ситуации равнове-
сия (
p
0
, q
0
) перейти к выполнению этапа 2.
Этап
2. Если
q
0
6
=
λ
0
, то один из игроков, пусть это игрок 2,
изменяет свое решение — вместо стратегии
q
0
применяет стратегию
λ
0
и сообщает ее игроку 1. Перейти к действиям этапа 1.
На этапе 1 разворачивается итерационный процесс из теоремы 3.
Если проверяемое на этапе 2 условие не выполнено, то ситуация (
p
0
, q
0
)
есть искомое равновесие по Нэшу исходной игры (замечание 3).
Вычислительный пример.
Пусть
m
=
n
= 4
, а платежи игроков
представлены матрицей
((
a
ij
, b
ij
))
вида
(1
,
3) (1
,
2) (0
,
1) (3
,
1)
(3
,
2) (2
,
3) (2
,
0) (0
,
1)
(2
,
3) (1
,
0) (1
,
2) (3
,
1)
(1
,
0) (3
,
2) (0
,
2) (2
,
3)
.
58
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2008. № 3
