Петросян_Теория_игр
.pdfПодставляя (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