Поиск оптимальных смешанных стратегий
Пусть дана платежная матрица A[mxn] = aij[mxn], у которой не существует цена игры, т.е. α≠β, α<β. Величина α – та величина, которая не может быть больше гарантированного среднего выигрыша игрока А, если он при повторении игры все время будет выбирать стратегию максимина.
Ставится вопрос: можно ли найти величину V
(α,β), чтобы изменяя выбор своей стратегии игрок А гарантировал себе средний выигрыш не меньше чем V.
Теорема (Основная теорема теории игр с нулевой суммой): Любая игра [mxn] с нулевой суммой имеет пару оптимальных смешанных стратегий (S*A,S*B), обладающих свойством устойчивости: Если игрок будет придерживаться своей оптимальной стратегии, то другому игроку невыгодно отступать от своей оптимальной стратегии при многократном повторении игры.
Смешанной стратегией игрока А называется вектор SA=(p1,p2,…pm), где pi – вероятность случайного выбора стратегии Ai. SB=(q1,q2,…qn) – смешанная стратегия игрока В, qi – вероятность случайного выбора стратегии Bj игроком B.
Условия: 
(1); 
(2)
Предполагая, что существует некоторая величина V ниже которой не может быть средний выигрыш игрока А, независимо от выбора игроком В своей стратегии получим, что для вектора SA должны выполняться неравенства: 
(3)
Обозначим pi/V := xi, i=1,..m (4). Тогда (3) запишется в виде: 
(5). Введем функцию 
(6). z=1/V – величина, обратная среднему выигрышу игрока А, при условии, что он будет придерживаться стратегии SA.
Т.к. игрок А заинтересован в том, чтобы получить максимально возможный средний выигрыш V, то учитывая выражение (6) игрок А должен решать задачу 
(7) при условии, что (8), 
(9), i=1,..m. Задача (7),(8),(9) является задачей линейного программирования.
Если рассмотреть задачу со стороны игрока В и обозначить yj=qj/V, j=1,..n (10), то получим задачу 
(11), при условиях 
(12), i=1,..m, 
(13), j=1,..n. 
(14), а игрок В стремится минимизировать величину V, т.к. V – средний выигрыш игрока А. Неравенство (12) получаются из условий 
(15), означающих, что средний проигрыш игрока В при любом выборе стратегии игрока А будет не больше величины V.
Таким образом, получены две задачи - (7),(8),(9) и (11),(12),(13), образующие пару двойственных задач линейного программирования.
Пример (Решение игры в три пальца)
Не существует чистой стратегии ни для какого из игроков. Будем искать оптимальные смешанные стратегии. К элементам платежной матрицы добавим число M=5 так, чтобы все элементы этой матрицы были неотрицательны. Доказано, что при этом смешанные стратегии SA,SB не изменятся, а цена игры увеличится на М. V’=V+M
| B1 | B2 | B3 | |
| A1 | |||
| A2 | |||
| A3 |
Запишем задачу (7),(8),(9) для этой матрицы: 
Эта задача решается симплекс-методом. В результате будет найдено оптимальное решение: x1*=1/20, x2*=1/10, x3*=1/20. z*=1/20+1/10+1/20=1/5. Следовательно, 1/V'=z*=1/5, V'=5, V*=5-5=0
Т.е. оптимальный средний выигрыш игрока равен 0, если игрок B будет придерживаться оптимальной стратегии. p1*=x1*·V’=5/20=1/4, p2*=5/10=1/2, p3*=5/20=1/4. Следовательно, оптимальная смешанная стратегия для игрока А задается S*A=(1/4, ½ , ½).
Для игрока B аналогично записывается задача (11),(12),(13) и ее решение будет: S*B=(1/4, ½ , 1/4).
Понятие о двойственных задачах линейного программирования
Пусть дана задача линейного программирования в стандартной форме: 
(1).
, i=1,..m (2) 
, j=1,..n (3)
Для перехода к двойственной задаче вводятся новые переменные yi, i=1,..m. При этом любая переменная yi соответствует одному из неравенств (2). После этого записывается двойственная задача в следующем виде: