Использование линейной оптимизации при решении матричных игр
Пусть игра 
не имеет оптимального решения в чистых стратегиях, т.е. седловая точка отсутствует 
.
Будем считать, что все элементы платежной матрицы неотрицательны (если это не так, то можно ко всем элементам матрицы добавить некоторое число 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 равны:
