Линейное программирование для решения матричных игр

Пусть имеется некоторая матричная игра Г=<X,Y,H> (где X и Y — множества стратегий 1го и 2го игроков соответственно, а Н — платежная матрица), H=(a_ij) R^m*n

Требуется найти оптимальную смешанную стратегию, т.е.

p^*=(p₁^*,p₂^*,…,p_m^*) и q*=(q₁^*,q₂^*,…,q_n^*), при которых

,

где v — цена игры.

Для решения этой задачи можно применять линейное программирование.

Будем считать, что все a_ij 0, игра Г’ эквивалентна игре Г, H’=H+L, L — число, при котором неравенство будет выполняться (при переходе от игры Г к игре Г’).

Далее предположим, что 2й игрок принимает стратегию y_k, , тогда выигрыш игрока 1 будет определяться условием

p₁a_1k + p₂a_2k + … + p_ma_mk v, (*)

(равенство v достигается, если k-я стратегия является рабочей)

p_i 0, ; p_i a_ik > 0 v>0 (т.к. левая часть неравенства (*) больше нуля).

Разделим неравенство (*) на v:

t₁a_1k + t₂a_2k +…+ t_ma_mk 1, где t_i= , t_i 0,

 

Цель стратегии 1-го игрока — максимизировать выигрыш:

v max min

Исходя из рассмотренных условий, задачу линейного программирования можно сформулировать так:

1) t_i 0,

2) min

3) , причем z_k=0 для рабочих стратегий, z_k>0 для нерабочих стратегий.

Решение этой задачи позволяет:

1. Вычислить t_i^*.

2. Определить те k, при которых z_k=0 (т.е. найти рабочие стратегии 2го игрока)

3.

4. p_i^*=t_i^* v

 

Для определения стратегии 2го игрока можно поступить двояко:

1) сформулировать двойственную задачу

2) использовать информацию о полезных стратегиях 2-го игрока (полезные стратегии – при z_k=0)

Пусть найдена полезная стратегия игрока y_j, , . Для определения оптимальной стратегии q_j^*, для рабочих стратегий 1-го игрока можно записать условие

q₁a_i1 + q₂a_i2 + … + q_ka_ik v,

(причем если i-я стратегия 1-го игрока рабочая, то =v,а если нет, то >v)

q₁a_i1 + q₂a_i2 + … + q_ka_ik v,

- система уравнений для определения оптимального q.

 

ПРИМЕР.

Пусть имеется некоторая игра с матрицей A=

 

A+5 A₁=

Предположим, что все стратегии рабочие. Составляем систему уравнений:

7t₁ + 2t₂ + 9t₃ - z₁ = 1

2t₁ + 9t₂ - z₂ = 1

9t₁+11t₃ - z₃ = 1

 

Решение этих уравнений при условии t₁ + t₂ + t₃ min:

t₁ = 0,05

t₂ = 0,1

t₃ = 0,05

v(A₁) = = 5 p₁=0,05*5=0,25

p₂=0,1*5=0,5

p₃=0,05*5=0,25

v(A)=v(A₁) - 5=0 игра справедливая. Найдём стратегию второго игрока:

 

q₁^* + q₂^* + q₃^* = 1

2q₁ + 9q₂ = 5 q₁=q₃=0,25

9q₁ + 11q₃ =5 q₂=0,5

 

 

Графическое решение игр 2*n и m*2

Рассмотрим игру (2*n) с матрицей

A=

Выигрыш 1-го игрока H(p,y_k)=p₁a_1k + p₂a_2k = p₁a_1k + (1-p₁)a_2k,

На плоскости такая зависимость изображается отрезком прямой, причем при p=0 H(p,y_k)=a_2k, p=1 H(p,y_k)=a_1k

Таким образом, получаем семейство из n прямых:

Исходя из условия гарантированного выигрыша, его величина при разных значениях р будет определяться нижней границей множества этих прямых. Очевидно, что оптимальная стратегия соответствует той точке полученного множества, в которой значение функции максимально, а само это максимальное значение есть значение игры.

Рабочими стратегиями 2-ого игрока являются в данном случае 3я и 4я, а значит, оптимальная стратегия 1-ого игрока определяется из системы уравнений:

q₃ + q₄ = 1

a₂₃q₃ + a₂₄q₄ = v

 

Рассмотрим теперь игру (m*2) с матрицей

Эту игру удобно рассматривать для второго игрока. Как и в предыдущем случае, строится семейство из m отрезков прямых, отображающих зависимость величины функции выигрыша 2го игрока от выбираемой им стратегии:

Н(x_i,q)= a_i1q + a_i2(1-q), ,

Исходя из разумности поведения 1-ого игрока, проигрыш 2-ого определяется верхней огибающей семейства этих прямых. Значения q* и v находятся как абсцисса и ордината нижней вершины огибающей, а затем оптимальная стратегия 2-ого игрока определяется исходя из его рабочих стратегий (в данном случае рабочими стратегиями 2-ого игрока являются x_r и x_e), аналогично предыдущему случаю.

Во всех этих случаях число рабочих стратегий обоих игроков одинаково.

Бесконечные антагонистические игры\

Антагонистическая игра называется бесконечной, если хотя бы у одного из двух игроков существует бесконечное множество стратегий.

Рассмотрим общие сведения об этих играх.

Имеется игра Г=<X,Y,H>, X и Y — произвольные множества элементов . На каждую ситуацию (x,y) определена функция H=H(x,y), задающая выигрыш 1-ого и проигрыш 2-ого игрока. Обычно считают, что x и y — непрерывно меняющиеся параметры. Функция H(x,y) может быть непрерывной или кусочно-непрерывной.

В бесконечном варианте принцип разумности в поведении игроков сохраняется: 1-ый игрок стремится увеличить свой выигрыш за счет выбора стратегии x , а 2-ый стремится уменьшить свой проигрыш за счет выбора своей стратегии y .

Как и в конечном варианте игры, величину называют нижней ценой игры, — верхней ценой игры. Если , это бесконечная игра с седловой точкой (седловая точка — точка равновесия).

Если (x₀,y₀) — точка равновесия, то H(x,y₀) H(x₀,y₀) H(x₀,y). Любое отклонение от x₀ приводит к уменьшению выигрыша 1-ого игрока, а отклонение от y₀ — к увеличению проигрыша 2-ого.

В геометрии седлообразная точка не зависит от направления, вдоль которого функция возрастает или убывает. В данном случае седловая точка максимальна по x и минимальна по y

Функция H(x,y) должна быть аналитической, т.е. должны существовать ее первые производные по x и по y.

В теории игр нередко максимум и минимум принадлежат границам множеств Х или Y, а не являются внутренней точкой. В общем случае решение нужно искать в смешанном расширении игры.

Общих методов решения бесконечных антагонистических игр в настоящее время не разработано. В литературе описываются некоторые частные виды таких игр, которые предполагают достаточно простое решение, например, строго выпуклые игры на единичном квадрате.