Использование линейной оптимизации при решении матричных игр

Использование линейной оптимизации при решении матричных игр

Пусть игра  не имеет оптимального решения в чистых стратегиях, т.е. седловая точка отсутствует .

Будем считать, что все элементы платежной матрицы неотрицательны  (если это не так, то можно ко всем элементам матрицы добавить некоторое число L, переводящее платежи в область неотрицательных значений - очевидно, при этом цена игры увеличится на L, а решение задачи не изменится). Таким образом, предполагаем, что >0.

Будем искать решение игры в смешанных стратегиях:

;  

Применение игроком I оптимальной смешанной стратегии  гарантирует ему, независимо от поведения игрока II, выигрыш, не меньший цены игры .

Пусть игрок II применяет свою активную чистую j-ю стратегию, а игрок I - свою оптимальную стратегию . Тогда средний выигрыш игрока I будет равен

Учитывая, что   не может быть меньше , запишем условия:

Рекомендуемые материалы

Разделив левую и правую части каждого из неравенств (4.4) на цену игры >0, получим:

          (4.5) 

При использовании обозначений     

                                                               (4.6)

неравенства (4.5) примут вид:

где, очевидно, все , так как  .

Из равенства и в силу определения (4.6) следует, что переменные () удовлетворяют условию

Учитывая, что игрок I стремится максимизировать , получаем линейную функцию

                             (4.8)

Таким образом, задача решения игры свелась к следующей задаче линейной оптимизации: найти неотрицательные значения переменных  минимизирующие линейную функцию (4.8) и удовлетворяющие ограничениям (4.7).

Из решения задачи линейной оптимизации легко найти цену игры  и оптимальную стратегию игрока I:

В свою очередь, оптимальная стратегия игрока II   может быть найдена из выражения

где   -  неотрицательные переменные задачи линейной оптимизации:

,

которая является двойственной по отношению к задаче, представленной условиями (4.7) и (4.8).

В этой системе неравенств переменные 

Таким образом, оптимальные стратегии  и  игры с платежной матрицей  () могут быть найдены путем решения симметричной пары двойственных задач линейной оптимизации.

Цена игры и вероятности применения стратегий игроками I  и II равны: