Поиск оптимальных смешанных стратегий

Пусть дана платежная матрица A[mxn] =aij[mxn], у которой не существует цена игры, т.е. α≠β, α<β. Величина α – та величина, которая не может быть больше гарантированного среднего выигрыша игрока А, если он при повторении игры все время будет выбирать стратегию максимина.

Ставится вопрос: можно ли найти величину V(α,β), чтобы изменяя выбор своей стратегии игрок А гарантировал себе средний выигрыш не меньше чем V.

Теорема(Основная теорема теории игр с нулевой суммой): Любая игра [mxn] с нулевой суммой имеет пару оптимальных смешанных стратегий (S*_A,S*_B), обладающих свойством устойчивости: Если игрок будет придерживаться своей оптимальной стратегии, то другому игроку невыгодно отступать от своей оптимальной стратегии при многократном повторении игры.

Смешанной стратегиейигрока А называется вектор S_A=(p1,p2,…pm), где pi – вероятность случайного выбора стратегии Ai. S_B=(q1,q2,…qn) – смешанная стратегия игрока В, qi – вероятность случайного выбора стратегии Bj игроком B.

Условия: (1);(2)

Предполагая, что существует некоторая величина Vниже которой не может быть средний выигрыш игрока А, независимо от выбора игроком В своей стратегии получим, что для вектораS_Aдолжны выполняться неравенства:(3)

Обозначим pi/V:=xi,i=1,..m(4). Тогда (3) запишется в виде:(5). Введем функцию(6).z=1/V– величина, обратная среднему выигрышу игрока А, при условии, что он будет придерживаться стратегии S_A.

Т.к. игрок А заинтересован в том, чтобы получить максимально возможный средний выигрыш 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 так, чтобы все элементы этой матрицы были неотрицательны. Доказано, что при этом смешанные стратегии S_A,S_Bне изменятся, а цена игры увеличится на М.V’=V+M

	B1	B2	B3
A1	7	2	9
A2	2	9	0
A3	9	0	11

Запишем задачу (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).