Матричное представление парной антагонистической игры

 

Число стратегий конечно.

Игрок A: {A_i}  i=1…m

Игрок B: {B_j}  j=1…n

 

Ai \Bj	B1	…	Bj	…	Bn
A1	a11	…	a1j	…	a1n
…	…	…	…	…	…
Ai	ai1	…	aij	…	ain
…	…	…		…	…
Am	am1	…	amj	…	amn

 

a_ij – это выигрыш игрока A при выборе им стратегии A_i, и игрок B отвечает ему стратегией B_j.

 

 

Пример.

 

                       

 

 

 

Построим матрицу игры. Возможны два случая:

1. Ситуация с неполной информацией. (Игроку В не сообщается о выборе игрока А).

 

2. Ситуация с полной информацией.

	Ai \Bj B1(3) B2(4) B3(+) B4(-)     B2(4) A1(1) 4 -5 4 -5     -5 A2(2) -5 6 6 -5     6

 

 

       B₃(+) -игрок В действует также, как и игрок А.

 

       Вводятся две величины:

       max min a_ij = a нижняя оценка цены игры

 i     j

       min max a_ij = b верхняя оценка цены игры

i     j

       Докажем, что a <= b

Ai \Bj	B1	…	Bj’	…	Bj	…	Bn
A1	a11	…	a1j	…	a1j	…	a1n
…	…	…	…	…	…	…	…
Ai’	ai1	…	ai’j’	…	ai’j	…	ain
…	…	…	…	…	…	…	…
Ai	ai1	…	aij’	…	aij	…	ain
…	…	…		…		…	…
Am	am1	…	amj	…	amj	…	amn

       a_ij’ = a <= a_ij <= a_i’j’ = b

Если a = b = V, то говорят, что игра имеет седловую точку, а решением игры является пара чистых стратегий A_i*,B_j*, дающая максимальный выигрыш и минимальный проигрыш равный V равный цене игры.

 

       Теорема 1.

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

 

Пример:

 

 

       max min a_ij = -5                                    max min a_ij = -5

i     j                                                                                          i     j

       min max a_ij = 4                                      min max a_ij = -5

i     j                                                                                          i     j

       Седловой точки нет                                 (A₁,B₄) = (A₂,B₄) = V = 5

 

       Если нет седловой точки:

1) Однократно, следовательно, необходимо использовать наиболее осторожный метод maxmin.

2) Многократно – используются смешанные стратегии.

то есть каждой стратегии соответствует вероятноть:

       A_i, p_i   p_i

       B_j, q_j     q_j  

Решением будет смешанная стратегия

       S_A =(p₁, p₂…, p_N)

       S_B =(q₁, q₂…, q_N)

           

Теорема 2. (Основная теорема теории игр)

       Всякая парная антагонистическая игра имеет хотя бы одно решение, то есть пару стратегий S_A*, S_B* в общем случае смешанных, дающих устойчивый выигрыш равный цене игры V. И в этом случае можно доказать, что:

       a <= V <= b

 

S_A - чистая стратегия, следовательно S_A = (0, …, 0, 1, 0, ….,0)