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

Оглавление | Назад | Далее| Глоссарий понятий

Игра m × n в общем случае не имеет наглядной геометрической интерпретации. Ее решение достаточно трудоемко при больших m и n, однако принципиальных трудностей не имеет, поскольку может быть сведено к решению задачи линейного программирования. Покажем это. Пусть игра m × n задана платежной матрицей p = (a_ij ), i = 1, 2, ..., m; j = 1, 2, ..., n. Игрок А обладает стратегиями A₁ , A₂ , ..., A_m , игрок В — стратегиями B₁ , B₂ , ..., B_m . Необходимо определить оптимальные стратегии 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: этого можно добиться, сделав все элементы a_ij ≥ 0. Если игрок А применяет смешанную стратегию S*_A = ( p*₁ ,  p*₂ , ... ,  p*_m ) против любой чистой стратегии B_j игрока В, то он получает средний выигрыш, или математическое ожидание выигрыша a_j = a_1j p₁ + a_2j p₂ +...+ a_m j p_m , о = 1, 2, ..., n (т.е. элементы j-го столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий A₁ , A₂ , ..., A_m и результаты складываются).

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

(3.11)

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

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

(3.13)

Цель игрока А — максимизировать свой гарантированный выигрыш, т.е. цену игры v.
Разделив на v ≠ 0 равенство p₁ + p₂ + ...+ p_m = 1 , получаем, что переменные x₁ (i = 1, 2, ..., m) удовлетворяют условию: x₁ + x₂ + ...+ x_m = 1/v. Максимизация цены игры v эквивалентна минимизации величины 1/v, поэтому задача может быть сформулирована следующим образом: определить значения переменных x_i ≥ 0, i = 1, 2, ..., m, так, чтобы они удовлетворяли линейным ограничениям (13) и при этом линейная функция

обращалась в минимум. Это задача линейного программирования. Решая задачу (3.13)—(3.14), получаем оптимальное решение p*₁ + p*₂ + ...+ p*_m и оптимальную стратегию S_A .
Для определения оптимальной стратегии S*_B = (q*₁ + q*₂ + ...+ q*_n) следует учесть, что игрок В стремится минимизировать гарантированный выигрыш, т.е. найти . Переменные q₁ , q₂ , ..., q_n удовлетворяют неравенствам:

(3.15)

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

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

(3.17)

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

Решение задачи линейного программирования (3.16), (3.17) определяет оптимальную стратегию S*_B = (q*₁ + q*₂ + ...+ q*_n) . При этом цена игры

Составив расширенные матрицы для задач (3.13), (3.14) и (3.17), (3.18), убеждаемся, что одна матрица получилась из другой транспонированием:

Таким образом, задачи линейного программирования (3.13), (3.14) и (3.17), (3.18) являются взаимно-двойственными. Очевидно, при определении оптимальных стратегий в конкретных задачах следует выбрать ту из взаимно-двойственных задач, решение которой менее трудоемко, а решение другой задачи найти с помощью теорем двойственности. Приведем примеры экономических задач, которые описываются игровыми моделями т х п и могут быть решены методами линейного программирования.

Пример 3.5.1.

Обозначив x_i =  p_i/v, i = 1, 2, 3 и y_j = q_j/v , j = 1, 2, 3, составим две взаимно-двойственные задачи линейного программирования (см. (3.13)-(3.14) и (3.17)-(3.18)).

Пример 3.5.2

При решении произвольной конечной игры размера m × n рекомендуется придерживаться следующей схемы:

1. Исключить из платежной матрицы заведомо невыгодные стратегии по сравнению с другими стратегиями. Такими стратегиями для игрока А (игрока В) являются те, которым соответствуют строки (столбцы) с элементами, заведомо меньшими (большими) по сравнению с элементами других строк (столбцов).
2. Определить верхнюю и нижнюю цены игры и проверить, имеет ли игра седловую точку. Если седловая точка есть, то соответствующие ей стратегии игроков будут оптимальными, а цена совпадает с верхней (нижней) ценой.
3. Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. Для игр размера m × n рекомендуется симплексный метод, для игр размера 2×2, 2×n, n×2 возможно геометрическое решение.

На практике реализация оптимального решения в смешанных стратегиях может происходить несколькими путями. Первый состоит в физическом смешении чистых стратегий A_i  - в пропорциях, заданных вероятностями p_i .
Другой путь — при многократном повторении игры — в каждой партии чистые стратегии применяются в виде случайной последовательности, причем каждая из них — с частотой, равной ее вероятности в оптимальном решении.

Рассмотрим еще одну экономическую задачу, сводящуюся к игровой модели.

Пример 3.5.3.

Упражнения

Оглавление | Назад | Далее| Глоссарий понятий