методичка Теория игр 2014

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

Ценой (значением) игры называется средний выигрыш игрока А . Пример 1. (игра в орлянку) Играют два игрока. Каждый игрок держит в кулаке свою монету, затем игроки одновременно разжимают пальцы. Если монеты повернуты одинаковой стороной (герб или решка), то первый игрок ( А ) выигрывает 1 руб., если же монеты повернуты разными сторонами, то тогда второй игрок ( B ) выигрывает 1 рубль.

Итак, в этой игре у обоих игроков есть по две стратегии. У игрока А :
А1 Г, Г ,	А2 Р, Р , у игрока B :		B1 Г , Р ,	B2 Р, Г . Так как
выигрыши нам известны, то платежная матрица P выигрышей игрока А
будет иметь следующий вид:
		1	1
	P
		1	.
			1

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

1.2. СИТУАЦИИ РАВНОВЕСИЯ В МАТРИЧНОЙ ИГРЕ

[1, гл.9, § 2], [2, гл.5, § 1], [3, гл.1, § 3], [4, гл.1, § 2-3], [5, гл.1, § 1], [6, гл.5, § 2], [7, гл.8, § 26].

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

Логика игры глазами игрока А : если я выберу свою стратегию Аi , то

игрок B (будучи не очень глупым) ответит на нее такой стратегий		B j ,
для которой мой выигрыш будет минимальным (т.е. игрок	B стремится
минимизировать свой возможный проигрыш и навредить	игроку	А ).

Отсюда следует, что игрок А при любой своей стратегии получит min aij .
		1 j n
Тогда среди всех таких чисел игрок		А выберет максимально возможное,
т.е.	v max min aij . Величина v	называется нижней ценой	игры
	1 i m 1 j n
(максимином) и является гарантированным выигрышем игрока А .			При
этом,	принцип выбора игроком	А стратегии, основанной	на

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

Для игрока B можно провести аналогичные рассуждения. Пусть он

выбрал	стратегию B j ,			тогда в худшем случае			он проиграет max aij .
							1 i m
Поэтому второй игрок ( B ) всегда может себе гарантировать проигрыш,
	v min max aij .
равный				Величина v называется			верхней ценой игры
			1 j n 1 i m

(минимаксом) и является гарантированным проигрышем игрока B . Сделаем вывод. В матричной игре выигрыш v игрока A всегда

больше или равен максимину v , а выигрыш игрока B (т.е. величина v )

всегда больше или равна maxmin( aij ) . Тогда
j	i
v v	(выигрыш А) v .			(1)

Лемма. В любой матричной игре максимин всегда меньше или равен минимакса, т.е.

v v .			(2)

Так, в примере 1, v 1 , а v 1 , .т.е. v v .

Рассмотрим вопрос об оптимальном поведении игроков в антагонистической игре. Естественно считать оптимальной в игре такую

ситуацию (Ai , Bj ) , от которой не выгодно отклоняться ни одному из

игроков. Такая ситуация (Ai , Bj ) называется равновесной, а принцип оптимальности, построенный на равновесной ситуации, – принципом равновесия. Ситуацию (Ai , Bj ) или, в других обозначениях, – (i , j )

принято еще называть седловой точкой. Номера i и j обозначают оптимальные стратегии игроков A и B .

Теорема. Если в матричной игре существует седловая точка (i , j ) , то говорят, что она имеет решение в чистых стратегиях. Причем Ai – оптимальная стратегия игрока A , а Bj – оптимальная стратегия игрока

B . В этом случае тогда
v v (максимин равен минимаксу).	(3)

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

Так, в примере 1, седловой точки нет. В этом случае говорят, что игра не имеет решения в чистых стратегиях. Рассмотрим другой пример.

Пример 2. Пусть имеется платежная матрица						P . Найти все седловые
точки в этой игре:
5		3	1	20	3
P	5	5	4	6	4	.
	4	2	0	0	2

