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

ца выигрышей для игры в нормальной форме имеет вид

(1,1)	(1,2)	(2,1)	(2,2)
1Г1	3	7	9]
2|_5	6	1	7 J

Значение игры равно 17/5, и оптимальные смешанные стратегии игроков 1 и 2 соответственно равны (2/5, 3/5), (3/5, 0,2/5,0).

Заметим, что в многошаговых играх с полной информацией (см. теорему п. 2.1) существует ситуация равновесия по Нэшу в классе чистых стратегий, а в случае антагонистических многошаговых игр — просто ситуация равновесия в чистых стратегиях. Вместе с тем во всех играх с неполной информацией, рассмотренных в при­ мерах 7 — 10, ситуации равновесия в чистых стратегиях не суще­ ствует.

7.2. Дадим теперь формальное определение многошаговой пози­ ционной игры.

Определение. Многошаговая позиционная игра п лиц Г опреде­ ляется:

1)Заданием древовидного графа G={X, F) с начальной вершиной х0, называемой начальной позицией игры.

2)Разбиением множества всех вершин X нап + 1 множество X,,

Х2, .... Х„, Хп+1, где множество X, называется множеством очеред­ ности i-го игрока i=\, ..., п, а множество X„+l = {x:Fx=0} —мно­ жеством окончательных позиций.

3) Заданием вектор-функции K(x) = (Kt (x),..., К„(х)) на множест­ ве окончательных позиций xeX„+i; функция Kt(x) называется выиг­

рышем i-го игрока.

