MMP_5

Платежную матрицу удобно также представить в виде таблицы 5

B j	B1		B2			Bn
Ai
A1	a11		a12			a1n
A2	a21		a22			a2n
Am	am1		am2			amn

В ее строках расположены чистые стратегии игрока А, а в столбцах –

чистые стратегии игрока В.

Цель матричной игры – выбор наиболее выгодных стратегий,

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

В. Оптимальной для игрока В называют стратегию, при которой проигрыш игрока В не увеличивается при любой стратегии игрока А. При поиске оптимальных стратегий игроки соблюдают принцип осторожности, согласно которому противник является по меньшей мере таким же разумным и не упустит ни единой возможности использовать любую ошибку соперника в своих интересах. Пусть игрок А выбрал некоторую стартегию Ai . Сначала он

найдет минимальное значение ожидаемого выигрыша: i			min aij j		, а
				1, m
			j
затем из всех i выберет наибольшее min ai i		.
	1, m
i
Число называют нижней ценой игры и является гарантированным
выигрышем игрока А.
Очевидно, находится в одной из строк матрицы H, к примеру в

строке i0 . Тогда стратегию Ai 0	называют максиминной, т.к. max(min aij ) .
	i	j

60

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

найдет максимально возможный проигрыш – j		max aij j 1 n , а затем
		i
среди j выберт минимальное	значение	min j . Ему будет
		j
соответствовать чистая стратегия	B j 0 , называемая минимаксной, т.к.

min(max aij ) . Число называют верхней ценой игры. Оно показывает
j	i

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

правильно используя чистые стратегии, игрок А обеспечит выигрыш не меньше , а игрок В не позволит игроку А выиграть больше чем .

Рассмотрим примеры нахождения и .

Пример 1. Пусть игра задана платежной матрицей 4 3:

	3	1	0
	2	1	4
H	5	7	6
	4	8	2

Выпишем для каждой строки справа от матрицы min aij						, а снизу max aij
					j	i
каждого столбца. Тогда получим
	3	1	0		1
	2	1	4		1
	5	7	6		5
	4	8	2		2
	5	8	6

max min aij max 1;1; 5; 2 5

ij

min max aij		min 5; 8; 6 5
j	i

Верхняя и нижняя цены игры совпали: 5.

61

Пример 2. Задана платежная матрица

	4	7	10	1		1
H	0	3	2	6		0
	5	4	9	8		4
	5	7	10	8

max 1; 0; 4 4

min 5; 7;10; 8 5

Здесь 4 5 .

Теорема 1. В любой матричной игре нижняя цена игры не превосходит верхней цены игры, т.е. .

Обозначим через i0 и j0 номера чистых стратегий, при котором .

Пару чистых стратегий Ai 0 и B j 0 при этом называют седловой точкой

игры, а aij – седловым элементом платежной матрицы.

Число называют чистой ценой игры. Простота решения игры

с седловой точкой заключается в том, что сразу найдены оптимальные стратегии: максиминная Ai 0 для игрока А и минимаксная B j 0 для игрока В, а

цена игры – седловой элемент платежной матрицы: ai0 j 0 .

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

Максиминные и минимаксные стратегии называют общим термином – минимаксными стратегиями, а их выбор – принципом минимакса.

Решение матричных игр в смешанных стратегиях

Рассмотрим конечные матричные игры, в которых нет седловой точки,

т.е. .

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

. Таким образом, для цены игры справедливо соотношение

62

(48)

Если игра повторяется неоднократно, то постоянный выбор игроками

минимаксных стратегий не логичен. Действительно, игрок В, зная что игрок

А применяет лишь минимаксную стратегию Ai 0 , выберет иную стратегию – стратегию, соответствующую наименьшему элементу в строке i0 платежной матрицы. Такие же рассуждения имеют место и для поведения игрока А.

Следовательно, при неоднократном повторении игры игрокам необходимо менять стратегии. Выясним механизм выбора игроками оптимальных стратегий, а также что принять за стоимость игры.

Рассмотрим матричную игру, заданную таблицей 6.

Таблица 6

	Ai						B j			pi
				B1	B2				Bn
	A1		a11		a12				a1n	p1
	A2		a21		a22				a2n	p2
	Am		am1		am2				amn	pm
	q j			q1	q2				qn
Через pi i				и q j	j		обозначим соответственно вероятности
			1, m			1, n

(относительные частоты), согласно которым игроки А и В выбирают стратегии Ai и B j .

		i 1 m ,	m			q j 0 j		,	n