Здесь v max{ 5, 4, 4} 4 ,			v min{5,5, 4, 20, 4} 4 , т.е.		v v . Таким
образом, в данной игре есть две седловые точки: ( A2 , B3 )					и ( A2 , B5 ) , а
цена игры v v v 4 .

1.3. СМЕШАННОЕ РАСШИРЕНИЕ МАТРИЧНОЙ ИГРЫ

[1, гл.9, § 3], [2, гл.5, § 1.2], [3, гл.1, § 4], [4, гл.1, § 4-5], [5, гл.1, §2],

[6, гл.5, § 3-4], [7, гл.8, § 26].
	Если в матричной игре не		существует ситуации равновесия (т.е.
v v ), то применение игроками			A и B своих чистых максиминных и

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

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

Определение. Случайная величина, значениями которой являются

стратегии игрока, называется его смешанной стратегией.

Так,

в

матричной

(m n) игре

смешанной стратегией

игрока A

является m мерная случайная величина x ( p1 , p2 ,...,

pm ) , у которой

m

pi

1,

pi 0 , i 1, m .

(4)

i 1

Аналогично,

смешанная

стратегия

игрока

B

есть

n мерная

случайная величина y (q1 , q2 ,..., qn ) , у которой

n

q j

1 ,

q j 0 , j 1, n .

(5)

j 1

В (4)-(5) величины

pi , q j

– это вероятности выбора игроками A и

B своих стратегий Аi

и B j . Если pi

1,

то это означает, что игрок A

выбрал

свою «чистую»

стратегию

Аi ,

тогда

x (0, ...,1,...,0) (i) .

i

Аналогичные рассуждения можно провести и для игрока B .

Пара

(x, y)

смешанных

стратегий

игроков

в

игре

называется

ситуацией в смешанных стратегиях.

В условиях смешанных стратегий ситуация Аi , B j (в чистых стратегиях) является случайным событием и в виду независимости

наборов вероятностей

( p1 , p2 ,..., pm ) и (q1 , q2 ,..., qn )

вероятность

его

появления равна

pi q j .

В такой ситуации игрок

A получает выигрыш,

равный aij . Тогда выигрыш v игрока

A в ситуации (x, y) в смешанных

стратегиях

для

матричной (m n) игры

можно

определить

как

математическое ожидание H A (x, y)

(среднее значение) его выигрыша при

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

стратегии x

и

y

соответственно:

m

n

H A (x, y) aij pi q j .

(6)

i 1

j 1

В векторно-матричной форме записи формула (6) примет вид:

a ...

a

q

(x, y) xAyT

p ...

11

1n

1

H

A

p

m

... ... ...

...

,

(7)

1

am1 ...

amn qn

при этом функция	H A (x, y) является непрерывной по x и y .
Определение.	Ситуация (x , y ) является ситуацией равновесия в

матричной (m n) игре, а число v H A (x , y ) – ценой игры, если при любых x и y :

H A (x, y ) H A (x , y ) H A (x , y) .

(8)

Ситуацию равновесия (x , y ) , удовлетворяющую соотношению (8),

принято называть оптимальной ситуацией в смешанных стратегиях.

Приведенное условие оптимальности (8) означает, что

v maxmin H A	(x, y) H A (x , y ) min max H A (x, y) .		(9)
x y		x y
Теорема (Дж. фон Нейман).		В любой матричной игре существует
хотя бы одна ситуация равновесия		в смешанных стратегиях.

Основные свойства оптимальных смешанных стратегий

1.	Пусть	x ( p ,... , p				)	и	y	(q ,... , q )		– оптимальные смешанные
			1		m				1	n
стратегии игроков A и B , и v H A (x , y )										– цена игры.
Оптимальная смешанная стратегия x										игрока A смешивается только
из тех	стратегий		Аi	i 1, m ,				т.е.	отличными от нуля будут только те

вероятности pi , для которых выполнены равенства:

