Решение матричных игр
Существует несколько основных методов решения матричных игр:
1. Аналитический
2. Графический
3. Итеративный (метод Брауна-Джонсона)
4. Метод линейного программирования
Рассмотрим подробнее последний из перечисленных.
Пусть имеется некоторая матричная игра Г=<X,Y,H> (где X и Y — множества стратегий 1го и 2го игроков соответственно, а Н — платежная матрица), H=(aij) Rm*n
Требуется найти оптимальную смешанную стратегию, т.е.
p*=(p1*,p2*,…,pm*) и q*=(q1*,q2*,…,qn*), при которых
,
где v — цена игры.
Для решения этой задачи можно применять линейное программирование.
Будем считать, что все aij0, игра Г’ эквивалентна игре Г, H’=H+L, L — число, при котором неравенство будет выполняться (при переходе от игры Г к игре Г’).
Далее предположим, что 2й игрок принимает стратегию yk, , тогда выигрыш игрока 1 будет определяться условием
p1a1k + p2a2k + … + pmamk v, (*)
(равенство v достигается, если k-я стратегия является рабочей)
pi 0, ;pi aik > 0 v>0 (т.к. левая часть неравенства (*) больше нуля).
Разделим неравенство (*) на v:
|
|
t1a1k + t2a2k +…+ tmamk 1, где ti=, ti 0,
Цель стратегии 1-го игрока — максимизировать выигрыш:
vmax min
Исходя из рассмотренных условий, задачу линейного программирования можно сформулировать так:
1) ti 0,
2) min
3) , причем zk=0 для рабочих стратегий, zk>0 для нерабочих стратегий.
Решение этой задачи позволяет:
1. Вычислить ti*.
2. Определить те k, при которых zk=0 (т.е. найти рабочие стратегии 2го игрока)
3.
4. pi*=ti* v
Для определения стратегии 2го игрока можно поступить двояко:
1) сформулировать двойственную задачу
2) использовать информацию о полезных стратегиях 2-го игрока (полезные стратегии – при zk=0)
Пусть найдена полезная стратегия игрока yj, , . Для определения оптимальной стратегии qj*, для рабочих стратегий 1-го игрока можно записать условие
q1ai1 + q2ai2 + … + qkaik v,
(причем если i-я стратегия 1-го игрока рабочая, то =v,а если нет, то >v)
q1ai1 + q2ai2 + … + qkaik v,
- система уравнений для определения оптимального q.