Очевидно, что pi 0			pi	1,			1, n		q j	1.
			i 1						j 1
Упорядоченные множества	p ( p1 , p2 , , pm )			и q (q1 , q1 ,...,qn ) полностью
	63

определяет характер игры игроков А и В и называются их смешанными стратегиями. Отметим, что любая их чистая стратегия Ai и B j может быть

описана как смешанная. Действительно, p (0, ...,0,1, 0, ...,0) или q (0, ...,0,1, 0, ...,0) .

Пусть игроки А и В применяют смешанные стратегии p и q, выбирают их случайно. Тогда вероятность выбора комбинации Ai B j будет равна pi q j .

Игра приобрела случайный характер. Следовательно, случайной становится и величина выигрыша.

Этой величиной является математическое ожидание выигрыша,

которое определяется формулой:

m n

f( p, q) aij pi q j

i 1 j 1

Функцию f ( p, q) называют платежной функцией игры с заданной

матрицей. Как и выше, введем понятие нижней и верхней цены игры,

сохраняя при этом обозначения и :

max min f ( p, q) , min max f ( p, q) .

p	q	q p
Оптимальными смешанными стратегиями p и			q называют такие
стратегии, при	которых	f ( p ,q ) . Величину	f ( p ,q ) называют
ценой игры v.

Для практических целей важны следующие свойства оптимальных

смешанных стратегий, выражаемые следующими теоремами.

Сформулируем основную теорему теории игр.

Теорема (Нейман): Любая конечная матричная игра имеет, по крайней

мере, одно оптимальное решение, возможно, среди смешанных стратегий.
Теорема 1. Для того чтобы смешанные стратегии p p , p , , p					и
		1	2	m
q q , q , , q		были оптимальными, необходимо и	достаточно
1 2	m

выполнение неравенств

64

m

j

aij pi

1, n

(49)

i 1

n

i

aij q j

1, m

(50)

j 1

Теорема 2. Пусть p

p , p , , p

и

q q , q , , q

–

1 2

m

1 2

m

оптимальные смешанные стратегии и – цена игры.

Только те вероятности p

i

, отличны от нуля, для которых

,

1, m

i

n

aik qk . k 1

Только те вероятности qk , k 1, n , отличны от нуля, для которых

m

aik pi . i 1

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

В этой лекции рассматриваются матричные игры, не имеющие седловых точек.

2 2 – игры.

Рассмотрим игру с платежной матрицей

a	a
H 11	12
a21	a22

Пусть		игрок	A применяет набор своих	оптимальных стратегий
p p , p .		По	основной теореме теории игр	это обеспечивает ему
1	2

выигрыш при любых стратегиях игрока В, т.е. выполняются соотношения:

a11 p1 a21 p2				при стратегии В1	игрока В	(51)
a	p a		p	при стратегии В игрока В
		22
12 1			2	2
Дополняя их уравнением
p	p 1			(52)
1	2

65

получим систему линейных уравнений относительно p1 , p2 и . Решая ее найдем

p	a22 a21	,	p	a11 a12	,		a11a22 a12 a21	, (53)
1	d		2	d			d
где d a11 a22			a12 a21 .

Повторяя те же рассуждения для игрока В, получим систему линейных

уравнений

a11q1

a12 q2

a21q1

a22 q2

(54)

q

q 1

1

2

Ее решениями будут

q

a22 a12

,

q

a11 a21

,

a11a22 a12 a21

,

(55)

1

d

2

d

d

Пример. Молокозавод поставляет в магазин молочную продукцию (T1 )

и кисломолочную продукцию (T2 ). Согласно договора между ними продукция поступает в магазин два раза в день: с 10.00 до 11.00 (1-ый срок) и

с 17.00 до 18.00 (2-ой срок). Если молокозавод соблюдает сроки поставок, то магазин выплачивает премии по следующей схеме: при поставке продукции

T1 в первый срок выплачивает 5 тыс. руб., во второй срок – 3 тыс. руб.; при поставке продукции T2 в первый срок выплачивает 2 тыс. руб., во второй срок – 3 тыс. руб. Определить оптимальные стратегии поставок и получения

продукции.

Решение. Примем молокозавод за игрока А, а магазин – за игрока В.

Составим платежную матрицу игры:

Сроки	1-ый	2-ой
Продукция	срок	срок
T1	5	1
T2	2	3

или

66

	5	1
H
	2
		3