n
v aij q j	H A (i, y ) .			(10)
j 1
Аналогично для игрока B :		оптимальная смешанная стратегия					y
игрока A смешивается только		из тех стратегий	B j	j 1, n ,			т.е.
отличными от нуля будут только те вероятности			q j ,	для которых
выполнены равенства:
m
v aij pi		H A (x , j) .		(11)

i 1

Вформулах (10)-(11) знак i в аргументе функции H A (x, y) означает,

что игрок A выбрал свою чистую стратегию Аi , и, соответственно, j означает, что игрок B выбрал свою чистую стратегию B j .

Кроме того, выполняются соотношения:

m

m

n

v min

aij

pi max min

aij pi

min max

aij q j

max

1 j n

i 1

x

1 j n

i 1

y 1 i m

j 1

1 i m

Соотношение (12) можно переписать и в такой форме:

v min H

A

(x , j) max min H

A

(x, j)

1 j n

x 1 j n

min max H

A

(i, y) max H

A

(i, y* ).

y

1 i m

1 i m

n

aij q j . (12)

j 1

(12а)

2. Для того, чтобы ситуация (x , y ) была ситуацией равновесия в

матричной (m n) игре, и число v H A (x , y ) – ценой игры, необходимо и достаточно, чтобы выполнялись следующие неравенства:

H A (i, y ) H A (x , y ) H A (x ,
	j) , для любых i 1, m , j 1, n .						(13)
3. Для того, чтобы ситуация	(x , y )	была ситуацией равновесия в
матричной (m n) игре, необходимо		и достаточно выполнения
следующего равенства (см. равенство (12а)):
max H A (i, y ) min H A (x , j) .							(14)
i	j

4.В матричной игре множества оптимальных смешанных стратегий игроков A и B являются выпуклыми многогранниками [4, гл.1, § 5].

5.Пусть платежная матрица P матричной игры является

кососимметрической, т.е.	aij a ji для	i j . Тогда, если	x –
оптимальная смешанная стратегия игрока		A , то такую же оптимальную
стратегию имеет и игрок B :	y x , при этом цена игры v 0 .
На этих свойствах основаны методы решения матричных игр.

1.4. РЕШЕНИЕ МАТРИЧНОЙ ИГРЫ 2 2

[1, гл.9, § 3-4], [2, гл.5, § 5.1], [3, гл.1, § 5], [6, гл.5, § 3-4].

Рассмотрим матричную игру размера 2 2 , которая является простейшим случаем конечной игры. Пусть платежная матрица P игры имеет вид:

a	a
P 11	12
	a22	.
a21

Пусть игра не имеет решения в чистых стратегиях, т.е. v v . Это означает, что решение следует искать в смешанных стратегиях.

Рассмотрим аналитический способ решения.

Пусть	x p1 , p2 ( p,1 p) ,		0 p 1 –	смешанная стратегия
игрока A (если		p 0 , то это означает, что игрок		A выбрал свою чистую
стратегию	A2 ;	если p 1, то это означает, что игрок A выбрал свою

чистую стратегию A1 , что в данном случае недопустимо). Таким образом,

обе стратегии игрока A являются активными (определение приведено в разделе 1.5.2). Тогда из свойства 1 и равенства (11) (см. также (12в) в 1.5.2) следует, что какую бы чистую стратегию не выбрал игрок B , если

x ( p,1 p)

– оптимальная стратегия игрока

A , то цена игры v

будет

определяться из следующих равенств:

v a11 p a21

(1 p) H A (x,1),

(15)

(1 p) H A (x, 2).

v a12 p a22

Отсюда получим следующее решение:

p p

a22 a21

p

a11 a12

v

a22 a11

a12 a21

1

a11 a22 a12

,

2

a11

a22 a12 a21

,

a11 a22

a12

a21

.

a21

Аналогичные

рассуждения

можно

провести

и

для

игрока

