Л. Петросян Теория игр

Подставляя (7.15), (7.16) в функцию выигрыша и используя предположение о неубывании ценностей объектов, а также (7.14), получаем

K(X*,J):

Ь-т;(1-л>1;=«>(о, i-/. и.

Таким образом, для всех i,j=\, ..., и выполняются неравенства

K(i,y*)^(p(l)^K(x*,j).

Тогда по теореме п. 7.1 х* и у* — оптимальные стратегии игроков и vA = <p(l) — значение игры. Игра решена.

§ 8. ДОМИНИРОВАНИЕ СТРАТЕГИЙ

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

8.1. Определение. Говорят, что стратегия х" игрока 1 до­ минирует стратегию х" в (тхп)-игре ТА, если для всех чистых стратегий je(l, ..., и} игрока 2 выполняются неравенства

x'ai>x"ai. (8.1)

Аналогично, стратегия у' игрока 2 доминирует его стратегию у", если для всех чистых стратегий /е{1, ..., т) игрока /

a , / W .

(8.2)

Если неравенства (8.1), (8.2) выполняются как строгие, то говорят о строгом доминировании. Частным случаем доминирования страте­ гий является их эквивалентность.

Определение. Будем называть стратегии х" и х" игрока 1 эк­ вивалентными в игре ГЛ, если для ecexje{\, ..., л}

x'aJ=x"aJ,

и обозначать х'~х".

40

Для двух эквивалентных стратегий х" и х" выполняется (для каждого у е У) равенство

К(х',у) = К(х",у).

Аналогично, стратегии у' и у" игрока 2 эквивалентны (у' ~у") в игре ГА, если для всех /е{1, ..., т)

у'а^У'ъ.

Отсюда имеем, что для любой смешанной стратегии хеХ игрока 1 выполняется равенство

К(х,у') = К(х,у").

Для чистых стратегий введенные определения трансформируют­ ся следующим образом. Если чистая стратегия Г игрока 1 до­ минирует стратегию i", а чистая стратегия / игрока 2 — стратегию / ' того же игрока, то для всех i'=l, ..., т; j=\, ..., и выполняются неравенства

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

аг^щ- и d<id".

Эквивалентность пар стратегий i\ i"(i'~i") nj',j"(j'~j") означает выполнение равенства аг = аг (</ = </).

Определение. Будем говорить, что стратегия х"(у") игрока 1 (2) доминируема, если существует стратегия х'фх"(у'Фу") этого

игрока, которая доминирует х"(у"). В противном случае стратегия х"(у") недоминируема.

Аналогично стратегия х" (соответственно у") игрока 1 (2) назы­ вается строго доминируемой, если существует стратегия х'00 этого игрока, которая строго доминирует х"(у"), т. е. для всех

У= 1, n(i= 1, т) выполняются неравенства x'd>x"d, aiy'<а{у".

В противном случае говорят, что стратегия х"(у") игрока 1 (2)

недоминируема строго.

8.2. Покажем, что игроки могут не использовать доминируемые стратегии. Этот факт устанавливает следующее утверждение.

Теорема. Если в игре ТА стратегия х' одного из игроков до­ минирует оптимальную стратегию х*, то стратегия х' также оптимальна.

Доказательство. Пусть, для определенности, х' я х* — стра­ тегии игрока 1. Тогда в силу доминирования

x'aj^x*aJ

41

для всех j=l, п. Откуда	в силу оптимальности стратегии х*
(см. п. 7.3) получаем
w^=min x*aJ^min		x'aJ^min x*aJ=vA
j	j	j

для Bcexj= 1, п. Поэтому согласно теореме п. 7.3 стратегия х' также оптимальна.

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

Теорема. Если в игре ТА стратегия х* одного из игроков оп­ тимальна, то х* — недоминируема строго.

Доказательство. Пусть, для определенности, х* — оптималь­ ная стратегия игрока 1. Предположим, что х* — строго доминиру­

ема, т. е. существует такая стратегия х'еХ,		что
х'а)>х*а),	у=1, 2, ..., и.
Откуда
min xV>min x*aJ.
i	i
Но в силу оптимальности	х*еХ	выполняется равенство

min x*aJ=vA. Поэтому справедливо строгое неравенство

j

max min xaJ>vA,

x j

что противоречит тому, что vA — значение игры (п. 7.3). Получен­ ное противоречие доказывает теорему.

Понятно, что обратное утверждение, вообще говоря, неверно. Так, в игре с матрицей

1-я и 2-я чистые стратегии игрока 1 недоминируемы строго, но они неоптимальны.

С другой стороны, интуитивно понятно, что если 1-я строка матрицы А (/-й столбец) доминируема, то нет необходимости при­ писывать ей (ему) положительную вероятность. Таким образом, для нахождения оптимальных стратегий вместо игры ГЛ достаточно решить подыгру IV, где А' — матрица, получаемая из матрицы

А вычеркиванием доминируемых строк и столбцов.

42

Прежде чем перейти к точной формулировке и доказательству
этого результата, введем понятие расширения смешанной стратегии
х на i-м месте. Если х=(£1, .... £т)еХ и l^i^m+l,jo	расширени­

ем стратегии х на i-м месте будем называть вектор xi=(£1, .... £,_,,

О, &. —. £m)eRm+i. Так, расширением вектора (1/3, 2/3, 1/3) на 2-м месте является вектор (1/3, 0, 2/3, 1/3); расширением на 4-м месте — вектор (1/3, 2/3, 1/3, 0); расширением на 1-м месте — вектор (0, 1/3, 2/3, 1/3).

8.3. Теорема. Пусть Гл — (тхп)-игра. Предположим, что i-я строка матрицы А доминируема (т. е. доминируема чистая страте­ гия i первого игрока) и пусть ГЛ— игра с матрицей А', получаемой

из А вычеркиванием i-й строки. Тогда справедливы следующие утвер ждения.

1.vA = vA.

2.Всякая оптимальная стратегия у* игрока 2 в игре IV являет­

ся оптимальной и в игре Гл.
3. Если	х* — произвольная оптимальная стратегия игрока
1 в игре ГА'	и х' —расширение стратегии х* на i-м месте, то

х* — оптимальная стратегия этого игрока в игре ТЛ.

4. Если i-я строка матрицы А строго доминируема, то произ­ вольная оптимальная стратегия х* игрока 1 в игре Тл может быть получена из некоторой оптимальной стратегии х* в игре ГА рас­

ширением на i-м месте.

Доказательство. Не нарушая общности, можно предполо­ жить, что доминируемой является последняя т-я строка. Пусть х= (£lt.... t,m) — смешанная стратегия, которая доминирует строку т. Если £„=0, то из условия доминирования для всех у=1, 2, ..., п получаем

т	т—1
/ - 1	i - 1	(8.3)

£6=1, £2*0, f=l, ...,m-l.

