Теорема 3. Для того чтобы смешанные стратегии и были оптимальными в игре с матрицей (7.1) и ценой игры u, необходимо и достаточно, чтобы выполнялись следующие неравенства:
³ u; j = , причем = 1; (7.3)
£ u; i = , причем = 1. (7.4)
Нахождение оптимальной стратегии можно свести к решению задачи линейного программирования.
Пусть требуется найти оптимальные стратегии для игры с заданной платежной матрицей (7.1), для которой aij строго больше нуля (аij >0, i= ,j = ), тогда цена игры u > 0. Найдем оптимальную стратегию игрока А – ().
Разделим левую и правую части в выражении (7.3) на положительную величину u:
³ 1; = .
Введем обозначение = Хi, тогда
Хi ³ 1; j = ; = .
Поскольку игрок А стремится сделать свой гарантированный выигрыш (u) как можно большим (u ® max), то величина должна быть как можно меньше (u ® min), тогда имеем следующую задачу линейного программирования:
f(x) = ® min, (7.5)
Хi ³ 1; j = , (7.6)
Хi ³ 0; i = . (7.7)
Если Х* = (, ,… … ) – оптимальный план задачи (7.5) – (7.7), а минимум функции f(x) = f(x*) = f*, то цена игры u при этом составит u = , а т.к. = Хi, тогда = (u × ,… u × ) = (,… ) – оптимальная смешанная стратегия игрока А.
|
|
Для игрока В используя выражение (7.4), получим
g(y) = ® max.
yj £ 1, i = .
yj ³ 0; j = .
Решение игры u = ;
= (u × ,… u × ) = (,… ).
Пример. Найти оптимальные смешанные стратегии игры, заданной следующей платежной матрицей:
В1 | В2 | В3 | нижняя цена игры a = 4, верхняя цена игры b = 5, т.е. a ¹ b – седловой точки нет. | |
А1 | ||||
А2 |
Сведем данную задачу к задаче линейного программирования.
Найдем оптимальную стратегию игрока А – ():
f(x) = X1 + X2 ® min.
X1 + 8X2 ³ 1,
10X1 + 4X2 ³ 1,
3X1 + 5X2 ³ 1,
X1, X2 ³ 0.
f(x) = 0,21; X1 = 0,026; X2 = 0,184,
отсюда
u = = 4,76; P1 = 4,76 × 0,026 = 0,124;
P2 = 4,76 × 0,184 = 0,876.
Найдем оптимальную стратегию игрока В – ():
g(y) = y1 + y2 + y3 ® max.
y1 + 10y2 + 3y3 £ 1,
8y1 + 4y2 + 5y3 £ 1,
y1, y2 , y3 ³ 0.
g(y) = 0,21; y1 = 0; y2 = 0,0526; y3 = 0,158,
отсюда
q1 = 0; q2 = 4,76 × 0,0526 = 0,25;
q3 = 4,76 × 0,158 = 0,75.
Таким образом, применяя свою первую чистую стратегию с вероятностью 0,124 и вторую – с вероятностью 0,876, игрок А выигрывает величину 4,76. Игрок В, применяя свою вторую чистую стратегию с вероятностью 0,25 и третью – с вероятностью 0,75, проигрывает величину 4,76, иначе он проигрывает больше.