В. А.МАТВЕЕВ

§6. Графоаналитический метод решения матричныхигр2× n иm×2

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

В основе метода лежит утверждение 4.2, которое остаётся верным и в смешанном расширении игры. Седловая точка в матричной игре существует тогда и только тогда, когда выполняется равенство

max	min	f (x,y) = min	max f (x,y) = ν*,
x X	y Y	y Y	x X

причём седловую точку составляют стратегии, доставляющие внешние экстремумы в последнем равенстве.

Пример 6.1. Найти седловую точку матричной игры, заданной матрицей

	2		3	11
A = A2×3
	=	7	5	2

Здесь первый игрок имеет две чистые стратегии, а второй игрок три стратегии. Решаем игру с позиций первого игрока, т.е. с позиций игрока, имеющего две чистые стратегии.

Пусть его смешанная стратегия x = (α, 1−α), 0 ≤α ≤1. Вычислим

2 3		11
				= (2α +7(1 −α), 3α +5(1−α),
xA = (α, 1−α)	7 5	2

11α + 2(1−α)) = (7 −5α, 5 − 2α, 2 −9α).

Обозначим

f1 (α) = 7 −5α,

41

f2 (α) = 5 − 2α,

f3 (α) = 2 +9α.

Найдём

max min ( f1(α), f2 (α), f3 (α)) =

0≤α≤1 i {1,2,3}

max ( min (7 −5α, 5 - 2α, 2 +9α )).

0≤α≤1 i {1,2,3}

Для нахождения максимина приведём геометрическую иллюстрацию на рис.6.1.

f

7				f3 (α)
	E
5			49 C		f2 (α)
	3
B		,
2 A	11		11		D

	f1 (α)
0	1	α
Рис. 6.1.
Вначале для каждого α [0,1]	найдём

min (7 −5α, 5 -2α, 2 +9α ).

i {1,2,3}

На рис.6.1 такие минимумы для каждого α [0,1] образуют

ломаную – нижнюю огибающую АВСD. Затем на огибающей находим наибольшее значение, которое достигается в точке В.

Эта точка реализуется при α [0,1] , которое является решением

42

уравнения

f2 = f3 , т.е.

5-2 α = 2+9 α. Здесь

α =

311. Вторая

координата точки В будет 5 −2

3

=

49

. Итак В(

3

,

49

). В

11

11

11

11

смешанном расширении данной игры

max ( min (7 −5α, 5 - 2α, 2 +9α )) =49 .

0≤α≤1 i {1,2,3}

11

Максиминная стратегия первого игрока xн

= ( α, 1- α) =

(3/11, 8/11).

По аналогичной схеме найдём минимаксную стратегию

второго

игрока.

Его

стратегию

обозначим

y = (0, β, 1 − β), 0 ≤ β ≤1. Первая компонента вектора y равна

0, т.к. максиминная стратегия определяется вторым и третьим столбцом матрицы А. В этом случае в максиминной стратегии

первая компонента равна 0. Для нахождения β [0, 1] в матрице

А оставим только второй и третий столбцы. Вычислим

×	T		3 11		β
A y						= (3β +11(1− β), 5β + 2(1 − β)) =
		=	5 2
				1	− β

(11 −8β, 2 +3β) .

Обозначим

f1 (β) =11 −8β ,

f1 (β) = 2 +3β.

Найдём

min max ( f1(β), f2 (β)) =

0≤β≤1 i {1,2}

min (max (11−8β, 2 +3β)).

0≤β≤1 i {0,1}

Для нахождения минимакса приведём геометрическую иллюстрацию на рис.6.2.

43

f

K

11 f1(β)

		9		49
	L		,
		11		11

M

2 f2 (β)

0		1 β
Рис.	6.2.

Вначале для каждого β [0,1] найдём

min (11−8β, 2 +3β).

i {1,2}

На рис.6.2 такие минимумы для каждого β [0,1] образуют