Впротивном случае (£т>0) рассмотрим вектор х''=(£,[, .... С)> г л е

г,=	Ш		(8.4)
		i=m.

Компоненты вектора неотрицательны (б'^О, i=\, ..., и ) и ^ £/=1-

i - 1

С другой стороны, для всеху'=1, ..., и имеем

43

1	tn	1	m
— !£«<,>оц,--			Y 6
И Л И
	m — i	1	m	—1
—у	E	60u>flWr-r I		&
1 — 5m j . i			1 — Cm (-1
Учитывая (8.4), получаем
7 B - 1		ffl-1

E Ца-ц^вщ E ^'=a»>J=ls -, n,

i - i

(8.5)

m - l

X « = 1 , {/>0, i=l m - l .

i - l

Таким образом, всегда из доминирования m-й строки следует, что она не превосходит выпуклую линейную комбинацию оста­ льных m— l строк [(8.5)].

Пусть (х*. y*)eZ(rA) — ситуация равновесия в игре Г^, х* = (£,\,

•••>	£m-i), У* = (ч*> —. *&• Для доказательства утверждений 1, 2,
3 теоремы достаточно показать, что К(х'т, y*)=vA> и
	Е	a« »& < ^ '	< Ё «У«*+0 * «ч>	(8.6)
для всех 1=1, ..., т;J-j\		— \ , ..., п.	i-l	стратегий
(х*,	Первое равенство очевидно, а из оптимальности
	у*) в игре Гл- следует выполнение неравенств

пт—\

Е	ay4j<vA'** £ «</£' f=1> •••> « - 1 иУ=1, ..., и.	(8.7)
; ' - 1	i - l

Из (8.7) очевидным образом следует правое из неравенств (8.6). Докажем левое неравенство. Для этого достаточно показать, что

я

Е Цц/%<*4'-

Из неравенств (8.3), (8.5) получаем

я	л	m—I		m —1
Е «wq/^E		Е ««/&• ч7< Е		v*Zi=vx,
j - l	j - l	i - l	( - 1

что и доказывает первую часть теоремы.

Для доказательства второй части теоремы (утверждение 4) до­ статочно заметить, что в случае строгого доминирования /и-й стро­ ки неравенства (8.3), (8.5) выполняются как строгие для всех j= 1, п.

44

Поэтому

яя т—1

Е °Ч/fy< £ £ *» & 1; < »i«-

Тогда из теоремы п. 7.6 получаем, что у любой оптимальной стратегии игрока / в игре Г^ /и-я компонента равна нулю. Теорема доказана.

Сформулируем теорему о доминировании для второго игрока, доказательство которой опустим.

Теорема. Пусть Тл — (тхп)-игра. Предположим, что j-й сто­ лбец матрицы А доминируем и пусть ГА< игра с матрицей А',

получаемой из А вычеркиванием j-го столбца. Тогда справедливы следующие утверждения:

1.vA=vA.

2.Всякая оптимальная стратегия х* игрока 1 в игре ГА' являет­

ся оптимальной и в игре ТА.

3. Если_у* — произвольная оптимальная стратегия игрока 2 в иг­ ре Т'л и )>j —расширение стратегии у* на j-м месте, то у) — оптимальная стратегия игрока 2 в игре ТА.

4. Далее, если j-й столбец матрицы А строго доминируем, то произвольная оптимальная стратегия у* игрока 2 в игре ГА может быть получена из некоторой оптимальной стратегии у* в игре ГА- расширением на j-м месте.

8.4. Обобщим полученные результаты. Подведем итоги. Теоре­ мы п. 8.3 дают алгоритм понижения размерности матрицы игры. Так, если строка (столбец) матрицы не больше (не меньше) некото­ рой выпуклой линейной комбинации остальных строк (столбцов) этой матрицы, то для нахождения решения игры можно эту строку (столбец) вычеркнуть. При этом расширение оптимальных страте­ гий в игре с усечешшой матрицей даст оптимальное решение исход­ ной игры. Если неравенства выполнялись как строгие, то множество оптимальных стратегий в первоначальной игре можно получить расширением множества оптимальных стратегий усеченной игры, в противном случае при такой процедуре оптимальные стратегии можно потерять. Поясним применение данных теорем на примере.

Пример 14. Рассматривается игра с матрицей

"2 1 1 0 "

2 3 1 3

А= 3 1 2 0 0 3 0 6

Так как 3-я строка аэ превосходит первую (а3 > at), то, вычеркивая

45

первую строку, получаем

2	3 1 3~|
[03	31 2О 06 J1.
В этой матрице 3-й столбец а3	не превосходит 1-й столбец а1

Поэтому получаем А2= п: ц

Uо бJ

Впоследней матрице никакая строка (столбец) не доминируется другой строкой (столбцом). Вместе с тем 1-й столбец а1 превос­ ходит выпуклую линейную комбинацию столбцов а2 а а3, так как 1^1/2о2 + 1/2в3, поскольку 3> 1/2+ 1/23, 1 = 1/22+1/2.0,

3=0 • 1/2+1/2 • 6. Исключая 1-й столбец, получаем

В

В этой матрице 1-я строка эквивалентна смешанной стратегии х=(0, 1/2, 1/2), поскольку 1 = 1/2-2+0-1/2, 3 = 0-1/2 + 6-1/2. Таким образом, исключая 1-ю строку, получаем матрицу

[::}

Оптимальные стратегии х* и у* игроков в игре с этой матрицей равны х*=у* = (3/4; 1/4), при этом значение v игры равно 3/2.

Последняя матрица получена вычеркиванием первых двух строк и столбцов, поэтому оптимальными стратегиями игроков в исход­ ной игре являются расширения указанных стратегий на 1-ми 2-м местах, т. е. £2=5»?, = (0, 0, 3/4, 1/4).

§ 9. ВПОЛНЕ СМЕШАННЫЕ И СИММЕТРИЧНЫЕ ИГРЫ

Знание спектра оптимальной стратегии упрощает нахождение решения игры. В спектр оптимальной стратегии могут входить лишь существенные чистые стратегии игрока. При этом никакая существенная стратегия не является строго доминируемой, что не­ посредственно следует из теорем § 8.

9.1. Рассмотрим класс игр, в котором знание спектра достаточ­ но для нахождения решения игры.

46

Определение. Стратегия х (у) игрока 1 (2) называется вполне смешанной, если ее спектр состоит из множества всех стратегий игрока, т. е. Mx=M{Ny=N).

Ситуация равновесия (х*. у*) называется вполне смешанной, если стратегии х* и у* — вполне смешанные. Игра ГА называется вполне смешанной, если каждая ситуация равновесия в ней является вполне смешанной.

Следующая теорема утверждает, что вполне смешанная игра имеет единственное решение.

Теорема. Вполне смешанная (т х п)-игра ГА имеет единственную ситуацию равновесия (х*. у*) и квадратную матрицу (т=п). Если чАфО, то матрица А невырожденная и

.	иА~1
**=-—',					(9.1)
	иА	'и
„.	А~хи
У*=-^г>					(9-2)
	иА *и
^ = - ^ г -					(9.3)
	иА	'и	Сде%*		y* = (rl\-	—
Доказательство. Пусть х* =		(£\, ....		и
..., IJj 6 У* — произвольные оптимальные стратегии игроков, a vA						—
значение игры ГА. Поскольку	Г^ — вполне смешанная игра, х*
и у* — вполне смешанные стратегии, которые (и только они) явля­
ются решениями систем линейных неравенств п. 7.6:
xaJ=vA, xu=l,	x>0,j=l,		..., п;		(9.4)
yat=vA, yw= 1, у>0, i= l,			..., m,		(9.5)

где и=(1, ..., l)eiT, w=(l, ..., 1)еЛ".

Покажем, что решение вполне смешанной игры (х*, у*) единст­ венно. Множества X*. У*, заданные (9.4) и (9.5), являются непус­ тыми выпуклыми многогранниками и, следовательно, имеют край­ ние точки. Согласно второй из теорем п. 5.2 имеем

/n^rangfa1,	..., a", и]=Т2Л%[А, u]^m,	(9.6)
H^rang^,	..., ат, w] = rang[^, w]^n.	(9.7)

Теперь из этой же теоремы следует, что множества X*. Y* имеют по одной крайней точке и, следовательно, состоят только из них (как выпуклые многогранники, содержащие единственную крайнюю точ­ ку). Единственность решения (х*, у*) доказана.

Пусть vA = 0. Тогда однородная система xaJ=vA,j=l, n

47

имеет ненулевое решение, откуда rang (A)<m. Так как rang [А, иТ]=т, имеем: rang (Л)=/и—1. Аналогично, из (9.5) и (9.7) следует, что тап$(А)=п — 1. Отсюда п=т.

Пусть vA^0. Тогда

rang (A)=rang [A, i^«] = rang|>4, и]=т, rang (А)=rang [A, vAw]=rang [A, w]=n.

Отсюда имеем H=m=rang(.4), т. е. А — невырожденная матрица. Система уравнений x*A=vAu имеет решение

x*=vAuA~i.

Запишем решение системы Ay*—vAu: y*=vAA~1u.

Так как x*u=l=vAuA~lu, то v.=

.

лл иА~1и

Теорема доказана.

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

Теорема. Пусть в (тхт)-игре ГА матрица А является невыро­ жденной. Тогда, если игрок 2 имеет в ТА вполне смешанную оп­ тимальную стратегию, то игрок 1 имеет единственную оптималь­ ную стратегию х* (9.1). Если в игре ГА вполне смешанную оптималь­ ную стратегию имеет игрок 1, то игрок 2 имеет единственную оптимальную стратегию у* (9.2), при этом значение игры vA равно

(9.3).

Пример 15. ((2 х 2)-игра.) Пусть дана (2 х 2)-игра с матрицей Гаи а12

\_л21 ч1г

Произвольная смешанная стратегия х игрока 1 может быть записа­ на в виде *=(<!;, 1—£)> где 0<£<1. Аналогично, смешанная страте­ гия игрока 2 имеет вид у=(п, 1—п), где 0 < » J < 1 . Выигрыш в ситу­ ации (х, у) равен

K(x,y)=^[a11n + ai2(\-n)]+^-0[^2irl

+ ^22(i-rl)l

Предположим теперь, что в игре ГА нет ситуации равновесия в чистых стратегиях (в противном случае решение просто найти из

равенства минимаксов) и пусть х* = (£*, 1 —£*), у* = (ч*, 1 — п*) — произвольные оптимальные стратегии соответственно первого и второго игроков. Ситуация (х*. у*) и игра ГА являются вполне смешанными (<!;*> О и п*>0). Поэтому по теореме п. 9.1 в игре существует единственная пара оптимальных смешанных стратегий, которые являются решением системы уравнений

48

a2i'?* + (1 -'?*)a 22=^) « ц { ' + (1-{*)«21=^. a 12^* + ( 1 - ^ * ) « 2 2 = ^ -

Если добиваться, чтобы ьАфЬ (например, если все элементы матри­ цы А положительны, то это неравенство вьшолняется), то решение игры

vA=—~—, x*=vAuA \ y*=vAA~iu,

иА 1и

где u=(l, 1). Так, легко проверить, что у матрицы А=\'-_Ц' ~3| нет

седдовой точки. Обратная матрица А~1 равна -4_1 =

• Тогда

1^=1/3, х* = (2/3, 1/3), >* = (1/3, 2/3).

9.2. Исследуем частный класс игр с матрицами специального вида.

Определение. Игра ГА с квадратной матрицей А называется симметричной, если матрица А — кососимметричная, т. е. если (Ху= — ctji для всех i и 7.

Вэтом случае все диагональные элементы матрицы А равны О,

т.е. ан=0 при всех i. Для кососимметричнои матрицы А всегда

выполняется условие АТ= — А. Поскольку матрица А квадратная, множества смешанных стратегий игроков совпадают, т. е. Х= Y.

Докажем теорему о свойствах решения симметричной игры Г^, которая полезна при отыскании ситуации равновесия.

Теорема. Пусть ГА — симметричная игра. Тогда vA = 0

и множества оптимальных стратегий игроков совпадают, т. е. X* = Y*.

Доказательство. Пусть А — матрица игры и хеХ— произ­ вольная стратегия. Тогда хАх=хАТх= —хАх. Поэтому хАх=0.

Пусть (х*. y*)eZ(A)— ситуация равновесия, а vA — значение игры. Тогда

vA = х*Ау* < х* Ау, vA=x*Ay*^xAy*

для всех хеХ, ye Y. Следовательно,

vA^x*Ax* = 0, vA^y*Ay* = 0.

Откуда получаем vA = 0.

49