B :

если

y q , q (q,1 q)

,

0 q 1

–

оптимальная

смешанная

стратегия

1

2

игрока B , то из свойства 1 и равенства (10) следует, что

v a

q a

(1 q) H

A

(1, y ),

v a

11

12

(16)

21

q a

22

(1 q) H

A

(2, y ).

Отсюда имеем:

q

q

a22 a12

q

a11 a21

,

.

(16а)

1

a11 a22

2

a12 a21

a11 a22 a12 a21

Так, решение игры из примера 1 будет иметь следующий вид:

v 1 p1	( 1) p2	,		p2	1 p1 (1 p1 ) p1 (1 p1 )
	p1 1 p2 ,		p1
v ( 1)

2 p1 1 2 p1 1 p1 12 p2 12 .

A будет x

1

1

Таким образом, оптимальной стратегией игрока

;

, а

2

2

цена игры v 0 .

Аналогично для игрока B :

v 1 q1 ( 1) q2 ,

q1 q2 1 q1

1 2 и q2 1 2 , v 0 .

v ( 1) q1 1 q2 ,

Значит, игрокам A и B при многократном проведении игры следует

применять обе свои стратегии в пропорции 1:1.

Приведем геометрическое решение игры 2 2 .

Отложим по оси абсцисс Ox

единичный отрезок A1 A2 : точка

A1

( x 0) изображает

стратегию

A1 ,

а все промежуточные точки этого

отрезка – смешанные стратегии x ( p1 , p2 )

игрока A , причем расстояние

от x

до правого конца

A2 – это вероятность

p1

выбора стратегии

A1 , а

расстояние до левого конца A1

– вероятность p2 выбора стратегии A2 . На

перпендикулярных осях I-I и II-II откладываются выигрыши при

стратегиях

A1 и A2 .

Если игрок B выберет стратегию

B1 ,

то она даст

игроку

A

выигрыши a11 и a21

на осях I-I и II-II, соответствующие стратегиям

A1 и

A2 . Обозначим эти точки на осях I-I и II-II буквой B1 . Средний выигрыш

v1 , соответствующий смешанной

стратегии

x ( p1 , p2 ) , определяется

тогда

по

формуле:

v1 a11 p1

a21 p2 , и

равен

ординате

точки

M1 ,

принадлежащей отрезку B1B1 и имеющей абсциссу x (см. рис.1а).

y

I

II

y

I

B2

II

M1

B1

M2

B1

a12

a21

B2

v1

v2

a11

a22

0

x

1

x

x

1

A1

p2

A2

0

A

A2

x

I

II

1 p2

p1

II

I

Рис.1а

Рис.1б

Аналогично, строим отрезок B2 B2 , соответствующий применению игроком B его стратегии B2 . При этом средний выигрыш v2 определяется по формуле: v2 a12 p1 a22 p2 , и равен ординате точки M 2 ,

принадлежащей отрезку B2 B2		(см. рис.1б).
Объединим рис.1а и рис.1б и покажем графическое решение на рис.2.
y	I	II

B1

	B2		M
a12	B1			B2	a21
			v
	a11
				a22
	A1		x*
				1
	0	p	p	A2	x
	I
		2	1	II

Рис.2

В соответствии с принципом максимина оптимальная стратегия x такова, что минимальный выигрыш игрока A (при наихудшем поведении

игрока	B )	обращается в максимум. Ординаты точек,					лежащих на
выделенной		ломаной	B1MB2 , на рис.2 показывают минимальный
выигрыш игрока A при использовании им любой смешанной стратегии
(участок	B1M – против стратегии			B1 , участок	MB2	– против стратегии
B2 ). Оптимальную			стратегию	определяет	точка	M ,	в которой

минимальный выигрыш достигает максимума, а ее ордината равна цене игры v .

Пример 3. Применим данный геометрический метод к нахождению

оптимальной стратегии игрока A	в игре с платежной матрицей			2		5
				P		.
					3
						1