ломаную – верхнюю огибающую KLM. Затем на огибающей находим наименьшее значение, которое достигается в точке L.

Эта точка появляется при β [0,1] ,		которое является решением
уравнения f1 = f2 , т.е. 11-8 β = 2+3 β . Здесь						β = 911. Вторая
координата точки L будет 11−8 9	11		= 49	11	. Итак L(		9	,	49	). В
						11		11
смешанном расширении данной игры
min (max (11−8β, 2 +3β)) =49 .
0≤β≤1 i {1,2}					11
Минимаксная стратегия второго игрока yB = (0,						β, 1-β) = (0, 9/

11, 2/11).

В примере выполнены условия утверждения 4.2. В самом деле, минимакс и максимин существуют и выполнено равенство

νB = νН = 49/11.

44

Значит цена игры ν * = 49/11 и седловая точка (x*, y*) = ((3/11, 8/ 11), (0, 9/11, 2/11)).

Витоговой проверке следует продемонстрировать

выполнение равенства			(x*)T A( y*) =v *.					В данном случае
получаем
						0
			2	3 11
( 3 , 8						9	= 49 .
	)
11	11		7			11		11
				5 2
						2
						11

Это верное равенство.

Ответ : (x*, y*) = ((3/11, 8/11), (0, 9/11, 2/11)), ν * = 49/11 .

Пример 6.2. Найти седловую точку матричной игры, заданной матрицей

1 4 A3×2 = 3 - 20 5

Здесь игрок 1 имеет три чистые стратегии, а второй игрок две стратегии. Решаем игру с позиций второго игрока, т.е. с позиций игрока, имеющего две чистые стратегии.

Пусть стратегия второго игрока					y = (β, 1− β), 0 ≤ β ≤1.
Вычислим
	1 4		β		4		−3β
	3 - 2					5β − 2
A yT =			−		=			.
	0 5	1		β		5	−5β

Обозначим

f1 (β) = 4 −3β , f2 (β) = 5β −2, f3 (β) = 5 −5β.

45

Найдём

min max ( f1(β), f2 (β), f3 (β)) =

0≤β≤1 i {1,2,3}

min ( max (4 −3β, 5β−2, 5 −5β)).

0≤β≤1 i {1,2,3}

Для нахождения минимакса приведём геометрическую иллюстрацию на рис.6.3.

f

5	H
4	J		3		7		L	f	2	(β)
		K		,
			4		4
								f1(β)
0							1	β
−2	Рис. 6.3.							f3 (β)

Вначале для каждого β [0,1] найдём

max (4 −3β, 5β−2, 5 −5β).

i {1,2,3}

На рис.6.3 такие максимумы для каждого β [0,1] образуют

ломаную – верхнюю огибающую HJKL. Затем на огибающей находим наименьшее значение, которое достигается в точке K.

Эта точка будет при β [0,1] , которое является решением

	уравнения	f1 = f2 ,	т.е. 4-3 β = 5 β -2.			Значит β = 34. Вторая
	координата	точки	K есть 4 −3 3	4	= 7	4	. Итак	K(	3	,	7	).	В
									4		4

смешанном расширении данной игры

46

min ( max (4 −3β, 5β−2)) = 74 .

0≤β≤1 i {1,2,3}

Определим и минимаксную стратегию второго игрока. Это

yВ = (3 4 , 14).

По аналогичной схеме найдём максиминную стратегию первого игрока. Его стратегию обозначим

x = (α, 1−α, 0), 0 ≤α ≤1. Третья компонента вектора x равна

0, т.к. минимаксная стратегия второго игрока определяется первым и вторым строками матрицы А. В этом случае в максиминной стратегии третья компонента равна 0.

Вычислим

1		4
	3	−2		=
xA = (α, 1−α, 0)
	0 5

= (1α +3(1−α) + 0 0, 4α - 2(1 −α) +0 5) = (3 −2α, 6α −2) .

Обозначим

f1 (α) = 3 − 2α,

