лекции(II курс)

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

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

Смешанной стратегией SA называется применение чистых стратегий A1, A2, . . . , Am ñ

	вероятностями		причем	m
		p1, p2, . . . , pm,		∑i=1 pi = 1. Смешанные стратегии записываются в
	виде матрицы
			A1 A2 . . . Ai . . . Am			.)
		SA = ( p1		p2	. . . pi . . . pm
	Аналогично смешанные стратегии игрока B обозначаются
			B1 B2 . . . Bj . . . Bm			.)
		SB = ( q1		q2 . . . qi . . . qm

Чистые стратегии можно считать частным случаем смешанных.

Справедлива следующая теорема:

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

Если чистая стратегия входит в оптимальную смешанную стратегию с нулевой веро-

ятностью, то она называется активной.

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

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

Рассмотрим игру размера 2 × 2, которая является простейшим случаем конечной иг-

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

соответствии с основной теоремой теории игр оптимальное решение существует и определяется парой смешанных стратегий SA(p1, p2) è SB(q1, q2). Для того, чтобы их найти,

воспользуемся теоремой об активных стратегиях. Если игрок A придерживается своей оптимальной стратегии SA, то его средний выигрыш будет равен цене игры ν, какой бы активной стратегии не пользовался игрок B. Äëÿ èãðû 2 × 2 любая чистая стратегия

противника является активной, если отсутствует седловая точка. Выигрыш игрока A (проигрыш игрока B) случайная величина, математическое ожидание (среднее значе- ние) которой является ценой игры. Поэтому средний выигрыш игрока A (оптимальная стратегия) будет равен ν и для 1-й, и для 2-й стратегии противника.

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

()

	P =	a11	a12
		a21	a22

Средний выигрыш игрока A, если он использует оптимальную смешанную стратегию

()

	S	=	A1	A2	,
			p1	p2
	A

а игрок B чистую стратегию B1 (это соответствует первому столбцу платежной матрицы P ), равен цене игры ν:

a11p1 + a21p2 = ν.

121

Тот же средний выигрыш получает игрок A, если 2-й игрок применяет стратегию B2, ò.å. a12p1 + a22p2 = ν. Учитывая, что p1 + p2 = 1, получаем систему уравнений для

определения оптимальной стратегии SA		è öåíû èãðû ν.
	a11p1 + a21p2 = ν;
	a12p1 + a22p2 = ν;
	p1 + p2 = 1.
Решая эту систему, получим

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

Применяя теорему об активных стратегиях при отыскании SB оптимальной страте- гии игрока B, получаем, что при любой чистой стратегии игрока A (A1 èëè A2) средний проигрыш игрока B равен цене игры ν, ò.å.

a11q1 + a12q2 = ν;

a21q + a22q = ν;

q1 +1q2 = 1.2

Из системы находим оптимальную стратегию SB.

7.5. Геометрическая интерпретация игры 2 × 2.

Дадим геометрическую интерпретацию игры 2 × 2 с матрицей

()

	P =	a11	a12
		a21	a22

В системе координат XOY на оси абсцисс отложим от начала координат единичный отрезок A1A2; точка A1(x = 0) изображает стратегию A1, а все промежуточные точки этого отрезка смешанные стратегии SA первого игрока, причем расстояние от SA äî правого конца отрезка это вероятность p1 стратегии A1, расстояние до левого конца вероятность p2 стратегии A2.

Y

I

II

B2

N

B1

A12 B1

A21

A11

B2

S*

A22

X

A

A1

A2

P2

P1

На перпендикулярных осях I и II откладываем выигрыши при стратегиях A1 è A2 ñî- ответственно. Если 2-й игрок примет стратегию B1, то она дает выигрыш a11 è a21 íà îñÿõ I è II, соответствующие стратегиям A1 è A2. Обозначим эти точки на осях I и II буквой B1. Аналогично строим отрезок B2B2, соответствующий приненению вторым игроком стратегии B2. В соответствии с принципом минимакса оптимальная стратегия SA такова, что минимальный выигрыш игрока A (при наихудшем поведении игрока B) обращается в

122

максимум. Оптимальную стратегию определяет точка N (максимум на нижней границе). Ее ордината равна цене игры ν.

Замечание 1. Геометрически можно определять оптимальную стратегию как игрока A, так и игрока B; в обоих случаях используется принцип минимакса, но во втором случае

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

а минимум.

Замечание 2. Если платежная матрица содержит отрицательные числа, то для графического решения задачи лучше перейти к новой матрице с неотрицательными элементами, для этого к исходной матрице достаточно добавить соответствующее положительное число. Решение игры при этом не изменится, а цена игры увеличится на это число.

Если игра имеет седловую точку, то графическое решение дают варианты, изображенные на рисунках 1 и 2:

Y
I	!и#.1	II
		B1
		B2
		N
B2
B1		= =
A12		= A22		A21
A11		*
		S A	A2	X
A1
	P2=1

Наибольшей ординатой на ломанной B1NB2 обладает точка B2, поэтому оптимальной является чистая стратегия A2 для игрока A (äëÿ B B2), т.е. оптимальное решение SA = (0, 1), SB = (0, 1). Игра имеет седловую точку a22 = ν.

Y

!и#.2

I

II

B2

B1

A22

B2

= =

B1

= A21

A12

A11

X

A1

A2

P2=1

Чистая стратегия B2 не выгодна для игрока B, поскольку при любой стратегии игрока A она дает последнему больший выигрыш, чем чистая стратегия B1. На основании принципа минимакса выделим прямую B1B1 и на ней точку B1 с наибольшей ординатой на оси I. Чистая стратегия A2 является оптимальной для игрока A, а чистая стратегия

123

B1 для игрока B. Оптимальное решение: SA = (0, 1); SB = (1, 0), ν = a21 = α = β, ò.å.
имеется седловая точка.
Графический метод можно применять при решении игры 2 × n è m × 2. Не доказывая,
отметим, что любая конечная игра		m × n имеет решение, в котором число активных
стратегий каждого игрока не превосходит min(m, n). Следовательно, у игры 2 × m èëè
n×2 всегда имеется решение, содержащее не более двух активных стратегий у каждого из
игроков. Если найти эти активные стратегии игроков, то игра 2×m èëè n×2 превращается
â èãðó 2 × 2. Решение таких игр мы уже рассматривали.
Пример. Графическим методом найти решение игры, заданной матрицей.
			7	−1
			5	4
			1	5		.
			3	−	2
			2
				1
Решение. Перейдем к эквивалентной матрице, путем добавления к каждому элементу
данной 3. Получим:			10	2
			8	7
			4	8		.
			6	1
			5	4
Т.к. матрица порядка 5 × 2, по будем искать оптимальные смешанные стратегии для
игрока B. Проведем 5 прямых, соответствующих стратегиям B1 è B2.
Y	I					II
10	(A1)
(A2) 8	M				N	8 (A3)
(A3)6						7 (A2)
(A4)5
(A5)4						4 (A5)
						2 (A1)
			S	B		1 (A4)	X
	B1					B2
	Q2					Q1
На ломанной A1MNA3 найдем нижнюю границу, это точка N, ее ордината и есть
искомая цена игры. Точка N получена пересечением прямых A2A2 è A3A3. Таким образом,
мы свели игру размера 5 × 2 ê èãðå 2 × 2.
Составив уравнения этих прямых, найдем координаты точек. A2(0, 8); A2(1, 7).

x − 0

=

y

− 8

,

→

y = 8

−

x

−

уравнение прямой A

A

.

1

−

0

7

−

8

2

2

Аналогично, уравнение прямой A3A3 : y = 4x + 4.

124

Решим систему 2-х уравнений:

{

y= 8 − x;

y= 4x + 4.

Откуда получим координаты точки N(4/5; 36/5). Тогда оптимальная смешанная стратегия игрока B

SB = (	B1 B2	).
	1/5 4/5

à öåíà èãðû ν = 36/5. Также графическим методом найдем оптимальную смешанную стратегию для игрока A. Построим прямые B1B1 è B2B2.

Y	I	II

8	(B1)	M	8	(B2)
7	(B2)
			4 (B1)

					SA						X
		A2							A3
				P2		P1

Составив уравнения прямых B1B1 è B2B2 найдем координаты точки пересечения M:

B1B1 : y = 8 − 4x; B2B2 : y = x + 7.

{

y= 8 − 4x;

y= x + 7.

Точка M(1/5; 36/5). Тогда оптимальная смешанная стратегия для игрока A примет вид:

SA = (	A	A2 A3 A	A	).
	01	4/5 1/5 04	05

Замечание. Стратегии игрока A A1, A4 è A5 имеют нулевые вероятности, т.к не участвовали в рассмотрении. Цена игры ν одинакова как для игрока A, так и для игрока B.

Ответ:

SB = (	B1 B2	), SA = (	A1 A2 A3 A4 A5	), ν =	36
	1/5 4/5		0 4/5 1/5 0 0			.
					5

7.6. Приведение матричной игры к задаче линейного программирования.

Èãðà m × n в общем случае не имеет наглядной геометрической интерпретации. Ее решение достаточно трудоемко при больших m è n, однако принципиальных трудностей

не имеет, поскольку может быть сведено к решению задачи ЛП.

Пусть игра m ×n задана платежной матрицей P = (aij), i = 1, . . . , m, j = 1, . . . , n. Игрок A обладает стратегиями A1, A2, . . . , Am, а игрок B стратегиями B1, B2, . . . , Bn. Необходимо определить оптимальные стратегии SA è SB.

125

Оптимальная стратегия SA удовлетворяет следующему требованию. Она обеспечивает игроку A средний выигрыш, не меньший, чем цена игры, при любой стратегии игрока B и выигрыш, равный цене игры, при оптимальной стратегии игрока B. Если игрок A применяет смешанную стратегию SA против любой чистой стратегии Bj игрока B, то он получает средний выигрыш или математическое ожидание выигрыша aj = a1jp1 + a2jp2 + . . .+ amjpm, т.е элементы j−го столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий A1, A2, . . . , Am b результаты складываются. Для оптимальной стратегии SA все средние выигрыши не меньше цены игры ν, поэтому получаем систему неравенств:

a p

11 1a12p1

a1np1

+a21

+a22

+a2n

p2 + . . .	+ am1pm ≥ ν;
p2 + . . .	+ am2pm ≥ ν;	(1)
. . . . . . . . .

p2 + . . . + amnpm ≥ ν.

Каждое из неравенств можно разделить на число ν > 0. Введем новые переменные:

x1 = p1/ν, x2 = p2/ν, . . . xm = pm/ν.

Тогда система (1) примет вид:

		a11x1 + a21x2 + . . . + am1xm		≥	1;	(2)
	a12x1 + a22x2 + . . . + am2xm				1;
			. . . . . . . . .	≥
Цель игрока A	максимизировать		свой гарантированный выигрыш, т.е. цену игры			ν.
	a1nx1 + a2nx2 + . . . + amnxm ≥ 1.
Разделив на ν ̸= 0 равенство p1 + p2 + . . . + pm = 1,					получаем, что переменные xi

удовлетворяют условию:

x1 + x2 + . . . + xm = 1/ν.

Максимизация цены игры ν эквивалентна минимизации величины 1/ν, поэтому задача

может быть сформулирована следующим образом:

определить значения переменных xi ≥ 0, так чтобы они удовлетворяли линейным ограничениям (2) и при этом линейная функция

F = x1 + x2 + . . . + xm	(3)
обращалась в минимум.
Эта задача ЛП. Решая задачу (2) (3), получаем оптимальное решение	p1, p2, . . . , pm
и оптимальную стратегию SA.

Для определения оптимальной стратегии SB = (q1, q2, . . . , qn), следует учесть, что игрок

	B стремится минимизировать гарантированный выигрыш, т.е. найти max					1	. Переменные
						ν
	q1, q2, . . . , qn удовлетворяют неравенствам
			a11q1 + a21q2 + . . . + a1nqn	≤	ν;		(4)
			a21q1 + a22q2 + . . . + a2nqn		ν;
			. . . . . . . . .	≤
	которые следуют из того,	что средний проигрыш игрока			B не превосходит цены игры,
		am1q1 + am2q2 + . . . + amnqn ≤ ν.

какую бы чистую стратегию не применял игрок A.

126

Если обозначить

	yj	= qj/ν, j = 1, 2, . . . , n,
То получим систему неравенств:
	a11y1 + a21y2 + . . . + a1nyn		≤	1;	(5)
	a21y1 + a22y2 + . . . + a2nyn			1;
		. . . . . . . . .	≤
		+ am2y2 + . . . + amnyn ≤ 1.
am1y1

Переменные yj удовлетворяют условию y1 + y2 + . . . + yn = 1/ν. Игра свелась к следующей задаче.

Определить значения переменных yj ≥ 0, j = 1, 2, . . . , n, которые удовлетворяют системе неравенств (5) и максимизируют линейную функцию

Z = y1 + y2 + . . . + yn.

(6)

Решение задачи ЛП (5) (6) определяет оптимальную стратегию SB, ïðè ýòîì öåíà èãðû

ν = 1/ max Z = 1/ min F.

(7)

Составив расширенные матрицы для задач (2) (3) и (5) (6), заметим, что одна матрица получается из другой транспонированием:

				≥
	a11 a21		. . . am1		1
a12 a22			. . . am2		1
		a. 2.n.	.. .. ..	a.mn. .	.1. .
a. 1.n.
	1	1	. . .	1	min F

				≤
		a11	a12	. . . a1n		1
a21			a22	. . . a2n		1
				.. .. ..	a.mn. .	.1. .
a.m. .1 a.m. .2
		1	1	. . .	1	max Z

Таким образом, задачи ЛП (2) (3) и (5) (6) являются взаимо - двойственными. Очевидно, при определении оптимальных стратегий в конкретных задачах следует выбрать ту из взаимно-двойственных задач, решение которой менее трудоемко, а решение другой задачи найти с помощью теорем двойственности.

Пример. Торговая фирма разработала несколько вариантов плана продажи товаров на предстоящей ярмарке с учетом меняющейся конъюнктуры рынка и спроса покупателей. Получающиеся от их возможных сочетаний показатели дохода представлены матрицей

	8	4	2
	1	2	8
P =	2	8	4	.

Определить оптимальный план продажи.

Решение. Задача сводится к игровой модели, в которой игра торговой фирмы A против покупательского спроса B задается матрицей P.

Составим вспомогательную таблицу, для определения α è β.

	B1	B2	B3	αi
A1	8	4	2	2
A2	2	8	4	2
A3	1	2	8	1
				α = 2
βj	8	8	8	β = 8

127

Ò.ê. α ≠ β, то седловая точка отсутствует и оптимальное решение следует искать в смешанных стратегиях игроков:

A1 A2 A3	)	è SB = (	B1 B2 B3	).
SA = ( p1 p2 p3			q1 q2 q3

Обозначив xi = pi/ν, i = 1, 2, 3, è yj = qj/ν, j = 1, 2, 3, составим две взаимно-

двойственные задачи ЛП.

Задача 1.

Задача 2.

8x1 + 2x2 + x3

1;

8y1 + 4y2 + 2y3

1;

4x1 + 8x2 + 2x3≥

1;

2y1 + 8y2 + 4y3

≤ 1;

2x1 + 4x2 + 8x3

≥

1.

y1 + 2y2

+ 8y3

≤1.

≥

j ≥ 0

≤

x

, i

= 1

,

2

, .

y

, j

= 1

, , .

i

≥ 0

3

2 3

F = x1 + x2 + x3 → min .

Z = y1 + y2 + y3 → max .

Решаем симплексным методом одну из задач, например, вторую, т.к для нее 1БР будет допустимым. Введем добавочные переменные и перейдем к уравнениям:

8y1 + 4y2 + 2y3 + y4 = 1;

2y1 + 8y2 + 4y3 + y5 = 1; y1 + 2y2 + 8y3 + y6 = 1.

Выразим добавочные переменные через исходные:

y4 = 1 − 8y1 − 4y2 − 2y3;

| y5 = 1 − 2y1 − 8y2 − 4y3;| y6 = 1 − y1 − 2y2 − 8y3.

1БР (0; 0; 0; 1; 1; 1) допустимо. Но не оптимально, т.к. все коэффициенты в функции Z при переменных y1, y2, y3 положительны, что не удовлетворяет критерию оптимальности.

Пусть y2 → базис, (данном случае, все переменные равноценны для перевода в базис) y2 = min{1/4, 1/8, 1/2} = 1/8, следовательно y5 → свободные. Разрешенное уравнение,

второе.	y2 = 1/8 − 1/4y1 − 1/2y3 − 1/8y5;
		| y4 = 1/2 − 7y1 + 1/2y5;|
		y6 = 3/4 − 1/2y1 − 7y3 + 1/4y5.

2ÁÐ (0; 1/8; 0; 1/2; 0; 3/4) допустимо. Выразим целевую функцию, через новые свободные переменные y1, y3, y5.

Z = 1/8 + 3/4y1 + 1/2y3 − 1/8y5 − критерий оптимальности не выполнен.

y1 → базис, y1 = min{1/2, 1/14, 3/2} = 1/14, следовательно y4 → свободные. Третье

уравнение разрешенное.

y1 = 1/14 + 1/4y5 − 1/7y4;

y2 = 3/28 − 1/2y3 − 1/7y5 + 1/28y4; | y6 = 5/7 − 7y3 + 3/14y5 + 1/28y4.|

3ÁÐ (1/14; 3/28; 0; 0; 0; 5/7) допустимое.

Z = 5/28 + 1/2y3 − 1/14y5 − 3/28y4, но не оптимальное.

128

Переведем y3 в базис, y3 = min{∞; 3/14; 5/49} = 5/49.

y1 = 1/14 + 1/14y5 − 1/7y4;

y2 = 11/196 − 31/196y5 − 3/984y4 + 1/14y4; y3 = 5/49 + 3/28y5 + 1/196y4 − 1/7y6.

Z =	315		−	11	y5	−	41	y4	−	1	y6	,	Zmax =	315	.
	1372			196			392			14				1372

Таким образом, 4БР (1/14; 11/196; 5/49; 0; 0; 0) является допустимым и оптимальным. По формуле (7) найдем цену игры:

ν =	1	=	1372		≈ 4, 4.
	Zmax		315

Вероятности использования стратегий B1, B2, B3 найдем по формулам yj = qj/ν, j = 1, 2, 3, получим

	1	·	1372		98			11	·	1372		77			5	·	1372		140
q1 =				=		,	q2 =				=		,	q3 =				=		.
	14		315		315			196		315		315			49		315		315

Чтобы найти вероятности p1, p2, p3 использования стратегий A1, A2, A3, воспользуемся второй теоремой двойственности:

										x1				x2				x3						x4 x5 x6
										↕				↕						↕				↕		↕					↕
										y4				y5				y6						y1		y2			y3
										41				11						1
										392		196						14						0		0			0
По коэффициентам целевой функции Z при соответствующих переменных, получаем
допустимое и оптимальное решение Задачи 1 (																										392;			196				; 14; 0; 0; 0). Тогда
																										41			11				1
11		1372			77											41					1372					140											1		1372	98
p1 =		·		=					,		p2 =									·					=						,		p3 =					·		=		.
	196		315		315											392							315				315										14		315		315
Ответ:					∑i=1						i			∑j=1							j
Заметим, что равенство					3					p		=				3				q			= 1 выполнено.
		SA =			A1 A2 A3																			SB		=			B1 B2 B3
					77				140			98								è									98				77				140 .
		(														)										(													)
					315				315			315																	315				315				315

Следовательно, предприятие должно выпустить 24 процента продукции A1, 44 процента продукции A2 и 32 процента продукции A3. При этом оптимальный спрос в 32 процента находится в состоянии B1, 24 процента в состоянии B2 и 44 процента в состоянии B3.

При решении произвольной конечной игры размера m × n рекомендуется придержи-

ваться следующей схемы:

1) Исключить из платежной матрицы заведомо невыгодные стратегии по сравнению с другими стратегияим. Такими стратегиями для игрока A (игрока B) являются те, кото-

рым соответствуют строки (столбцы) с элементами, заведомо меньшими (большими) по сравнению с элементами других строк (столбцов).

2) Определить α è β и проверить имеет ли игра седловую точку. Если есть седло-

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

3) Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. Для игр размера m × n рекомендуется симплексный метод, для игр размера 2 × 2,

2 × n, m × 2 возможно геометрическое решение.

129