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

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

Пусть игра mxn задана платежной матрицей Р=(a_ij) i=1,2,…,m; j=1,2,…,n. которой имеет размерность mn. Игрок А располагает стратегиями A_i, (i=1,2,...,m), а игрок В - стратегиями В_j , (j= 1, 2, ... , n). Необходимо определить оптимальные стратегии S*_A = (р₁^*,р₂^*, …, р_m^*) и S*_B = (q₁^*, q₂^*, ... ,q_n^*), где р_i^* и q_j^* - вероятности применения соответствующих чистых стратегий А_i и В_j.

р₁^*+р₂^*+ …+ р_m^*=1 , q₁^*+ q₂^*+ ...+q_n^*=1.

Применение игроком А оптимальной стратегии S*_A должно обеспечить ему при любых действиях игрока В средний выигрыш не меньше цены игры v, т. е. необходимо выполнение соотношения j=1, 2, ... , n. Цена игры неизвестна, но полагаем v>0, этого можно добиться, сделав все элементы a_ij0, прибавляя ко всем a_ij некоторое положительное число, величина которого равна абсолютному значению элемента, наименьшего среди всех отрицательных элементов матрицы.

Если игрок А применяет смешанную стратегию S*_A = (р₁^*,р₂^*, …, р_m^*) против любой чистой стратегии игрока В, то он получает средний выигрыш, или математическое ожидание выигрыша (т.е. элементы j-го столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий А₁,А₂,…,А_m и результаты складываются).

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

Каждое из неравенств разделим на число v>0 и введем новые переменные (2)

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

(3)

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

Разделив на v>0 равенство р₁+р₂+ …+ р_m=1, получаем, что переменные x_i (i=1,2,..,m) удовлетворяют условию х₁+х₂+ …+ х_m=1/v. Максимизация цены игры v эквивалентна минимизации величины 1/v, поэтому задача может быть сформулирована следующим образом: определить значения переменных x_i0 так, чтобы они удовлетворяли линейным ограничениям (3) и при этом линейная функция обращалась в минимум. Это ЗЛП. Решая задачу, находим значения x_i и величину 1/v, затем получаем оптимальное решение р_i^*= vx_i (I=1,2,..,m) и оптимальную стратегию S*_A.

Для определения оптимальной стратегии S*_B = (q₁^*, q₂^*, ... ,q_n^*) следует учесть, что игрок В стремится минимизировать гарантированный выигрыш, т.е. найти . Стратегия S*_B должна обеспечить при любых стратегиях игрока А проигрыш, не превышающий величину v, т. е. необходимо выполнение соотношения i=1, 2, ... ,m, т.е. переменные q₁, q₂, ... ,q_n удовлетворяют неравенствам

Если обозначить y_j= j=1, 2, ... ,n, то получим

(4)

Элементы смешанных стратегий должны удовлетворять условиям

q₁+q₂+ ... +q_n=1.

Данные условия в новых переменных ( q_j=y_jv, j=1, 2, ... , n) получают следующий вид:

y₁+y₂+ ... +y_n= .

Игра свелась к ЗЛП: определить значения переменных y_i0, которые удовлетворяют линейным ограничениям (4) и максимизируют функцию .

Решая задачу, находим значения y_i и величину 1/v, затем получаем оптимальное решение q_j^*= vy_j (j=1,2,..,n) и оптимальную стратегию S*_B.