ВУЗ:
Составители:
3 2 8 4 6
Игру 2 × 4 можно решать графически, но можно продолжить подобные преобразования дальше, они
дадут последующее упрощение задачи.
5 В игре 2 × 4 пятая стратегия второго игрока доминирует третью, отбрасывание которой приводит
к игре 2 × 3.
2 4 5
1 4 3 2
3 2 4 6
Смешанная стратегия второго игрока ξ
2
= 0,5 и ξ
5
= 0,5 доминирует четвертую стратегию, исключе-
ние которой приводит к игре 2 × 2.
2 5
1 4 2
3 2 6
6.4 РЕШЕНИЕ МАТРИЧНОЙ ИГРЫ
МЕТОДОМ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Если нельзя методами упрощения свести игровую задачу к размерности 2 × m или n × 2, то ее заме-
няют задачей линейного программирования.
Сведение матричной игры к задаче линейного программирования является общим методом решения
подобных задач.
Пусть цена игры ν. Эта величина является максимальным гарантированным выигрышем первого
игрока. Так, если первый игрок поддерживает оптимальную смешанную стратегию ξ
*
, его выигрыш не
может быть меньше ν. Однако, если первый игрок поддерживает не оптимальную стратегию ξ
*
, а неко-
торую другую стратегию ξ, то существует некоторый гарантированный выигрыш ν
1
, т.е. при любой
стратегии второго игрока, выигрыш первого не может быть меньше ν
1
. При этом ν
1
≤ν, и задача первого
игрока найти такую стратегию ξ
*
, при которой ν
1
примет максимальное значение, равное ν.
Геометрическую интерпретацию этого положения можно просмотреть на примере задачи 2 × n (рис.
6.12).
Если взять ξ
2
≠ ξ
2
*
, гарантированный выигрыш ν
1
будет меньше цены игры ν.
Таким образом, задача матричной игры может быть сформулирована для первого игрока как задача
нахождения такой стратегии
ξ
*
= (ξ
1
*
, …, ξ
n
*
), при которой максимизируется величина ν
1
: ν
1
→ max, при условии, что выигрыш пер-
вого игрока при любых чистых стратегиях j = 1, …, m второго игрока будет больше ν
1
:
.0,,0,0
;
;
;
21
12211
11222112
11221111
≥ξ≥ξ≥ξ
ν≥ξ++ξ+ξ
ν≥ξ++ξ+ξ
ν≥ξ++ξ+ξ
n
nnmmm
nn
nn
qqq
qqq
qqq
K
L
L
L
L
(6.15)
Кроме того считают, что ν
1
> 0. Это всегда можно сделать, прибавив к составляющим матрицы
ij
q
одно и то же положительное число.
