Методы решения матричных игр

	Ai \Bj B1 … BN A1(1)       …   ||aij||   AN

 

1) Проверить на наличии седловой точки.

2) Если нет седловой точки, то матрицу игры упрощают.

Из матрицы игры исключают доминируемые и дублируемые стратегии.     

Задача: найти стратегии S_A =(p₁, p₂…, p_N) и S_B =(q₁, q₂…, q_N), дающие максимальный средний выигрыш.

Игра mxn, число активных стратегий будет равняться min(m,n)

Определение.

       Стратегия A_i доминирует () A_k, то есть A_i  A_k, значит:

j a_ij  a_kj

Определение.

       Стратегия A_i дублирует (=) A_k, то есть A_i = A_k, значит:

j a_ij = a_kj

 

       Стратегия B_j  B_r, i   a_ij  a_rj

       Стратегия B_j = B_r, i a_ij = a_rj

	Ai \Bj B1 B2 B3 B4 B5 A1 4 7 2 3 4 A2 3 5 6 8 9 A3 4 4 2 2 8 A4 3 6 1 2 4 A5 3 5 6 8 9

       Пример: игра (5x5)

           

       A₁  A₄

A₂ = A₅

 

 

	Ai \Bj B1 B2 B3 B4 B5 A1 4 7 2 3 4 A2 3 5 6 8 9 A3 4 4 2 2 8

B₁  B₂

B₁  B₅

 

 

	Ai \Bj B1 B3 A1 4 2 A2 3 6

A₂₁ = A₅

 

Получим S_A = (p₁, p₂, 0, 0, 0)

        S_B = (q₁, 0, q₂, 0, 0)

           

 

 

Метод Лагранжа

Этот метод используется в играх с квадратной матрицей игры G(m,m).

 

	B1	B2
A1	а11	а12
A2	а21	а22

 

 

S_A=(p₁,p₂) - вектор вероятностей выбора стратегий игроком А.

S_B=(q₁,q₂) - вектор вероятностей выбора стратегий игроком В.

 

Пусть игрок А использует смешанные стратегии, а В чистые, тогда выигрыш составит:

 

V₁=a₁₁*p₁+a₂₁*p₂

V₂=a₁₂*p₁+a₂₂*p₂

если же В также использует смешанные стратегии, то выигрыш составит:

 

V=(a₁₁*p₁+a₂₁*p₂)*q₁+(a₁₂*p₁+a₂₂*p₂)*q₂

 

Строится функция Лагранжа:

 

L=(a₁₁*p₁+a₂₁*p₂)*q₁+(a₁₂*p₁+a₂₂*p₂)*q₂+l₁*(p₁+p₂-1)+ l₂*(q₁+q₂-1)

 

     q₁, q₂    

 

   p₁, p₂

                  p₂ =1- p₁  

                  q₂ =1- q₁         

 

 

Получим

 

 ;

 ;

;

 

Пример.

 

G(2,2)

 

	B1	B2
A1	4	2
A2	3	6

 

 

Метод линейного программирования

 

Этот метод используется в играх с произвольной матрицей игры G(m,n).

 

	B1	B2	…	Bj	…	Bn
A1	а11	а12	…	а1j	…	а1n
A2	а21	а22	…	а2j	…	а2n
…	…	…	…	…	…	…
Ai	аi1	аi2	…	аij	…	аin
…	…	…	…	…	…	…
Am	аm1	аm2	…	аmj	…	аmn

 

S_A=(p₁,p_2,…, p_i,…, p_n) - вектор вероятностей выбора стратегий игроком А.

S_B=(q₁,q_2,…, q_j,…, q_n) - вектор вероятностей выбора стратегий игроком B.

Требование, накладываемое на матрицу -  "i, j a_ij>0

 

Для того, чтобы произвольная матрица удовлетворяла этому требованию ищется M=мах(|а_ij||a_ij<0) и прибавляется ко всем элементам, получаем a_ij+M>0.

 

 

Пусть А выбирает смешанную(оптимальную) стратегию, а В чистую:

 

Введем величину ³0, i=1,…,m

Тогда:

 

(*)     x_i³0 i=1,…,m

 

Т.к.

 

Получаем задачу линейного программирования:

при системе ограничений (*).

Решив ее, найдем (x_1, x_2,…, x_m) и

Зная V, найдем p_i=x_i*V.

 

 

Итерационный метод Брауна-Робинсона