Постановка задачи

Рассмотрим это на примере.

Приведение матричной игры к задаче линейного программирования

Игра m × n в общем случае не имеет наглядной геометрической интерпретации. Ее решение достаточно трудоемко при больших m и n, но принципиальных трудностей не имеет, так как может быть сведено к решению задачи линейного программирования (ЗЛП).

Пусть игра m × n задана платежной матрицей Н = (h_ij ), i =1,2,...,m; j=1,2,...,n.

Игрок А обладает стратегиями A₁ , A₂ , ..., A_m , игрок В - стратегиями B₁ , B₂ , ..., B_n .

Необходимо определить оптимальные стратегии

S*_A = (p*₁,p*₂,... ,p*_m) и S*_B = (q*₁,q*₂,..., q*_n),

где p*_i, q*_j - вероятности применения соответствующих чистых стратегий A_i, B_j,

p*₁ + p*₂ +...+ p*_m =1,

q*₁ + q*₂ +...+ q*_n = 1.

 

 

Определение оптимальной стратегии игрока А

Оптимальная стратегия S*_A удовлетворяет следующему требованию:

она обеспечивает игроку А средний выигрыш, не меньший, чем цена игры v, при любой стратегии игрока В, и выигрыш, равный цене игры v, при оптимальной стратегии игрока B.

Без ограничения общности полагаем v > 0: этого можно добиться, сделав все элементы h_ij ≥ 0.

Если игрок А применяет смешанную стратегию S*_A = (p*₁,p*₂,... ,p*_m) против любой чистой стратегии B_j игрока В, то он получает средний выигрыш, или математическое ожидание выигрыша

a_j = h_1j p₁ + h_2j p₂ +...+ h_{m j} p_m ,

где j =12, ...,n (т.е. элементы j-го столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий A₁,A₂ ,...,A_m и результаты складываются).

Для оптимальной стратегии S*_A все средние выигрыши не меньше цены игры, поэтому получаем систему неравенств:

 

(2)

 

Каждое из неравенств можно разделить на число v > 0. Введем новые переменные:

 

x1 = , x2 = , ..., xm =

(3)

 

Тогда система (11) примет вид:

 

(1)

 

Цель игрока А - максимизировать свой гарантированный выигрыш, т.е. цену игры v.

Разделив на v ≠ 0 равенство p₁+ p₂ + ...+ p_m = 1, получаем, что переменные x_i (i = 1,2, ...,m) удовлетворяют условию:

x₁ + x₂ + ...+ x_m = .

Максимизация цены игры v эквивалентна минимизации величины , поэтому задача может быть сформулирована следующим образом:

определить значения переменных x_i ≥ 0, i = 1, 2, ..., m, такие, чтобы они удовлетворяли линейным ограничениям (13) и при этом линейная функция

 

Z = x1 + x2 + ...+ xm,

(4)

 

обращалась в минимум.

Это задача линейного программирования. Решая задачу (2)-(3), получаем оптимальное решение p*₁ , p*₂ , ..., p*_m и оптимальную стратегию S_A.

Определение оптимальной стратегии игрока В

 

Для определения оптимальной стратегии S*_B = (q*₁ + q*₂ + ...+ q*_n) следует учесть, что игрок В стремится минимизировать гарантированный выигрыш, т.е. найти .

Переменные q₁ , q₂ , ..., q_n удовлетворяют неравенствам:

 

(5)

 

которые следуют из того, что средний проигрыш игрока В не превосходит цены игры, какую бы чистую стратегию не применял, игрок А.

Если обозначить

 

yj = , где j = 1, 2, ..., n,

(6)

 

то получим систему неравенств:

 

(7)

 

Переменные y_j (1, 2, ..., n) удовлетворяют условию у₁ + у₂ + ... + у_n = .

 

Игра свелась к следующей задаче:

определить значения переменных y_j ≥ 0, j = 1, 2, ..., n, которые удовлетворяют системе неравенств (7) и максимизируют линейную функцию

 

Z' = y1 + y2 + ...+ yn,

(8)

 

Решение задачи линейного программирования (3.16), (3.17) определяет оптимальную стратегию S*_B = (q*₁ + q*₂ + ...+ 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 возможно геометрическое решение.

На практике реализация оптимального решения в смешанных стратегиях может происходить несколькими путями:

_· первый состоит в физическом смешении чистых стратегий A_i - в пропорциях, заданных вероятностями p_i,

· другой путь — при многократном повторении игры — в каждой партии чистые стратегии применяются в виде случайной последовательности, причем каждая из них — с частотой, равной ее вероятности в оптимальном решении.