6. Матричная игра

Два игрока А и В играют в матричную игру. Дана платёжная матрица (А), отражающая выигрыш игрока А или проигрыш игрока В при использовании ими их стратегий.

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

Попытаемся упростить матрицу А, если это возможно, за счёт выявления дублирующих и доминирующих стратегий.

Стратегия A_e дублирует стратегию A_k, если элементы e-строки равны элементам k-строки.

Стратегия B_m дублирует стратегию B_n, если элементы m-столбца равны элементам n-столбца.

В нашем случае B₁ дублирует B₄. Исключим B₄ из рассмотрения.

Стратегия A_L доминирует стратегию A_k, если элементы L-строки превышают или равны элементам k-строки. Доминируемая k-стратегия из рассмотрения исключается.

1-я стратегия доминирует 2-ую стратегию, так что 2-ую стратегию из рассмотрения исключаем.

Стратегия Bm, доминирует стратегию Bn, если элементы m-столбца меньше или равны элементам n-столбца. Доминируемая n-стратегия из рассмотрения исключается. В нашем случае такого нет.

Выясним, есть ли решении игры в чистых стратегиях (проверим на оседлую точку).

A\B	B1	B2	B3	B4	αi
A1	9	-2	1	0	-2
A2	-3	4	-5	6	-5
A3	5	-7	8	-9	-9
βj	9	4	8	6

α≠β, т.е. можно сделать вывод, что игры в чистых стратегиях нет.

Введём новые переменные: для игрока A P(p₁,p₂,p₃) , т.е. вероятности использования игроком А 1-ой стратегии, 2-ой стратегии и т.д. соответственно, для игрока B Q(q₁,q₂,q₃,q₄) , т.е. вероятности использования игроком B 1-ой стратегии, 2-ой стратегии и т.д. соответственно. Так же введем υ – цену игры.

Добавим к каждому элементу матрицы значение +9, чтобы выигрыши были неотрицательные.

A\B		q1	q2	q3	q4
		B1	B2	B3	B4
p1	A1	18	7	10	9
p2	A2	6	13	4	15
p3	A3	14	2	17	0

Пусть игрок В играет по оптимальной стратегии, а игрок А – по чистым.

A1: 18*q₁+ 7*q₂+ 10*q₃+ 9*q₄<= υ

A2: 6*q₁+ 13*q₂+ 4*q₃+ 15*q₄<= υ

A3: 14*q₁+ 2*q₂+ 17*q₃+ 0*q₄<= υ

П

(_*)

оделим данные три неравенства на υ>0 и введём новую переменнуюx_j=q_j/ υ при x_j=>0 j=1,2,3,4 , тогда получим:

18*x₁+ 7*x₂+ 10*x₃+ 9*x₄<= 1

6*x₁+ 13*x₂+ 4*x₃+ 15*x₄<= 1

14*x₁+ 2*x₂+ 17*x₃+ 0*x₄<= 1

x_j=>0 j=1,2,3,4

Так как q₁,q₂,q₃,q₄ – вероятности использования стратегий игроком В, то:

q₁+q₂+q₃+q₄=1 Делим на υ>0 и получаем:

q₁/υ +q₂/υ +q₃/υ +q₄/υ =1/υ

x₁+x₂+x₃+x₄=1/υ

Так как υ – проигрыш игрока В, то он хочет минимизировать, тогда 1/υ – максимизировать. Итак, приходим к постановке задачи: найти значение вектора X=( x₁; x₂; x₃; x₄ ), которое обеспечивало бы максимальное значение функции x₁+x₂+x₃+x₄=1/υ=Z → max при следующих линейных ограничениях (*).

Решим задачу симплексным методом.

C	Базис	H	х1	х2	х3	х4	х5	х6	х7	Примечание
0	Х5	1	18	7	10	9	1	0	0	Min ∆j=-1 х2 – в базис min(1/7;1/13;1/2)=1/13 х6 – из базиса 2-е ур-ие разрешающее
0	Х6	1	6	13	4	15	0	1	0
0	Х7	1	14	2	17	0	0	0	1
		0-Z	-1	-1	-1	-1	0	0	0
										Min ∆j=-9/13 х3 – в базис min(1/17;1/4;11/213)=11/213 x7 – из базиса 3-е ур-ие разрешающее
0	X5	6/13	192/13	0	102/13	12/13	1	-7/13	0
1	Х2	1/13	6/13	1	4/13	15/13	0	1/13	0
0	Х7	11/13	170/13	0	213/13	-30/13	0	-2/13	1
		1/13-Z	-7/13	0	-9/13	2/13	0	1/13	0
										Все ∆j=>0 => решение оптимальное
0	Х5	4/71	604/71	0	0	144/71	1	-33/71	-34/71
1	Х2	13/213	46/213	1	0	85/71	0	17/213	-4/213
1	Х3	11/213	170/213	0	1	-10/71	0	-2/213	13/213
		8/71-Z	1/71	0	0	4/71	0	5/71	3/71

X=(0; 13/213; 11/213; 0)

Zmax=1/υ=8/71

Тогда цены игры υ=71/8

q_i=x_i* υ i=1,2,3,4

q₁=0*71/8=0

q₂=13/213*71/8=13/24

q₃=11/213*71/8=11/24

q₄=0*71/8=0

Оптимальная стратегия игрока В (0; 13/24; 11/24; 0).

Ч

(_**)

тобы найти стратегии игрока А, нужно решить двойственную задачу:

18*y₁+6*y₂+14*y₃=>1

7*y₁+13*y₂+2*y₃=>1

10*y₁+4*₂+17*y₃=>1

9*y₁+15*y₂+0*y₃=>1

y_i=p_i/υ =>0 i=1,2,3

Так как p₁+p₂+p₃=1, то y₁+y₂+y₃=1/ υ.

Так как υ – выигрыш игрока А, то он хочет максимизировать, тогда 1/υ – минимизировать. Итак, приходим к постановке задачи: найти значение вектора Y=( y₁; y₂; y₃; y₄ ), которое обеспечивало бы минимальное значение функции y₁+y₂+y₃=1/υ=L → min при следующих линейных ограничениях (**).

Эта задача является двойственной по отношению к рассмотренной выше задачи, так что решение возьмём из последней симплексной таблицы.

Y=(0; 5/71; 3/71)

Lmin=Zmax=1/υ=8/71

υ=71/8

p_i=y_i* υ i=1,2,3

p₁=0*71/8=0

p₂=5/71*71/8=5/8

p₃=3/71*71/8=3/8

Оптимальная стратегия игрока А (0; 5/8; 3/8).

Теперь возвращаемся к начальной матрице А_4,5 , тогда её решение имеет вид:

A\B		q1=0	q2=13/24	q3=11/24	q4=0	q5=0
		B1	B2	B3	B4	B5
p1=0	A1	9	-2	1	9	0
p2=0	A2	-3	-7	-5	-3	-9
p3=5/8	A3	-3	4	-5	-3	6
p4=3/8	A4	5	-7	8	5	-9

А цена игры υ=71/8 - 9= - 1/8.

Теперь, имея все данные, найдем риски игроков при использовании ими своих оптимальных и чистых стратегий. Нижний индекс соответствует игроку А, верхний – игроку В.

υ=M(P,Q)=∑∑a_ij*p_i*p_j= - 1/8

Найдём риск игры при использовании игроками своих оптимальных стратегий:

D₀⁰=∑∑(a_ij)²*p_i*q_j - υ²=1073/32-1/64=2145/64;

D₀²=∑(a_i2)²*p_i - υ²=1815/64;

D₀³=∑(a_i3)²*p_i - υ²=2535/64;

D₃⁰=∑(a_3j)²*q_j - υ²=1287/64;

D₄⁰=∑(a_4j)²*q_j - υ²=3575/64;

Минимальное значение риска равно: . Данные риск соответствует ситуации, когда игрок А играет по 3-ей чистой стратегии, а игрок В по оптимальной.

Так как минимальное найденное значение риска меньше чем значение риска при использовании игроками своих оптимальных стратегий, то можно сделать вывод , что играть они могут только при договорённости.