2 Решение матричной игры (2х2)

2.5. Решение матричной игры (2х2)


Пусть матричная игра G (2x2) имеет платежную матрицу

Bj Ai	B1	B2
A1	a11	a12
A2	a21	a22

Предположим, что игра не имеет седловой точки, т.е. . При наличии седловой точки решение очевидно, тогда в соответствии с основной теоремой игра имеет оптимальное решение в смешанных стратегиях: S_A=||p₁, p₂|| и S_B=||q₁, q₂||, где вероятности применения чистых (относительные частоты применения) чистых стратегий удовлетворяют соотношениям

p₁+p₂=1; (2.11.)

q₁+q₂=1. (2.12.)

В соответствии с теоремой об активных стратегиях, оптимальная смешанная стратегия обладает тем свойством, что обеспечивает игроку максимальный средний выигрыш, равный цене игры , независимо от того, какие действия предпринимает другой игрок, если он не выходит за пределы своих активных стратегий. В частности, если игрок А использует свою оптимальную смешанную стратегию, а игрок В - свою чистую активную стратегию В₁, то цена игры  равна

а₁₁р₁+а₂₁р₂= (2.13.)

а при использовании игроком В чистой активной стратегии В₂, выигрыш будет равен

а₁₂р₁+а₂₂р₂= (2.14.)

Уравнения (11), (13) и (14) образуют систему трех линейных алгебраических уравнений с тремя неизвестным:

р₁, р₂ и 

Р

ешая ее, легко находим, что


(2.15.)



(2.16.)



(2.17.)


Если игрок В использует свою оптимальную смешанную стартегию, а игрок А - свою чистую активную стратегию А₁, то цена игры  равна

а₁₁q₁+а₂₁q₂= (2.18.)

а при использовании игроком А чистой активной стратегии А₂, выигрыш будет равен

а₂₁q₁+а₂₂q₂= (2.19.)

Уравнения (2.12), (2.18) и (2.19) образует систему трех линейных алгебраических уравнений с тремя неизвестными:

q₁; q₂ и 

Решая ее, легко находим, что




(2.20)



(2.21)



(2.22)


Естественно, что в обоих случаях цена игры (выражения (2.17) и (2.22)) получилась одна и та же.

Чтобы соотношения ((2.15), (2.16), (2.17), (2.20), (2.21), (2.22)) имели смысл, необходимо потребовать, чтобы



или



тогда 0
₁<1; 0
₂<1; 01<1; 02<1

Нетрудно заметить, что в этих неравенствах отражено предположение об отсутствии в рассматриваемой игре седловой точки. Действительно, ни один из четырех выигрышей а₁₁, а₁₂, а₂₁, а₂₂ не может удовлетворить этим неравенствам, будучи минимальным в своей строке и максимальным в своем столбце.

Решения системы уравнений (2.15), (2.16), (2.17) и (2.20), (2.21), (2.22), полученные алгебраическим методом, удобно получать и графическим методом (рис. 2.4). Для нахождения вероятностей р₁, р₂ и цены игры v в прямоугольной системе координат по оси абсцисс откладывается вероятность р₁[0,1], а по оси ординат - соответствующие этой вероятности - выигрыши игрока А.



Рис. 2.4.

