УДК 519.85
Н. С. В а с и л ь е в
ЧИСЛЕННОЕ РЕШЕНИЕ БИМАТРИЧНЫХ ИГР
Предложен эффективный игровой алгоритм поиска равновесия по
Нэшу в биматричных играх, основанный на методах линейного про-
граммирования и теории двойственности.
Поиск ситуации равновесия по Нэшу биматричной игры в сме-
шанных стратегиях игроков обычно проводится с помощью метода
полного перебора [1, 2]. Для этого строятся системы линейных алге-
браических уравнений (СЛАУ) вида
A
0
q
0
=
ue
;
p
0
T
B
0
=
ve
0
T
;
P
i
2
I
p
0
i
= 1;
P
j
2
J
q
0
j
= 1
относительно неизвестных
p
0
,
q
0
,
u
,
v
, в которых векторы
e
,
e
0
тако-
вы, что имеют все координаты, равные единице, множества значений
индексов
I
{
1
,
2
, . . . , m
}
,
J
{
1
,
2
, . . . , n
}
, а
A
0
,
B
0
являются под-
матрицами платежных матриц игроков
A
,
B
, имеющих размер
m
×
n
.
Здесь
m
(
n
)
— число чистых стратегий первого (второго) игрока. Па-
ра (
p
0
,
q
0
) есть искомая ситуация равновесия в смешанных стратегиях
лишь при условии того, что указанная СЛАУ имеет неотрицательное
решение
p
0
>
0
,
q
0
>
0
. Таким образом, для поиска равновесия игры
требуется решить
2
m
+
n
систем. Экспоненциальная сложность метода
перебора делает его практически неприменимым. В статье предложен
алгоритм предположительно полиномиальной сложности, апробиро-
ванный в вычислительных экспериментах.
Постановка задачи.
В биматричной игре [1, 2] каждый игрок рас-
полагает конечным множеством чистых стратегий. Игра полностью
определяется
m
×
n
матрицами
A
,
B
, которые являются табличным
заданием функций выигрыша игроков 1 и 2. Игрок 1 выбирает стро-
ку
i
, одновременно с ним игрок 2 выбирает столбец
j
. После этого
игрок 1 получает выигрыш
a
ij
, а игрок 2 — выигрыш
b
ij
.
Смешанная
стратегия игрока — это случайная величина, принима-
ющая значения в множестве его чистых стратегий. Смешанную стра-
тегию будем отождествлять с выбираемым игроком 1 (игроком 2) ве-
роятностным распределением
p
(
q
)
: игрок 1 (игрок 2) с вероятностью
54
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2008. № 3
