ли не в чистых стратегиях для единичной партии, то в смешанных для большого количества партий. Формально наличие такой возможности составляет суть основной теоремы теории игр, доказательство которой приводится, например, в [9]. Одной из основ практических методов решения игр является также следующая теорема: если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш игроков остается неизменным и равным цене игры независимо от того, какую смешанную или чистую стратегию применяет другой игрок, если только он не выходит за пределы своих полезных стратегий.

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

m
∑ pi*aij =V , j=1,2,…,n: q*j	≠ 0	;
i=1
n
∑q*jaij =V , i=1,2,…,m: pi* ≠ 0		.	(62)

j=1

Первая строка в (62) соответствует чистым стратегиям стороны В, входящим в число полезных (q*j ≠ 0 ), вторая – полезным чис-

тым стратегиям стороны А. Если записать (62) для всего множества исходных чистых стратегий сторон, следует учесть, что применение стороной В чистой стратегии, не входящей в число полезных, может привести к ухудшению получаемого ею результата – увеличению среднего проигрыша. Сумма в первой строке может оказаться больше цены игры V. Применение стороной А чистой стратегии, не входящей в число полезных, соответственно может привести к уменьшению ее среднего выигрыша. Таким образом, для всего множества исходных чистых стратегий сторон в общем случае

m
∑ pi*aij ≥V , j=1,2,…,n;	(63)
i=1
n
∑q*jaij ≤V , i=1,2,…,m.	(64)

j=1

5.2.2.Способы упрощения стратегических матричных игр

Рассматриваемые ниже способы, или приемы, упрощения игр наиболее полно описаны в книгах Е.С. Вентцель [3,4]. Совокуп-

130

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

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

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

тегий называют доминирующей, а вторую – заведомо невыгодной

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

Так для стороны А возможно наличие пары чистых стратегий Аk и Аl, для которых akj ≥ alj , j=1,2,…,m, причем хотя бы для

одного значения j имеет место ak j >al j . В таком случае Аk является доминирующей, Аl – заведомо невыгодной, p*l =0.

Пример 36 (продолжение). Рассмотрим пару стратегий В3 и В5. При первой, второй и четвертой чистых стратегиях стороны А стратегия В5 приносит стороне В проигрыш, больший, чем стратегия В3. При третьей стратегии стороны А результат применения В3 и В5 одинаков. Следовательно, стратегия В5 является заведомо невыгодной по сравнению с В3. Аналогично можно обнаружить, что стратегия В4 заведомо невыгодна по сравнению с В2. После исключения столбцов, соответствующих чистым стратегиям В4 и В5 (табл. 27) перейдем к анализу стратегий стороны А.

При всех оставшихся чистых стратегиях стороны В стратегия А1 приносит стороне А выигрыш, меньший, чем стратегия А2. Следовательно, стратегия А1 является заведомо невыгодной по сравнению с А2. Такой же вывод можно сделать и по отношению к стратегии А3.

131

Таблица 27

Стратегии	В1	В2	В3	α
А1	-1	1	0	−1
А2	4	2	3	2
А3	3	-1	1	-1
А4	1	4	-2	-2
β	4	4	3

После исключения строк, соответствующих чистым стратегиям А1 и А3 (табл. 28) вернемся еще раз к анализу стратегий стороны В и исключим как заведомо невыгодную стратегию В1. В результате игру удалось упростить до размерности 2 × 2 . Полученная игра соответствует рассмотренному выше примеру 37. Остается записать решение исходной игры: P*=(0; 0,857; 0; 0,143), Q*=(0; 0,714; 0,286; 0; 0), V=2,286.

Таблица 28

Стратегии	В1	В2	В3	α
А2	4	2	3	2
А4	1	4	-2	-2
β	4	4	3

Учет дублирующих стратегий. Если для одной из сторон име-

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

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

Пример 38. В игре, матрица которой представлена в табл. 29,

нижняя цена α=1, верхняя цена β=4, седловая точка отсутствует

[3].

132

						Таблица 29
Стратегии	В1	В2	В3	В4	В5	α
А1	0	5	4	2	3	0
А2	5	0	2	4	5	0
А3	5	5	1	1	2	1
А4	5	0	2	4	5	0
β	5	5	4	4	5

Переходя к упрощению игры прежде всего исключим заведомо невыгодную по сравнению с В4 стратегию В5.

Стратегии А2 и А4 соответствуют указанному выше признаку, следовательно, являются дублирующими. В процессе решения игры может далее рассматриваться только одна из них, например А2. Соответственно размерность задачи снизится. Целесообразно далее наравне с чистыми стратегиями А1 и А3 оперировать новой стратегией, которую можно обозначить как А24 и которая фактически является смешанной, причем исходные чистые стратегии А2 и А4 в рамках этой смешанной стратегии могут применяться с любыми частотами. Условно такой прием отразим следующим обра-

зом: A24 : A2 A4 . Упрощенная матрица игры представлена в табл. 30.

					Таблица 30
Стратегии	В1	В2	В3	В4	α
А1	0	5	4	2	0
А24	5	0	2	4	0
А3	5	5	1	1	1
β	5	5	4	4

Дальнейшее упрощение в рассматриваемом примере может быть выполнено на основе следующего приема.

Учет симметричных фрагментов. Симметричным называют фрагмент матрицы игры, представленный в табл. 31. Рассматривая табл. 31 как матрицу игры размерностью 2×2, отметим, что при a ≠ b такая игра не имеет седловой точки и может быть решена в смешанных стратегиях следующим образом:

