 |
Приведение матричной игры к задаче линейного программирования
|
|
|
|
Игра m × n в общем случае не имеет наглядной геометрической интерпретации. Ее решение достаточно трудоемко при больших m и n, но принципиальных трудностей не имеет, так как может быть сведено к решению задачи линейного программирования (ЗЛП).
Рассмотрим это на примере.
Пусть игра m × n задана платежной матрицей Н = (hij), i =1,2,...,m; j=1,2,...,n.
Игрок А обладает стратегиями A1 , A2 ,..., Am , игрок В - стратегиями B1 , B2 ,..., Bn.
Необходимо определить оптимальные стратегии
S*A = (p*1,p*2,...,p*m) и S*B = (q*1,q*2,..., q*n),
где p*i, q*j - вероятности применения соответствующих чистых стратегий Ai, Bj,
p*1 + p*2 +...+ p*m =1,
q*1 + q*2 +...+ q*n = 1.
Постановка задачи
Определение оптимальной стратегии игрока А
Оптимальная стратегия S*A удовлетворяет следующему требованию:
она обеспечивает игроку А средний выигрыш, не меньший, чем цена игры v, при любой стратегии игрока В, и выигрыш, равный цене игры v, при оптимальной стратегии игрока B.
Без ограничения общности полагаем v > 0: этого можно добиться, сделав все элементы hij ≥ 0.
Если игрок А применяет смешанную стратегию S*A = (p*1,p*2,...,p*m) против любой чистой стратегии Bj игрока В, то он получает средний выигрыш, или математическое ожидание выигрыша
aj = h1j p1 + h2j p2 +...+ hm j pm,
где j =12,...,n (т.е. элементы j-го столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий A1,A2 ,...,Am и результаты складываются).
Для оптимальной стратегии S*A все средние выигрыши не меньше цены игры, поэтому получаем систему неравенств:
| (2) |
Каждое из неравенств можно разделить на число v > 0. Введем новые переменные:
x1 =  , x2 =  ,..., xm = 
| (3) |
Тогда система (11) примет вид:
| (1) |
Цель игрока А - максимизировать свой гарантированный выигрыш, т.е. цену игры v.
|
|
|
Разделив на v ≠ 0 равенство p1+ p2 +...+ pm = 1, получаем, что переменные xi (i = 1,2,...,m) удовлетворяют условию:
x1 + x2 +...+ xm = 
.
Максимизация цены игры v эквивалентна минимизации величины , поэтому задача может быть сформулирована следующим образом:
определить значения переменных xi ≥ 0, i = 1, 2,..., m, такие, чтобы они удовлетворяли линейным ограничениям (13) и при этом линейная функция
| Z = x1 + x2 +...+ xm, | (4) |
обращалась в минимум.
Это задача линейного программирования. Решая задачу (2)-(3), получаем оптимальное решение p*1, p*2,..., p*m и оптимальную стратегию SA.
Определение оптимальной стратегии игрока В
Для определения оптимальной стратегии S*B = (q*1 + q*2 +...+ q*n) следует учесть, что игрок В стремится минимизировать гарантированный выигрыш, т.е. найти 
.
Переменные q1 , q2,..., qn удовлетворяют неравенствам:
| (5) |
которые следуют из того, что средний проигрыш игрока В не превосходит цены игры, какую бы чистую стратегию не применял, игрок А.
Если обозначить
yj =  , где j = 1, 2,..., n,
| (6) |
то получим систему неравенств:
| (7) |
Переменные yj (1, 2,..., n) удовлетворяют условию у1 + у2 +... + уn = .
Игра свелась к следующей задаче:
определить значения переменных yj ≥ 0, j = 1, 2,..., n, которые удовлетворяют системе неравенств (7) и максимизируют линейную функцию
| Z' = y1 + y2 +...+ yn, | (8) |
Решение задачи линейного программирования (3.16), (3.17) определяет оптимальную стратегию S*B = (q*1 + q*2 +...+ q*n). При этом цена игры
v =  , Z' = 
| (9) |
Составив расширенные матрицы для задач (2), (3) и (7), (8), убеждаемся, что одна матрица получилась из другой транспонированием:
Таким образом, задачи линейного программирования (2), (3) и (7), (8) являются взаимно-двойственными. Очевидно, при определении оптимальных стратегий в конкретных задачах следует выбрать ту из взаимно-двойственных задач, решение которой менее трудоемко, а решение другой задачи найти с помощью теорем двойственности.
|
|
|
1.11 Схема решения произвольной конечной игры размера m × n
При решении произвольной конечной игры размера m × n рекомендуется придерживаться следующей схемы:
1. исключить из платежной матрицы заведомо невыгодные стратегии по сравнению с другими стратегиями. Такими стратегиями для игрока А (игрока В) являются те, которым соответствуют строки (столбцы) с элементами, заведомо меньшими (большими) по сравнению с элементами других строк (столбцов).
2. определить верхнюю и нижнюю цены игры и проверить, имеет ли игра седловую точку. Если седловая точка есть, то соответствующие ей стратегии игроков будут оптимальными, а цена совпадает с верхней (нижней) ценой.
3. если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. Для игр размера m × n рекомендуется симплексный метод, для игр размера 2×2, 2×n, n×2 возможно геометрическое решение.
На практике реализация оптимального решения 
в смешанных стратегиях может происходить несколькими путями:
· первый состоит в физическом смешении чистых стратегий Ai - в пропорциях, заданных вероятностями pi,
· другой путь — при многократном повторении игры — в каждой партии чистые стратегии применяются в виде случайной последовательности, причем каждая из них — с частотой, равной ее вероятности в оптимальном решении.
|
|
|