При р₁=0, игрок А применяет чистую стратегию ^ А₂. Если при этом игрок В применяет чистую стратегию В₁, то выигрыш игрока А равен а₂₁ (уравнение (13), а если игрок В применяет чистую стратегию В₂, то выигрыш игрока А равен а₂₂ (уравнение (14)). При р₁=1, игрок А применяет чистую стратегию А₁. Если при этом игрок В применяет чистую стратегию В₁, то выигрыш игрока А равен а₁₁, а при применении чистой стратегии В₂ - а₁₂. Так как значения р₁ лежат в пределах [0,1], то соединяя крайние точки для стратегий В₁ и В₂ (строя графики функций v=(a₁₁-a₂₁)p₁+a₂₂ и v=(a₁₂-a₂₂)p₁+a₂₂, получаем значения выигрышей игрока А для всех промежуточных значений р₁.

В соответствии с принципом максимина, игрок ^ А должен выбрать такую смешанную стратегию, при которой его минимальный выигрыш максимален. Точка N пересечения отрезков прямых (рис. 4) и определяет как оптимальную цену игры v_opt, так и оптимальные вероятности p_1opt и p₂=1-p_1opt, соответствующие оптимальной смешанной стратегии игрока А, т.е. дает решения системы уравнений (2.11), (2.13), (2.14).

Для графического решения системы уравнений (2.12), (2.18), (2.19) отложим по оси абсцисс вероятность q₁[0,1], а по оси ординат соответствующие этой вероятности выигрыши игрока В:

v=(a₁₁-a₁₂)q₁+a₁₂; (2.23)

v=(a₂₁-a₂₂)q₁+a₂₂ (2.24)



Рис. 2.5.

Решением являются координат точки М пересечения прямых, описываемых уравнений (2.23) и (2.24):

q_1opt:q_2opt=1-q_1opt и v_opt

Это же следует и из принципа максимина, в соответствии с которым игрок В должен выбрать такую смешанную стратегию, при которой его максимальный проигрыш будет минимами.

Для игры G(2х2) с седловой точкой геометрическая интерпретация решения быть представлена, например, следующим образом (рис.2.6.)



Рис. 2.6.

Стратегия В₂ игрока В является для него явно невыгодной, так как, применяя ее, он в любой случае проигрывает больше, чем при применении стратегии В₁. В данной игре р_1opt=1;р_2opt=0; v_opt=а₁₁, т.е. игра имеет седловую точку N и решается в чистых стратегиях. Игрок А должен применять стратегию А₁, а игрок В - стратегию В₁.

На рис. 2.7 показан случай, в котором решением игры для игрока А является чистая стратегия А₂, а для игрока В - стратегия В₁.



Рис. 2.7

Игра имеет седловую точку N.

Пример: Найти алгебраическим и геометрическим методами решение игры, платежная матрица которой имеет вид

Bj Ai	B1	B2	i
A1	4	-2	-2
A2	1	3	1
j	4	3

В данной игре нижняя цена игры =1 не равна верхней цены игры =3, поэтому игра не имеет седловой точки и, в соответствии с основной теоремой матричных игр, имеет оптимальное решение в смешанных стратегиях.

Для игрока А, в соответствии с формулами (2.15) и (2.16), оптимальные вероятности применения стратегий А₁ и А₂ равны:







Для игрока В, в соответствии с формулами (2.20) и (2.21), оптимальные вероятности применения стратегий В₁ и В₂ равны:







Таким образом, оптимальные смешанные стратегии игроков ; , а цена игры в соответствии с формулой (2.22) равна:



Так как , то игра выгодна для игрока А.

Графическое изображение игры для игрока А показана на рис. 2.8.




Рис. 2.8.

Нижняя граница выигрыша игрока А определяется ломаной CND. Оптимальное решение, определяется точкой N, естественно, дает тоже решение, что и алгебраический метод: .

Географическое изображение игры для игрока В показана на рис.2.9.




Рис. 2.9.

Оптимальное решение определяемое точкой М, дает решение .


ЗАДАЧИ

Определите алгебраическим и геометрическим методами оптимальные решения следующих игр 2х2:

1.		B1	B2		2.		B1	B2		3.		B1	B2
	A1	5	2			A1	-3	-6			A1	6	9
	A2	-1	0			A2	-4	-5			A2	7	8
4.		B1	B2		5.		B1	B2		6.		B1	B2
	A1	0	7			A1	8	6			A1	0	-1
	A2	10	4			A2	4	7			A2	-3	0
7.		B1	B2		8.		B1	B2		9.		B1	B2
	A1	-10	-16			A1	7	9			A1	1	2
	A2	-12	-14			A2	13	11			A2	4	3
10.		B1	B2		11.		B1	B2		12.		B1	B2
	A1	-3	-2			A1	0	2			A1	-1	1
	A2	0	-2			A2	3	1			A2	2	0
13.		B1	B2		14.		B1	B2		15.		B1	B2
	A1	6	-2			A1	4	-5			A1	5	6
	A2	-2	6			A2	-5	4			A2	6	5
16.		B1	B2		17.		B1	B2		18.		B1	B2
	A1	4	7			A1	4	-5			A1	8	-1
	A2	5	4			A2	-4	5			A2	1	9
19.		B1	B2		20.		B1	B2		21.		B1	B2
	A1	6	9			A1	1	-3			A1	4	-2
	A2	13	11			A2	-8	5			A2	-3	5
22.		B1	B2		23.		B1	B2		24.		B1	B2
	A1	5	8			A1	6	9			A1	2	5
	A2	7	6			A2	8	7			A2	3	4
25.		B1	B2		26.		B1	B2		27.		B1	B2
	A1	0	-3			A1	12	3			A1	4	-5
	A2	-1	0			A2	9	7			A2	1	-1