4) Подразбиением каждого множества Х„ i=l, ..., п, на непересе­ кающиеся подмножества Х{, называемые информационными множе ствами i-го игрока. При этом для любых позиций одного и того оке информационного множества множество следующих за ними вершин должно содержать одно и то же число вершин, т. е. для любых

х, уе Х{: \FX\ — \Fy\ (\FX\ — число элементов множества Fx), и никак вершина информационного множества не должна следовать за неко­ торой другой вершиной этого оке множества, т. е. если хеХ\, то не

существует другой вершины уеХ{ такой, что yeFx (см. п. 1.2).

Определение многошаговой игры с полной информацией (см. п. 1.4) отличается от приведенного здесь лишь условием 4, где вводят­ ся дополнительные разбиения множеств очередности игроков Xt на

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

210

информации не знает самой позиции х, а знает лишь, что эта позиция находится в некотором множестве XJ,c:X,(xeX{). На ин­ формационные множества игрока условие 4 накладывает опреде­ ленные ограничения. Требование 1^1 = 1^1 для любых двух вершин

одного информационного множества вводится для того, чтобы вершины х, уеХ}, были неразличимы. Действительно, при \FX\ Ф \F^

игрок г мог бы различить между собой вершины х, уеХ\ по числу выходящих из них дуг. Если бы в одном информагшонном множест­ ве существовали две такие вершины х, у, что yeFx, то это означало

бы, что партия игры может пересекать дважды одно информацион­ ное множество, а это, в свою очередь, равносильно тому, что игрок i не помнит номера своего хода в данной партии, что трудно иредставимо в реальной игре.

§ 8. СТРАТЕГИЯ ПОВЕДЕНИЯ

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

8.1. Для дальнейшего исследования необходимо ввести ряд до­ полнительных понятий.

Определение. Альтернативами в вершине хеХ называются дуги, инцидентные с х, т. е. {(х, y):yeFx}.

Если \Fx\ = k, то в вершине х имеется к альтернатив. Будем

считать, что если в вершине х имеется к альтернатив, то они нумеруются целыми числами 1, ..., к, причем вершина х обходится по часовой стрелке. В вершине х0 первая альтернатива может быть указана произвольно. Если некоторая вершина хфх0 обходится по часовой стрелке, то первой альтернативой в х считается та, которая следует за единственной дугой (F~l, х), входящей в х (рис. 27).

Будем считать, что в игре Г все альтернативы перенумерованы указанным способом. Пусть Ак— множество всех вершин хеХ,

имеющих	ровно	к альтернатив, т. е.
Ак={х:Щ	= к}.	Пусть		l = {X\:X\<z
с X,} — множество			всех	информа­
ционных множеств игрока i. Под чи­
стой стратегией игрока i будем пони­
мать функцию		и„	отображающую
/, в множество положительных чисел,
так что иХХ^^к,		если Х\<^Ак. Будем			Рис 27
говорить,	что стратегия			и, выбирает

211

альтернативу / в позиции xeXJt, если щ(Х§=1, где / — номер аль­

тернативы.

Так же как это было сделано в п. 1.4, можно показать, что каждой ситуации и() = (и1(), ..., и„()) единственным образом соот­ ветствует партия со, следовательно, и выигрыш в окончательной позиции этой партии.

Пусть xeX„+i — некоторая окончательная позиция и со — един­ ственный путь (F — дерево), ведущий из х0 в х. Условие принадлеж­ ности позиции у пути со будем записывать в виде у в со или у<х.

Определение. Позиция хеХ называется возможной для «,(•), если существует ситуация м(), содержащая щ(), такая, что в си­ туации и (•) реализуется путь со, который содержит позицию х, т. е хесо. Информационное множество Х{ называется существенным для И/(), если некоторая позиция xeXj, возможна для ы,().

Множество позиций, возможных для м((), обозначим через Poss «,(•), а семейство информационных множеств, существенных для «/(•),— через Rel иД).

Лемма. Позиция хеХвозможна для м,() тогда и только тогда, когда «,(•) выбирает альтернативы, лежащие на отрезке партии сох от х0 до х во всех своих информационных множествах, пересека­ ющих сох.

Доказательство. Пусть xePossut(). Тогда существует ситу­

ация м(-), содержащая «,(•), такая, что партия со, реализовавшаяся

в этой ситуации, проходит через х: а это и означает, что на своих информационных множествах, пересекающих отрезок партии сох,

стратегия м,() выбирает альтернативы (дуги), принадлежащие сох. Пусть теперь щ() выбирает все альтернативы игрока i в сох. Для

того чтобы доказать возможность х для ы*(), необходимо постро­ ить ситуацию «(•), содержащую «,(•), в которой партия проходила бы через х. Для игрока кФг построим стратегию щ(), которая на информационных множествах Х{, пересекающих отрезок пути сох,

выбирает альтернативы (дуги), лежащие на этом пути, а в оста­ льном произвольна. Поскольку каждое информационное множество пересекает путь со лить однажды, это всегда можно сделать. В по­ лученной ситуации и(-) партия со обязательно пройдет через х. Следовательно, мы показали, что xePossM,().

212

8.2. Смешанные стратегии в многошаговой игре с неполной информацией Г определяются так же, как и в п. 4.2 гл. I для конечных игр.

Определение. Смешанной стратегией ц, игрока i называется

вероятностное распределение на множестве чистых стратегий иг­ рока i, которое каждой его чистой стратегии ut() ставит в соот­ ветствие вероятность qUj() (в дальнейшем для простоты будем писать просто qu).

Ситуация fi=(p.i, ..., /О в смешанных стратегиях определяет

распределение вероятностей на всех партиях со (следовательно, и на окончательных позициях Х„+1) по формуле

и

где Ри(со) = 1, если партия со реализуется в ситуации и(), и Р„(со)=0 в противном случае.

Лемма. Обозначим через РДх) вероятность реализации позиции х в ситуации ц. Тогда имеет место формула

ЗД=	Е _Яи,..Чи„=й		I Яи,	(8.1)
	{u():xePossuj(), /-1,и)	/ - 1	{и<:дсеРов«к,}

Доказательство этого утверждения непосредственно следует из леммы п. 8.1.

Математическое ожидание выигрыша Е,(р) игрока i в ситуации

ц равно
£,(/х) = £ Ъ(х)Р„(х),	(8.2)
xeXn+i

где Рц(х) вычисляется по формуле (8.1).

Определение. Позиция хеХназывается возможной для /х„ если существует ситуация ц в смешанных стратегиях, содержащая ци такая, что РДл:)>0. Информационное множество Х\ игрока i назы­ вается существенным для ць если некоторое хеХ{ является воз­ можным для ц,.

Множество возможных для /*, позиций обозначим через Poss ць а множество существенных для и, информационных множеств — че­ рез Rel/i,.

8.3. Исследуя многошаговые игры с полной информацией

213

(см. 3.3), мы показали, что выбор стратегии может осуществляться на каждом шаге в соответствующей позиции игры, а при решении конкретных задач необязательно (да и практически невозможно) определять заранее стратегию, т. е. полный набор рекомендуемого поведения во всех позициях (информационных множествах), по­ скольку такое правило (см. пример п. 2.2) «страдает сильной избы­ точностью». Можно ли сделать аналогичное упрощение в играх с неполной информацией, т. е. строить стратегию не как заранее фиксированное правило выбора во всех информационных множест­ вах, а формировать ее по мере попадания в соответствующее ин­ формационное множество? Оказывается, что в общем случае этого сделать нельзя. Однако существует класс игр с неполной инфор­ мацией, где такое упрощение возможно. Введем понятие стратегии поведения.

Определение. Под стратегией поведения ft, игрока i будем

понимать правило, которое каждому информационному множеству Х\сАк игрока i ставит в соответствие систему из к чисел

b(XJ,, v)^0, v = l, ..., к, таких что

2>(nv)= l,

V

где Ak={x:\Fx\ = k).

Числа b(X{, v) могут интерпретироваться как вероятности выбо­ ра альтернативы v в информационном множестве X{czAk, каждая

позиция которого содержит ровно к альтернатив.

Любой набор P=(filf ..., Р„) стратегий поведения для л игроков

определяет вероятностное распределение на партиях игры и окон­ чательных позициях следующим образом:

^/>И= П b(X{v).

(8.3)

X'fp+0

уеш

Здесь произведение берется по всем Х\ и v таким, что Х{(~]соФ0, и выбор в точке Х{ (~)со альтернативы с номером v приводит в пози­ цию, принадлежащую пути со.

В дальнейшем под понятием «путь» удобно подразумевать не только набор составляющих его позиций, но и набор соответству­ ющих альтернатив (дуг).

Ожидаемый выигрыш E,(fi) в ситуации fi = (fil} ..., /?,,) в стратеги­ ях поведения определяется как математическое ожидание

£,(/?)= £ ВДРДсоД 1=1 и, где сох — партия, завершающаяся позицией хеХп+1.

214

8.4. Каждой смешанной стратегии ц, можно сопоставить некото­ рую стратегию поведения Р,.

Определение. Стратегией поведения р„ соответствующей сме­ шанной стратегии n,= {qUi} игрока i, называется стратегия поведе­ ния, определенная следующим образом.

Если XJ,eRelfih то
Ъ{Х{, v)={ч*,***чтУЪ-*)	(8-4)
I Чщ

Если AT^Relft, то на множестве Х\ стратегию /?, можно опреде­ лить произвольным, отличным от (8.4) образом. {В случае Af-^Rel Hi знаменатель в выражении (8.4) обращается в нуль.) Для определен­ ности будем полагать

ЫХ{,у)=

X 9и,

(8.5)

Приведем без доказательства следующий результат.

Лемма. Пусть /?, — стратегия поведения игрока i, a # = {?«<,} — смешанная стратегия, определяемая формулой

Тогда pt — стратегия поведения, соответствующая /*,.

8.5. Определение. Игра Г называется игрой с полной памятью для i-го игрока, если для любых ut(-), X\, x из условий AT{eRel

ы< и xeXJt следует, что jcePossw,.

Из определения следует, что в игре с полной памятью для i-го игрока любая позиция из существенного для ы,() информационного

множества является возможной для ы,(-). Термин «полная память»

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

8.6. Лемма. Пусть Г — игра с полной памятью для всех игроков; со — некоторая партия в Г. Пусть xeXJ, — последняя позиция в пу­ ти со, в которой ходит игрок i, и пусть он выбирает в х дугу veco.

215

Положим

Tl(o))={ui:XJleRdu„u,(X]) = v}.

Если в со нет позиций из Х„ то через Tt{co) обозначим множество

всех чистых стратегий игрока i. Тогда партия со реализуется в тех и только тех ситуациях и{) = {и1{-), ••-, и„{)), для которых и,еТ({со).

Доказательство. Достаточность. Достаточно доказать, что если и,е Т,{со), то стратегия и, выбирает все дуги (альтернативы)

игрока I, входящие в партию со (если, конечно, игрок / вообще имеет ход в со). Однако если ы,е Tt{co), то .Y^eRel щ, и так как игра Г имеет

полную память, то хе Poss щ (хеш). Значит, согласно лемме п. 8.1, стратегия щ выбирает все альтернативы игрока г, входящие в пар­

тию со.

Необходимость. Предположим, что партия со реализуется в ситуации «(•), у которой и,фТ{со) для некоторого i. Поскольку

AfjeRelM/, это означает, что щ^Х^фу. Но тогда путь со не реализует­

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

8.7. Лемма. Пусть Г — игра с полной памятью для всех игроков. Пусть v — альтернатива {дуга) в партии со, инцидентная xeXJh где хесо, и следующая позиция игрока i {если она существует) в пути со есть уеХ,. Рассмотрим множества S и Т, где

S={ut:XieRelUl,u,{Xi)=v},

T={u,:X'!eRelui}.

Тогда S=T.

Доказательство. Путь u,eS. Тогда A^eRel uh и так как Г име­ ет полную память, то xePoss ut. Следовательно, по лемме п. 8.1 стратегия щ выбирает все дуги, инцидентные к позициям игрока г на

пути от х0 до х и ut{XJi)=v. Таким образом щ выбирает все дуги,

инцидентные к позициям игрока i на пути от х0 до у, т. е. у G Poss uu XkieRel щ и ы,е Т.

Пусть ы(еТ. Тогда .У*eRel щ, и так как Г имеет полную память, то j>ePoss щ. Однако это означает, что xePossu, и ut{X^)=v, т. е. u,eS. Лемма доказана.

8.8. Теорема. Пусть Р — ситуация в стратегиях поведения, соответствующая ситуации в смешанных стратегиях ц в игре Г {в которой все позиции имеют по крайней мере две альтернативы).

216

Тогда для того чтобы E,(P)=E,(n),i=U:.,n,

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

Доказательство. Достаточность. Пусть Г — игра с полной памятью для всех игроков. Фиксируем произвольное ц. Достаточно показать, что Рр(со)=Р11(со) для всех партий со. Если в со существует

позиция игрока /, принадлежащая несущественному для ц( инфор­ мационному множеству, то найдется XJ,eRelfilt Х{[\саФ0, такое, что для стратегии поведения /?,, соответствующей ць выполняется равенство b(X]it v)=0, где veto. Отсюда имеем РД<») = 0. Справед­ ливость соотношения Р/|(ш)=0 в этом случае очевидна.

Будем теперь считать, что все информационные множества 1-го игрока, через которые проходит партия со, существенны для ци i= 1, 2, ..., и. Пусть игрок i в партии со ходит по порядку в пози­ циях, принадлежащих множествам Х\,.... Х\, и выбирает в множест­ ве Х{ альтернативу Vj, j=\, ..., s. Тогда согласно формуле (8.4)

и лемме п. 8.7 имеем

Ub(Xivj)=	£ qU{.
J-l	И(бГ,(ш)

Действительно, поскольку в партии со игрок i свой 1-й ход делает из множества X), оно является существенным для всех м<(-), поэтому

знаменатель в формуле (8.4) для b(X\, Vj) равен единице. Далее в силу леммы п. 8.7 в формулах (8.4) числитель Ь(Х{, у,) равен

знаменателю Ь(Х{+\ vJ+1),j=l, ..., s. Согласно формуле (8.3) окон­ чательно получим

«-1 u,eTt(fo)

где Т,(со) определено в лемме п. 8.6.

В то же время на основании леммы п. 8.6

Р ,Н = Ев..,-9чЛ(а»)=		Е qv.4m.
"О	и	щеЩа)

т. е. Рм(со)=Р^(ю), и достаточность доказана.

Необходимость. Пусть Г не является игрой с полной памятью для всех игроков. Тогда существуют игрок i, стратегия щ, инфор-

217

мационное множество A^eRel и, и две позиции х, yeXJ, такие, что xePoss и„ уфPoss и,. Пусть и', — стратегия игрока г, для которой

у £ Poss u'„ и со— соответствующая партия, проходящая через у в ситуации и'. Обозначим через ц, смешанную стратегию игрока /,

которая	предписывает с вероятностью	1/2 выбирать стратегию
и, либо	и,. Тогда Pulltl{y)-PuUi{co)=\j2	(здесь и'Ц/z,— ситуация,

в которой чистая стратегия и, заменена на смешанную /z,). Из условия у ф Poss и, следует, что путь со, реализующийся в ситуации и'\\и„ не проходит через у. Это означает, что существует Хк такое, что Хк[)со = Хк[)соФ0 и u,(Arf)^u,(Arf). Отсюда, в частности, следу­ ет A"feRel u„ Хк eRel и,. Пусть /?, — стратегия поведения, соответст­ вующая ц,. Тогда b(Xk, M,(Arf)) = l/2. He ограничивая общности, можно считать, что и,(Х'^фщ{X1,). Тогда Ъ(Х\, м,(Х§) = 1/2. Обозна­ чим через /? ситуацию в стратегиях поведения, соответствующую ситуации в смешанных стратегиях и'\\ц,. Тогда -РДсо)<1/4, в то время как PU|ft(co)= 1/2. Теорема доказана.

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

§ 9. ФУНКЦИОНАЛЬНЫЕ УРАВНЕНИЯ ДЛЯ ОДНОВРЕМЕННЫХ МНОГОШАГОВЫХ ИГР

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

а)

5}

Рис.28

218

вые игры. Выведем функциональное уравнение для значения таких игр и рассмотрим несколько широко известных [5, 11] примеров, где эти уравнения поддаются решению.

9.1. Содержательно одновременная многошаговая игра пред­ ставляет собой антагонистическую многошаговую игру, в которой на каждом шаге игры игроки 1 и 2 выбирают свои действия одно­ временно, т. е. не имея информации о выборе противником позиции в этот момент. После того как выборы сделаны, они становятся известными обоим игрокам, и игроки вновь совершают одновре­ менный выбор и т. д.

Условно такую игру будем изображать с помощью графа, име­ ющего одно из двух представлений (рис. 28, а, б). Граф изображает поочередную игру с четным числом ходов, в которой информацион­ ные множества игрока, совершающего первый ход, являются одно­ элементными, а информационные множества другого игрока двух­ элементными. В такой игре Г оба игрока обладают полной памя­ тью, поэтому в ней согласно теореме п. 8.8 при отыскании ситуации равновесия можно ограничиться классом стратегий поведения.

Пусть, для определенности, в Г первым ходит игрок 1. С каж­ дым xeXi связывается подыгра Гх с той же информационной

структурой, что и игра Г. Нормальная форма любой антагонисти­ ческой конечно-шаговой игры с неполной информацией представля­ ет собой матричную игру, т. е. антагонистическую игру с конечным числом стратегий, поэтому во всех подыграх Гх, хвХ^ (включая

игру Г=ГХо) существует ситуация равновесия в классе смешанных

стратегий. Согласно теореме п. 8.8 такая ситуация равновесия суще­ ствует и в классе стратегий поведения и значения игры (т. е. значения функции выигрыша в ситуации равновесия в классе сме­ шанных стратегий и в классе стратегий поведения) равны между собой.

Обозначим значение игры Гх через v(x), хеХ1 и составим

функциональные уравнения для v(x).

Для каждого xeXt следующая позиция х1, в которой ходит игрок 1 (если таковая вообще существует), принадлежит множеству Fx. Позиция х' реализуется в результате двух последовательных выборов: игроком 1 — дуги, инцидентной к вершине х, и игроком 2 — дуги в позициях yeFx, образующих информационные множест­ ва игрока 2. Поэтому можно считать, что позиция х? получается в результате отображения Тх, зависящего от выборов а, /} игроков

2 и 2, т. е.

х'=ГДсс,/?).

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

219