f2 (α) = 6α −2.

Найдём

max min ( f1(α), f2 (α)) =

0≤α≤1 i {1,2}

max ( min (3 −2α, 6α,−2)).

0≤α≤1 i {1,2}

Для нахождения максимина приведём геометрическую иллюстрацию на рис.6.4.

Вначале для каждого α [0,1] найдём

min (3 − 2α, 6α- 2).

i {1,2}

47

f

3N 5, 7

8 4

		P
	0	α
		Рис. 6.4.
	−2 M

Нарис.6.4 такиеминимумы длякаждого α [0,1] образуютломаную

– нижнюю огибающую MNP. Затем на огибающей находим наибольшее значение, которое достигается в точке N. Эта точка

появляется при α [0,1] и является решением уравнения f1 = f2 ,

т.е. 3-2a = 6a-2. Здесь a = 5 8 . Вторая координата точки N будет

	3 − 2 5	8	= 7	4	. ИтакN(	5	,	7	). Всмешанномрасширенииданнойигры
						8		4
					max ( min (3 −2α,					6α,−2))	= 7	.
					0≤α≤1	i {1,2}					4

Максиминная стратегия первого игрока xН = ( α, 1- α, 0) = (5/8, 3/8, 0).

В примере выполнены условия утверждения 4.2. В самом деле, минимакс и максимин существуют и выполнено равенство

	νB = νН = 7/4.
Значит цена игры	ν * = 7/4 и седловая точка (x*, y*) =
((5/8, 3/8, 0), (3/4, 1/4)).
В итоговой проверке следует продемонстрировать
выполнение равенства	(x*)T A( y*) =v *. В данном примере
получаем

48

						1 4			3
(5		, 3		, 0)		3 - 2				4		= 7
	8		8						1				4 ,
						0 5				4
верное равенство.
Ответ : (x*, y*) = ((5/8,						3/8, 0), (3/4,						1/4)), ν * = 7/4 .

Наконец, решим отложенный из §3 Пример 3.3. (Орлянка, окончание ). Напомним, что эта игра

представлена матрицей

	1		−1
A2×2
	=	−1	1

Здесь игрок 1 и игрок 2 имеет две чистые стратегии. Решаем игру с позиций первого игрока.

Пусть его стратегия x = (α, 1−α),0 ≤α ≤1. Вычислим

1		-1
				= (α −(1−α), -α +1 −α) =
xA = (α, 1−α)	-1	1

(2α −1, 1− 2α).

Обозначим

f1 (α) = 2α −1,

f2 (α) =1 −2α.

Найдём

max min ( f1(α), f2 (α)) =

0≤α≤1 i {1,2}

max ( min (2α −1, 1-2α )).

0≤α≤1 i {1,2}

Для нахождения максимина приведём геометрическую иллюстрацию на рис.6.5.

49

f

1				f1(α)
	1
	P	2	,0
					α
0				1
					f2 (α)
−1	M			Q

Рис. 6.5.

Вначаледля каждого α [0,1] найдём

min (2α −1, 1- 2α ).

i {1,2}

На рис.6.5 такие минимумы для каждого α [0,1] образуют

ломаную – нижнюю огибающую MPQ. Затем на огибающей находим наибольшее значение, которое будет в точке P. Эта точка

достигается при α [0,1] , которое является решением уравнения

f1 = f2 ,	т.е. 2 α - 1 = 1 - 2 α. Здесь						α =	1 2 . Вторая координата
точки P	будет	2 1	2	−1 =	0	. Итак	P( 1	2	, 0).	В смешанном

расширении данной игры

max ( min (2α−1, 1- 2α )) = 0.

0≤α≤1 i {1,2}

Максиминная стратегия первого игрока xн = ( α, 1- α) = (1/2, 1/2).

По аналогичной схеме найдём минимаксную стратегию второго игрока. Его стратегию обозначим

y = (β, 1− β), 0 ≤ β ≤1.

Вычислим

50