Найдем сначала максимин	v и минимакс v : v max{ 2,1} 2 ,

v min{ 3, 5} 3. Итак, решение нужно искать в смешанных стратегиях.

	y	I
					II
	B2
			M		B1
5	B1
	2		v		B2	3
					1
		A1	x*	1
	0	I	p2	p1	A2	x
					II

Рис.3

На рис.3 приведено геометрическое решение примера 3. Используя рис.3, вычислим точку пересечения прямых B1B1 и B2 B2 . Уравнение прямой B1B1 , проходящей через точки (0; 2) и (1; 3):

	x 0			y 2		y		x 2 .
	1 0			3 2
Уравнение прямой B2 B2 , проходящей через точки (0; 5) и (1; 1):
	x 0			y 5		y		3x 5 .
	1 0			1 4
Тогда			координаты					точки				пересечения					M прямых B1B1 и						B2 B2
определяются из системы:
y x 2,						x 2 3x 5 x								3			y	13
																				.
y 3x 5														5				5
Таким образом,							p	x	3		,	p 1 p			2		, цена игры				v y	13	.
							2	5				1	2	5							5
Аналогичным способом, приведенным выше, можно определить
оптимальную стратегию игрока B ,													если поменять местами игроков										A и

B , и вместо максимума нижней границы B1MB2 (рис.2) в соответствии с принципом минимакса рассмотреть минимум верхней границы A1 NA2 (рис.4). Абсцисса точки N на ломаной A1 NA2 определяет значение q2 в

оптимальной стратегии y (q1 , q2 ) игрока B , а ордината этой точки – цену игры v .

y	I	для игрока B

A2	N
A1

a21	= 3		v
		a11 = 2
			y*

0	q1
I q2
	Рис.4

II

A1

a12 = 5

A2

a22 = 1

B2 x

II

Итак, на рис.4 показан графический способ отыскания оптимальной стратегии игрока B в примере 3. Найдем координаты точки N пересечения прямых A1 A1 и A2 A2 . Для этого составим уравнения этих прямых.

Уравнение прямой A1 A1 , проходящей через точки (0; 2) и (1; 5):

	x 0		y 2
				y 3x 2 .
	1 0		5 2
Уравнение прямой A2 A2 , проходящей через точки (0; 3) и (1; 1):
	x 0		y 3
				y 2x 3.
	1 0		1 3
Значит, координаты точки пересечения																														N					прямых							A1 A1			и				A2 A2
определяются из системы:
y 3x 2,							2 2x 3 x																		1						y						13
				3x																																				.
y 2x 3																									5												5
Таким образом,					q x					1	,		q 1 p									4					, цена игры													v y				13				.
					2		5								1			2				5																						5
Сделаем проверку полученного решения. Используем формулу (6):
v H A (x , y ) 2						2		4	5			2				1	3	3		4	1									3				1		16 10 36 3														13	.
												5						5		5										5				5															5
					5		5								5																									25
Таким			образом,				решение										найдено										Оптимальные																смешанные
																		x						2				;			3		; y							4	;	1
стратегии игроков A и B следующие:																																											.
																																								5
																						5									5											5

Отметим, что графический способ решения годиться и в том случае, если игра имеет решение в чистых стратегиях (подробнее см. [1 гл.9, § 4]).

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

Лемма (о масштабе, аффинное правило). Пусть x и y – оптимальные стратегии двух игроков, а v – цена игры в матричной m n - игре с платежной матрицей P , причем

		P P ,	(17)
где	и	– некоторые числа, 0. Тогда в матричной	игре с
платежной матрицей P оптимальные стратегии будут такими же, как и в
матричной игре с платежной матрицей P , а цена игры
		v v .	(18)

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

1.5. ГРАФИЧЕСКИЕ МЕТОДЫ РЕШЕНИЯ МАТРИЧНЫХ ИГР