Найдем

max min aij max 1; 2 2

ij

min max aij		min 5; 3 3 ,
j	i

, седловой точки нет. Применим формулы (53) – (55) для

определения оптимальных стратегий и цены игры:

d 5 3 1 2 5													,	p	3 2							1		,			p		5 1									4			,	q			3 1			2	,
														1		5		5									2			5						5						1		5		5
q	5 2						3		,					5 3 1 2						13			2,6 ,
2		5				5								5				5
																			1						4					2						3
Оптимальные стратегии: p																							;			, q								;						, цена игры 2,6 .
																			5						5					5						5
Таким образом, молокозавод поставляет молочную продукцию с
вероятностью					1	,			а		кисломолочную												продукцию												–						с	вероятностью								4	, а
			5																																															5
магазин получает продукцию в 1-ый срок с вероятностью																																											2	, а во 2-ой срок –
																																										5
с вероятностью						3					и		выплачивает										2,6				тыс.			руб.											премии молокозаводу
						5
ежедневно.
Матричная										игра				2 2					допускает											простую														геометрическую
интерпретацию.
Нахождение цены игры																и оптимальной стратегии																												p		для игрока А
равносильно решению уравнения:
min a						p			a			2k	1 p			max min											a	p a				2k				1 p								(56)
1 k 2			1k			1								1				0 p 1 1 k 2									1k

Для нахождения правой части (56) применим графический метод.

67

Пусть игрок А выбрал смешанную стратегию p p,1 p , p 0;1 , а

игрок В – k-ую чистую стратегию, k 1,2 . Тогда средний выигрыш игрока А окажется равным

z a11 p a21 1 p при стратегии B1						(57)
z a12 p a22 1 p при стратегии B2						(58)
Очевидно, min a1k p a2k 1 p ломанная S0 S1S2 , которую называют
1 k 2
нижней огибающей прямых I и II.
Нетрудно видеть, что max S S S			2	p
0 p 1	0	1			1
Таким образом, верхняя точка нижней огибающей – S1 определяет
оптимальную стратегию игрока А:		p		p ,1 p		и цену игры .
				1	1
Проиллюстрируем описанный графичексий метод на рассмотренной
				5	1
выше игре с платежной матрицей H					.
				2
					3

На плоскости pOz построим две прямые, описываемые уравнениями: z 5 p 2 1 p и z p 3 1 p или z 3p 2 (I) и z 3 2 p (II).

Решая систему уравнений

z 3 p 2z 3 2 p,

найдем 3p 2 3 2 p ,					p	1	,	z 3	1		2	13		2,6 .
									5
					5								5
																	1		4
Таким образом,			имеем полученный выше ответ игры:													p		;		и
																	5		5
2,6 .
Теперь покажем как графическим методом найти стратегии игрока В.
max a q a				1 q min max a							q a		1 q		(59)
1 i 2	i1 1	i 2		1	0 q 1			1 i 2	i1		i 2

68

Пусть игрок В выбрал смешанную стратегию q q,1 q , q 0;1 , а

игрок А – i-ую чистую стратегию, i 1,2 . Тогда средний выигрыш игрока В окажется равным

z a11q a12 1 q при стратегии A1					(60)
z a21q a22 1 q при стратегии A2					(61)
На плоскости qOz уравнения (60) и (61) описывают прямые III и IV
Очевидно, max ai1q ai 2 1 q ломанная r0 r1r2 , которую						называют
1 i 2
верхней огибающей прямых III и IV.
Нетрудно видеть, что min r r r				q
0 q 1	0	1	2	1
Таким образом, нижняя точка верхней огибающей – r1						определяет
оптимальную стратегию игрока В: q q ,1 q и цену игры .
				1	1

Для рассмотренной выше гры с матрицей H найдем стратегии игрока В.

На плоскости qOz построим две прямые, описываемые уравнениями: z 5q 1 q и z 2q 3 1 q или z 4q 1 (III) и z 3 q (IV).

Решая систему уравнений

z 4q 1z 3 q,

найдем 4q 1 3 q , q	2	,	z 4				2	1	13			2,6 .
	5						5			5
			2		3
Таким образом, имеем q				;		и 2,6 .
			5		5

Замечания. На практике оптимальную стратегию игрока В, если оптимальная стратегия игрока А, следовательно, и цена игры известны,

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

цене игры:

a11q a12 1 q или a21q a212 1 q .

Для рассмотренного примера такими уравнениями будут

69