Дуплякин В.М. Теория игр

Т Е О Р И Я И Г Р

В.М.Дуплякин

На следующем этапе поиска оптимального решения найдём функцию минимумов всех скалярных произведений, координатами которой являются

координаты вектора смешанных стратегий

ψ(x) = min [x]× éa j ù.
j=1,...,n	ë û

Далее найдём максимум этой функции в m −мерном пространстве, который и

будет равен цене данной игры

ν = max ψ(x).

x

Скаляризация, т.е. в данном случае использование скалярных произведений на промежуточной стадии решения, позволяет значительно снизить размерность решаемой задачи, т.к. внутренний поиск оптимума ведётся по чистым стратегиям (их всего n ), а заключительный этап решения выполняется только по координатам вектора (x), что намного эффективнее

решения матричных уравнений с двумя произвольными векторами (x) и (y)

ν= max min [x]×[A]×[y] .

xy

Примечание.

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

é y1 ù

[ ] ê y ú

y = êê ...2 úú . êë ym úû

Обратимся к определению цены игры на основании следствия из утверждения № 3, которое с учётом блочного структурирования платёжной

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

ν = miny max [ai ]×[y].

i=1,...,m

Рассмотрим выражение max min	[ai ]×[y].
y i=1,...,m

Для произвольной смешанной стратегии игрока Р2 найдём скалярные

произведения

[a1 ]×[y], [a2 ]×[y], ... , [ai ]×[y], ... , [am ]×[y] .

На следующем этапе поиска оптимального решения найдём функцию максимумов полученных скалярных произведений

ξ( y) = max [ai ]×[y].

i=1,...,m

50

Т Е О Р И Я И Г Р В.М.Дуплякин

Далее найдём минимум этой функции в n −мерном пространстве,

который и будет равен цене данной игры

ν = min ξ( y).

y

Как видно, и при таком подходе выполненная промежуточная

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

7. ПРИМЕРЫ РЕШЕНИЯ МАТРИЧНЫХ ИГР

7.1. Решение игры 7х6 в чистых стратегиях

Рассматривая пример для приведенной ниже платёжной матрицы, начнём с определения нижней и верхней цены игры.

	Платёжная													Стратегии игрока Р2
	матрица																											^a = max min {a							}
											a1			a2			a3			a4			a5			a6
		[A]																																ij
										0			5			10			15			20			25					i=1,...,7 j=1,..,6
				a				0			43,7			25,0			13,7			10,0			13,7			25,0		→		10,0			игры
					1						5			0			5			0			5			0				0
	1Р			a				5			61,2			42,5			31,2			27,5			31,2			42,5		→		27,5			цена
					2						5			0			5			0			5			0				0
	игрока							1			73,7			55,0			43,7			40,0			43,7			55,0		→		40,0			нижняя-
				a	4			0			5			0			5			0			5			0				0
				a	3
	Стратегии							1			81,2			62,5			51,2			47,5			51,2			62,5		→		47,5
								5			5			0			5			0			5			0				0
							2			81,2			62,5			51,2			47,5			51,2			62,5			→	47,5				50, 0
				a				2			83,7			65,0			53,7			50,0			53,7			65,0		→		50,0		→
					5			0			5			0			5			0			5			0				0
				a6				5			5			0			5			0			5			0				0
				a7				3			73,7			55,0			43,7			40,0			43,7			55,0		→		40,0
								0			5			0			5			0			5			0				0
											↓			↓			↓			↓			↓			↓
										83,7			65,0			53,7			50,0			53,7			65,0
										5			0			5			0			5			0
																				↓
		a = min max{aij}
																			50,0				- верхняя цена игры
							j=1,...,6 i=1,..,7												0

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

51

Т Е О Р И Я И Г Р

В.М.Дуплякин

Решение данной игры, а именно выбор оптимальных стратегий выглядит

следующим образом

aopt (P1) = a5 = 20; aopt (P2) = a4 =15.

Следовательно, в данной игре игрок Р1, выбрав 5-ю стратегию, обеспечивает себе гарантированный выигрыш не ниже чем 50 усл. единиц, а игрок Р2, придерживаясь 4-й стратегии, имеет минимальный проигрыш непревосходящий 50 усл. единиц.

Выбор других стратегий участникам данной игры невыгоден.

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

Рассмотрим пример матричной игры размерностью 2х2 с приведенной ниже платёжной матрицей.

Следует отметить, что игры размерностью 2х2 имеют скорее учебный, чем практический интерес, однако они допускают наглядную геометрическую иллюстрацию полуаналитического решения, в то время как игры более высокой

размерности не имеют графического отображения в декартовой системе координат и решаются численно.

Тем не менее, основные особенности решения матричных игр в

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

Платёжная

Стратегии

матрица

игрока Р2

max

[A]

a

1

a

2

min

min

Стратегии игрока Р1

a1

5

3

→

3

3

a2

2

6

→

2

↓

↓

max

5

6

min max

5

Анализ приведенной платёжной матрицы приводит к получению

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

{aij}

