5. СТРАТЕГИЧЕСКИЕ МАТРИЧНЫЕ ИГРЫ

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

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

5.1.Основные термины и допущения. Формализация задачи. Принципы поиска решения

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

стороной).

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

В распоряжении стороны А имеется m вариантов поведения

А1,А2,…,Аm, называемых также стратегиями или чистыми стра-

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

Применение стороной А некоторой стратегии Аi , а стороной В некоторой стратегии Вj , в очередной партии игры приводит к получению стороной А выигрыша величиной ai j , а стороной В – проигрыша той же величины. Величины ai j для всех i=1,2,…,m и для всех j=1,2,…,n считаются априорно известными. Однако каждой из сторон неизвестно, какую стратегию выберет другая сторона в очередной партии.

120

Наиболее удобной формой задания игры является матричная –

матрица игры (табл. 22).

							Таблица 22
Стратегии	В1	В2	…	Вj	…	Вn		α
А1	a11	a12	… a1j		… a1n			α1
А2	a21	a22	… a2j		… a2n			α2
…	…	…	…	…	…	…		…
Аi	ai1	ai2	… aij		… ain			αi
…	…	…	…	…	…	…		…
Аm	am1	am2	… amj		… amn			αm
β	β1	β2	… βj		… βn

Задается матрица размерностью m× n , и принято говорить, что игра имеет размерность m× n .

Строки матрицы соответствуют чистым стратегиям стороны А, столбцы – чистым стратегиям стороны В. Элементы матрицы – выигрыши стороны А при всех возможных сочетаниях чистых стратегий сторон. Игра считается заданной, если наборы чистых стратегий и все значения ai j (i=1,2,…,m; j=1,2,…,n) заданы априорно.

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

Необходимо отметить, что при решении игровых задач приходится рассматривать и находить экстремумы несколько иного смысла, чем во всех рассмотренных выше задачах. С учетом неопределенности информации о стратегии противоположной стороны и гипотезы о выборе ею наилучшей для себя стратегии стороне А не приходится рассчитывать на получение максимального выигрыша, возможного в рассматриваемой задаче (максимального из заданных значений ai j ). Можно рассчитывать только на достижение максимума гарантированного выигрыша – нижней границы

121

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

Рассмотрим логику поиска максимального гарантированного выигрыша стороны А.

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

ному элементу в строке Аi : αi = min aij , это и есть гарантиро-

j

ванный выигрыш стороны A при i-й стратегии. При решении стратегической матричной игры гарантированные выигрыши стороны А заносятся в крайний правый столбец матрицы игры (табл. 22). Стороне A целесообразно выбрать такую стратегию Ai,

которой будет соответствовать α = maxαi .

i

При таком выборе сторона A при любой стратегии стороны B

будет получать выигрыш не менее α. То есть α – гарантированный выигрыш стороны A, максимальный на множестве чистых

стратегий. Величина α, определяемая, как α = max min αij , назы-
i	j

вается нижней ценой игры. Соответствующая ей стратегия Ai* на-

зывается максиминной.

Выполнив подобный анализ для стороны В, получим

β j = max aij – гарантированный проигрыш при j-й стратегии. Га-

i

рантированные проигрыши стороны В заносятся в нижнюю строку матрицы игры (табл. 22). Стороне В целесообразно выбрать та-

кую стратегию Вj, которой будет соответствовать β = minβ j .

j

Величина β, определяемая, как β = min max aij представляет собой
j	i

минимальный гарантированный проигрыш стороны В и называется верхней ценой игры. Соответствующая ему стратегия Bj* назы-

вается минимаксной.

Нетрудно убедиться в соотношении α ≤ β. Действительно, в соответствии с рассмотренными правилами определения нижней

и верхней цены игры для всех i и j справедливо: αi ≤ αij ≤ βj, откуда при i = i* и j = j* получим α ≤ β.

122

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

нижняя цена α=2, максиминная стратегия – А2, верхняя цена β=2, минимаксная стратегия – В2.

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

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

Если интерпретировать матрицу игры в рассмотренном примере как форму задания некоторой функции двух аргументов ai j =F(Аi ,Вj ), то с поправкой на дискретность аргументов графическое отображение такой функции окажется аналогичным рис. 22. Действительно, a22 в рассмотренном примере выполняет роль седловой точки (элемент a22 минимален в строке и максимален в столбце матрицы). Признаком наличия седловой точки в игре является совпадение нижней и верхней цены игры, седловая точка дает решение игры в чистых стратегиях. Цену игры, соот-

ветствующую решению игры в чистых стратегиях, называют чис-

той ценой игры (α=β=V).

Пример 35. В игре, матрица которой представлена в табл. 24, нижняя цена α=2, максиминных стратегий две – А2 и А4, верхняя цена β=2, минимаксных стратегий две – В2 и В3.

123

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

В данной игре имеется четыре седловых точки. Решение может быть сформулировано следующим образом: оптимальными для стороны А являются чистые стратегии А2 и А4, для стороны В – чистые стратегии В2 и В3, чистая цена игры V=2.

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

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

нижняя цена α=2, максиминная стратегия – А2, верхняя цена β=3, минимаксная стратегия – В3. Отметим, прежде всего, что здесь, в отличие от предыдущих примеров, нижняя и верхняя цены игры не совпадают.

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

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

124

партии свою стратегию сменит сторона А. Дальнейшее развитие игры пройдет следующим образом: третья партия – А4В2, результат 4; четвертая – А4В3, результат -2; четвертая – А2В3, результат 3 и так далее. Можно рассмотреть иные подходы к выбору стратегий сторон в последующих партиях. Но в любом случае будут получены следующие выводы:

1.В рассматриваемой игре не удается найти «устойчивого» сочетания чистых стратегий сторон. При любом сочетании стратегий, примененных в очередной партии, какая-либо из сторон будет заинтересована в изменении стратегии.

2.В матрице игры отсутствует седловая точка, т.е. ни один ее элемент не является одновременно минимальным в строке и максимальным в столбце матрицы.

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

рантированный (α для стороны А и β для стороны В) и располо-

женного в пределах между α и β.

Рассмотренный пример является примером стратегической матричной игры без седловой точки. Признак отсутствия седло-

вой точки – несовпадение нижней и верхней цен игры (α<β). Такая игра не имеет решения в чистых стратегиях, справедливого для единичной партии. Решение может быть найдено только для случая многократного повторения партий игры на множестве смешанных стратегий.

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

Смешанная стратегия определяется распределением вероятностей (частот применения) стороной ее чистых стратегий при многократном повторении партий игры. Смешанную стратегию стороны А принято описывать вектором P=(p1; p2; …; pm), для стороны В используется вектор Q=(q1; q2; …; qn), составляющие которых – вероятности или частоты применения сторонами их чистых стратегий. Очевидно, должны выполняться условия:

	m			n
0 ≤ pi ≤1	, i=1,2,…,т; ∑ pi =1	; 0 ≤ q j ≤1	, j=1,2,…,n;	∑qi =1.
	i=1			i=1

125