Пусть игра не имеет оптимального решения в чистых стратегиях, т.е. седловая точка отсутствует .
Будем считать, что все элементы платежной матрицы неотрицательны (если это не так, то можно ко всем элементам матрицы добавить некоторое число L, переводящее платежи в область неотрицательных значений - при этом цена игры увеличится на L, а решение задачи не изменится). Таким образом, предполагаем, что .
Будем искать решение игры в смешанных стратегиях:
;.
Применение игроком I оптимальной смешанной стратегии гарантирует ему, независимо от поведения игрока II, выигрыш, не меньший цены игры .
Пусть игрок II применяет свою активную чистую j-ю стратегию, а игрок I - свою оптимальную стратегию . Тогда средний выигрыш игрока I будет равен
Учитывая, что не может быть меньше , запишем условия:
Разделив левую и правую части каждого из неравенств (10.3) на цену игры , получим:
При использовании обозначений
неравенства (10.5) примут вид:
где, очевидно, все , так как .
Условие нормировки с учетом определения (13.13) дает следующее соотношение
Учитывая, что игрок I стремится максимизировать , получаем линейную функцию
Таким образом, задача определения оптимальной смешанной стратегии свелась к стандартной задаче линейной оптимизации: найти неотрицательные значения переменных , минимизирующие целевую функцию (13.15) и удовлетворяющие ограничениям (13.14).
Решение задачи линейной оптимизации позволяет найти цену игры и оптимальную стратегиюпервого игрока:
Аналогично можно показать, что оптимальная стратегия второго игрока определяется по формулам
где - неотрицательные решения задачи линейной оптимизации, двойственной по отношению к исходной задаче:
,
а переменные
Таким образом, оптимальные стратегии первого и второго игроков могут быть найдены путем решения пары двойственных задач линейной оптимизации.
Исходная задача | Двойственная задача |
Цена игры и вероятности применения стратегий игроками I и II равны:
Проиллюстрируем вышесказанное на двух простых примерах.