ˆ

=

max

min

=

3

- нижняя цена игры;

a

(

i=1,2

j=1,2

= min

max

{aij}= 5 - верхняя цена игры.

a

j=1,2

i=1,2

52

Т Е О Р И Я И Г Р	В.М.Дуплякин
Поскольку видно, что	aˆ <a , то из этого следует, что данная игра не

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

Воспользуемся утверждением №6 (скаляризация решения) из

предыдущего раздела и применительно к нашему примеру запишем

Р1:	ν = max min [x]× éa j ù			;	(7.1)
	x	j=1,2	ë û
Р2:	ν = min max [ai ]×[ y].				(7.2)
	y	i=1,2

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

	прямой линии
	é 1 ù				é5ù
			= [x1, x2	]´ ê ú		= 5× x1	+ 2 × x2 ;	(7.3)
	l1(x) = [x]´ ëa	û
					ë2û
	é	2 ù			é3ù
			= [x1, x2		]´ ê ú	= 3× x1	+ 6× x2 .	(7.4)
	l2 (x) = [x]´ ëa	û
					ë6û

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

координату через первую
x2 = 1 - x1 .	(7.5)
Подставив полученное выражение для координаты x 2	в соотношения
(7.3, 7.4), получим
l1(x1 ) = 5 × x1 + 2 × (1 - x1 ) = 3× x1 + 2 ;	(7.6)
l2 (x1 ) = 3× x1 + 6 ×(1 - x1 ) = -3× x1 + 6 .	(7.7)

Для графического отображения полученных результатов найдём крайние значения скалярных функций, подставив соответствующие значения аргументов, x1 = 0; x1 = 1

	Линии			Аргументы
			x1	= 0	x1	= 1
	l1	(x1 )		2		5
	l 2	(x1 )		6		3

53

Т Е О Р И Я И Г Р

В.М.Дуплякин

Имея координаты крайних точек, построим линии l1 (x1 ), l2 (x1 ) , как показано ниже на рис. 7.1.

Рис. 7.1 – Определение оптимальной стратегии игрока Р1

Далее займёмся построением линии ψ(x ) = min[x] ´ éaj ù .
1	j=1,2	ë û

Мысленно пересекаем вертикалями построенные линии l1 (x1 ), l2 (x1 ) , в

каждом из этих мысленных сечений получаем две точки и выбираем ту из них, вертикальная координата которой минимальна. Совокупность найденных минимумов представляет собой точки искомой линии ψ( x1 ), как это показано

на рис.7.1.

После этого найдём цену игры при оптимальных смешанных стратегиях – это будет максимум на линии ψ(x1 ) (если максимума внутри нет, то тогда

выбираем наибольшее значение при крайних координатах).

Таким образом, реализована процедура определения цены при выборе оптимальных смешанных стратегий игрока Р1

ν		é	j ù	= max ψ(x1) = 4.	(7.8)
	= max min [x]× ëa û
	x	j=1,2		x1

Приравнивая уравнения линий l1 (x1 ), l2 (x1 ) , найдём координату точки

их пересечения, которая представляет собой оптимальную вероятность выбора

первой стратегии

		3× x(0)	+ 2 = -3× x(0)		+ 6,
	2	1		1		2		1
откуда получаем x1(0) =		≈ 0,66(6) и		x2(0) = 1− x1(0) = 1 −			=		≈ 0,33(3) .
	3					3		3

54

Т Е О Р И Я И Г Р

В.М.Дуплякин

Убеждаемся, что полученный результат соответствует выполненному на рис. 7.1 графическому построению.

На всякий случай выполним проверку, подставив значения координат в уравнение одной из линий, например l1(x1 )

l1(x1(0) ) = l1(23) = 3´ 23 + 2 = 63 + 63 = 123 = 4.

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

l2 (x1(0) ) = l2 (23) = -3´ 23 + 6 = - 63 + 183 = 123 = 4 .

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

значением цены, подставив в уравнение одной из линий					l1(x1 ) или l2 (x1 ),
например					2 .
ν = l1(x1(0) )		Þ	4 = 3´ x1(0) Þ x1(0) =
Окончательно полученное решение представим в виде					3
éx(0)	ù =	éx(0) , x(0)		ù = [0,66(6); 0,33(3)].
ë	û	ë 1	2	û

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

Воспользуемся соотношением (7.2)

ν = miny max [ai ]×[y],

i=1,2

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

случае представляет уравнение прямой линии

g ( y) = [a

]´

é y1

ù

= [5; 3]´

é y1

ù

= 5× y + 3× y

2

;

(7.9)

1

1

ê

ú

ê

ú

1

ë y2

û

ë y2

û

g

2

( y) = [a

2

]´

é y1

ù

= [2; 6]´ é y1

ù

= 2 × y + 6× y

2

.

(7.10)

ê

ú

ê

ú

1

ë y2

û

ë y2

û

55

Т Е О Р И Я И Г Р										В.М.Дуплякин
Подставив выражение для координаты y2							= 1 − y1 в соотношения (7.9,
7.10), получим	g1( y1 ) = 5 × y1 + 3× (1 - y1 ) = 2 × y1 + 3 ;									(7.11)
	g2 ( y1 ) = 2 × y1 + 6 × (1 - y1 ) = -4 × y1 + 6 .									(7.12)
Найдём	крайние		значения		скалярных			функций,		подставив
соответствующие значения аргументов, y1 = 0;							y1 = 1
		Линии			Аргументы
				y1	= 0		y1 = 1
		g 1( y1 )			3		5
		g 2 ( y1)			6		2

По крайним точкам, построим линии g1 ( y1 ), g2 ( y1 ) , как показано ниже на рис. 7.2.

Рис. 7.2 – Определение оптимальной стратегии игрока Р2

Займёмся построением линии ξ( y1) = max[ai ] ×[ y] .

i=1,2

В каждом из произвольных вертикальных сечений мысленно находим точки пересечения с линиями g1 ( y1 ), g2 ( y1 ) . Совокупность найденных

максимумов представляет собой точки искомой линии ξ ( y1 ) , как это показано

на рис. 7.2.

После этого найдём цену игры при оптимальных смешанных стратегиях игрока Р2 – это будет минимум на линии ξ ( y1 ) .

56

Т Е О Р И Я И Г Р

В.М.Дуплякин

Таким образом, реализована процедура определения цены при выборе оптимальных смешанных стратегий игрока Р2

ν = min max [ai ]×[ y].	(7.13)
y i=1,2

Приравнивая уравнения линий g1 ( y1 ), g2 ( y1 ) , найдём координату точки

их пересечения, которая представляет собой оптимальную вероятность выбора

первой стратегии

		2 × y(0)	+ 3 = -4 × y(0)	+ 6,
	1	1	1		1		1
откуда получаем y1(0) =		= 0,5 и	y2(0) = 1− y1(0) =1−			=		= 0,5.
	5				2		2

Таким образом, игрок Р2 должен случайным образом смешивать свои стратегии в равных частях, что гарантирует ему проигрыш не более 4-х усл. единиц.

Выполним проверку, подставив значения координат в уравнение одной из линий, например g1( y1 )

g1( y1(0) ) = g1(12) = 2 × 12 + 3 = 1 + 3 = 4 .

Нами получена цена оптимальной игры, что подтверждает правильность выполненного решения. Подстановка найденного решения в уравнение линии g2 ( y1 )приводит к такому же результату

g2 ( y1(0) ) = g2 (12) = −4 × 12 + 6 = −2 + 6 = 4 .

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

Окончательно решение для игрока Р2 представим в виде

é	(0) ù	é y(0)	ù	é0,5ù
		1	ú	= ê ú.
ë y	û	= ê (0)
		ë y2	û	ë0,5û

57

Т Е О Р И Я И Г Р										В.М.Дуплякин
7.3. Доминирование в играх 2х2
Решение матричных игр с нулевой суммой и размерностью 2х2 в
смешенных стратегиях позволяет наглядно проиллюстрировать понятие
доминирования столбцов и строк, которое ранее было введено достаточно
формальным путём.
Обратимся к примеру с платёжной матрицей приведенной ниже
Платёжная			Стратегии
матрица			игрока Р2							max
[A]				a	1	a	2		min
										min
Стратегии игрока Р1	a1			3		4		→	3	5
	a2			5		6		→	5
				↓		↓
max				5		6
min max				5
aˆ = max		min		{aij} = 5				- нижняя цена игры;
i=1,2		j=1,2
(		max		{aij}= 5 - верхняя цена игры.
a = min
j=1,2		i=1,2

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

Опуская подробности, рассмотрим результаты скаляризации

ν

= max min [x]

é

j ù

× ëa

û = max ψ(x1 ) = 5

x

j=1,2

x1

с построением линий l (x) = [x] ´

éa1 ù

и

l

2

(x) = [x] ´ éa2

ù представив их

1

ë

û

ë

û

графически на рисунке 7.3.

Из выполненного построения очевидно, что решение может находиться

только

на

линии l (x) =

[x] ´ éa1

ù

,

при

построении

которой используется

1

ë

û

столбец

éa1

ù, поэтому данный столбец представляет собой dominant-столбец.

ë

û

58

Т Е О Р И Я И Г Р

В.М.Дуплякин

Как мы отмечали ранее, доминируемый столбец éa2	ù может быть изъят из
ë	û

рассмотрения – теперь это наглядно иллюстрируется рисунком 7.3.

Рис. 7.3 – Формирование dominant-столбца
Далее рассмотрим скаляризацию вида	ν = min max [ai ]×[ y] = 5.
			y	i=1,2
é	y	ù		g2 ( y1) = [a2	é	y	ù
Построение линий g1( y1) = [a1 ]´ ê	1	ú	и		]´ ê	1	ú	,
ë1	- y1 û				ë1	- y1 û
приведенное на рисунке 7.4 показывает, что строка				[a2 ] является доминант-
строкой.

59