133

Таблица 32

p* =	a − b	= 0,5	, p* =1 − p* = 0,5 ;		q* =	a − b	= 0,5 ,
1	a + a − b − b		2	1	1	a + a − b − b

q2* =1−q1* = 0,5; V = a +2 b .

Таблица 31

Стратегии	В1	В2
А1	a	b
А2	b	a

Если помимо симметричного фрагмента в образующих его столбцах и строках содержится дублирование или другие симметричные фрагменты, в процессе решения игры размерность ее матрицы может быть сокращена следующим образом: образующие симметричный фрагмент пары чистых стратегий заменяются смешанными с частотами по 0,5; сам фрагмент заменяется одним элементом матрицы игры величиной (a+b)/2.

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

	Страте-	В12	В34	α	применим рассмотренный при-
	гии
					ем. Получаемая в итоге матри-
	А124	2,5	3	2,5
	А3	5	1	1	ца игры представлена в табл.
					32. Пары чистых стратегий, об-
					разующих	симметричные
	β	5	3
					фрагменты	игры, заменены

смешанными: А124, предусматривающей применение стратегий А1 и А24 с частотами по 0,5 (А124:

p1 =p2 4 =0,5); В12: q1 =q2 =0,5; В34: q3 =q4 =0,5. На пересечении со-

ответствующих им строк и столбцов помещены рассчитанные по указанному выше правилу выигрыши стороны А.

Для новой игры нижняя цена α=2,5, верхняя цена β=3, седловая точка отсутствует (необходимо отметить, что рассмотренный прием в отдельных случаях может привести к получению седловой точки, так как вместо исходных чистых уже используются смешанные стратегии).

Решение игры, представленной табл. 32, дает следующие ре-

зультаты: p*	=	1−5	=	−4	= 0,89	, p* =1 − p*		= 0,11;
124		2,5 +1−3 −5		−4,5		3	124

134

Таблица 33

q12* = −1−4,35 = 0,44 , q34* =1−q12* = 0,56 ; V=2,78.

С учетом использованных в процессе решения приемов вернемся к исходному набору чистых стратегий и запишем решение игры для примера 36: P*=(0,445; p*2 ; 0,11; p*4), p*2 + p*4 = 0,445; Q*=(0,22; 0,22; 0,28; 0,28; 0), V=2,78.

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

Графический способ упрощения игр размерностью 2 × n и

m× 2 .

Пример 39. В игре, матрица которой представлена в табл. 33,

нижняя цена α=3, верхняя цена β=6, седловая точка отсутствует. Отсутствуют также заведомо невыгодные и дублирующие стратегии. В первых двух столбцах имеется симметричный фрагмент, но учесть его рассмотренным выше способом невозможно из-за произвольного содержания оставшейся части строк. Тем не менее, размерность игры может быть снижена на основе графической интерпретации, рассмотренной в п. 5.2.1.

Рис. 38 показывает, что в формировании оптимальной смешанной стратегии стороны В участвуют только две из четырех ее чистых стратегий, а именно В2 и В3.

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

	смешанной	стратегии	Стра-	В1	В2	В3	В4	α
			тегии
	стороны А проходят вы-		А1	3	8	4	7	3
	ше и соответственно при-		А2	8	3	6	5	3
	носят стороне В проиг-
	рыш, больший цены игры
			β	8	8	6	7
	V. Следовательно, страте-
	гии В1 и В4	не входят в

135

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

Рис. 38

В результате получена игра размерностью 2×2 (табл. 34). Она по-прежнему не имеет седловой точки, но может быть решена на основе приведенных выше расчетных соотношений:

		Таблица 34		p1* =			6	− 3			=	3	=	0,43,
					8 + 6			− 4	− 3			7
Страте-	В2	В3	α
гии				p*			=1 − p* = 0,57 ;
А1	8	4	4
					2			1
А2	3	6	3			q2* =		6 −	4	= 0,29 ,
								7
β	8	6		q3* =1−q2* = 0,71; V=5,14.

Решение примера 39 с учетом всего исходного набора чистых стратегий: P*=(0,43; 0,57), Q*=(0; 0,29; 0,71; 0), V=5,14.

Пример 40. В игре, матрица которой представлена в табл. 35, нижняя цена α=3, верхняя цена β=5, седловая точка отсутствует. Отсутствуют также заведомо невыгодные и дублирующие стратегии.

136

Таблица 35

Стратегии	В1	В2	α
А1	3	5	3
А2	5	0	0
А3	1	7	1
А4	4	3	3
β	5	7

Процедура упрощения данной игры иллюстрируется рис. 39. В формировании оптимальной смешанной стратегии стороны А участвуют только две ее чистые стратегии, а именно А1 и А4. Это следует из того, что в точке, дающей решение игры (нижней точке геометрического места гарантированных проигрышей стороны В, на рисунке – жирной ломаной линии), пересекаются отрезки, соответствующие только этим чистым стратегиям. Отрезки, соответствующие остальным чистым стратегии стороны А, при оптимальной смешанной стратегии стороны В проходят ниже и соответственно приносят стороне А выигрыш, меньший цены игры V. Следовательно, стратегии А2 и А3 не входят в число полезных и при дальнейшем решении могут не учитываться.

Рис. 39

137