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

Подождите немного. Документ загружается.

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

(1,1) (1,2) (2,1) (2,2)

1Г1 3 7 9]

2|_5 6 1 7J

Значение игры равно 17/5, и оптимальные смешанные стратегии

игроков 1 и 2 соответственно равны (2/5, 3/5), (3/5, 0,2/5,0).

Заметим, что в многошаговых играх с полной информацией (см.

теорему п. 2.1) существует ситуация равновесия по Нэшу в классе

чистых стратегий, а в случае антагонистических многошаговых

игр — просто ситуация равновесия в чистых стратегиях. Вместе

с тем во всех играх с неполной информацией, рассмотренных в при-

мерах 7 — 10, ситуации равновесия в чистых стратегиях не суще-

ствует.

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

ционной игры.

Определение.

Многошаговая позиционная

игра п лиц Г

опреде-

ляется:

Заданием древовидного

графа G={X, F) с

начальной вершиной

называемой начальной позицией

игры.

Разбиением множества

всех

вершин

X нап

+ 1 множество

X,,

, ....

Х„,

п+1

, где

множество

называется множеством

очеред-

ности

i-го

игрока

i=\, ..., п, а

множество

X„

{x:F

=0}

—мно-

жеством окончательных

позиций.

3) Заданием вектор-функции

K(x) = (K

(x),...,

К„(х)) на

множест-

ве

окончательных позиций

xeX„

i; функция K

(x)

называется

выиг-

рышем

i-го

игрока.

Подразбиением каждого множества Х„

i=l, ..., п,

на

непересе-

кающиеся подмножества

Х{,

называемые информационными

множе-

ствами

i-го

игрока.

При этом для любых

позиций одного

и того оке

информационного множества множество следующих за ними вершин

должно

содержать

одно и то же число

вершин,

т. е. для любых

х,

уе Х{:

—

(\F

—

число элементов множества

никакая

вершина информационного множества

не

должна следовать

за

неко-

торой другой вершиной этого оке

множества,

т. е.

если

хеХ\, то не

существует другой вершины

уеХ{

такой,

что

yeF

(см. п. 1.2).

Определение многошаговой игры с полной информацией (см. п.

1.4) отличается от приведенного здесь лишь условием 4, где вводят-

ся дополнительные разбиения множеств очередности игроков X

на

информационные множества. Как видно из примеров, содержатель-

ный смысл такого разбиения заключается в том, что при соверше-

нии своего хода в позиции хеХ, игрок /' в условиях неполной

210

информации не знает самой позиции х, а знает лишь, что эта

позиция находится в некотором множестве X

,c:X,(xeX{). На ин-

формационные множества игрока условие 4 накладывает опреде-

ленные ограничения. Требование 1^1 =

1^1

для любых двух вершин

одного информационного множества вводится для того, чтобы

вершины х, уеХ

}

, были неразличимы. Действительно, при

\F^

игрок г мог бы различить между собой вершины х, уеХ\ по числу

выходящих из них дуг. Если бы в одном информагшонном множест-

ве существовали две такие вершины х, у, что

yeF

то это означало

бы,

что партия игры может пересекать дважды одно информацион-

ное множество, а это, в свою очередь, равносильно тому, что игрок

i не помнит номера своего хода в данной партии, что трудно

иредставимо в реальной игре.

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

Продолжим исследование многошаговой игры с неполной ин-

формацией и покажем, что в случае полной памяти у всех игроков

она имеет ситуацию равновесия в стратегиях поведения.

8.1.

Для дальнейшего исследования необходимо ввести ряд до-

полнительных понятий.

Определение. Альтернативами в вершине хеХ называются

дуги, инцидентные с х, т. е. {(х, y):yeF

Если

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

считать, что если в вершине х имеется к альтернатив, то они

нумеруются целыми числами 1, ..., к, причем вершина х обходится

по часовой стрелке. В вершине х

первая альтернатива может быть

указана произвольно. Если некоторая вершина хфх

обходится по

часовой стрелке, то первой альтернативой в х считается та, которая

следует за единственной дугой (F~

, х), входящей в х (рис. 27).

Будем считать, что в игре Г все альтернативы перенумерованы

указанным способом. Пусть А

— множество всех вершин хеХ,

имеющих ровно к альтернатив, т. е.

={х:Щ

к}. Пусть l

{X\:X\<z

X,}

— множество всех информа-

ционных множеств игрока i. Под чи-

стой стратегией игрока i будем пони-

мать функцию и„ отображающую

/, в множество положительных чисел,

так что иХХ^^к, если

Х\<^А

Будем

говорить, что стратегия и, выбирает

Рис 27

211

альтернативу

/ в

позиции

xeX

если щ(Х§=1,

где /

— номер аль-

тернативы.

Так

же как это

было сделано

в п. 1.4,

можно показать,

что

каждой ситуации

и()

(и

(),

...,

и„()) единственным образом соот-

ветствует партия

со,

следовательно,

выигрыш

окончательной

позиции этой партии.

Пусть xeX„

i — некоторая окончательная позиция

со

— един-

ственный путь (F

—

дерево), ведущий из

в х.

Условие принадлеж-

ности позиции

пути

со

будем записывать

виде у в

со

или

у<х.

Определение. Позиция

хеХ

называется возможной

для

«,(•),

если

существует ситуация

м(),

содержащая

щ(),

такая, что

си-

туации и

(•)

реализуется путь

со,

который содержит позицию

х,

т.

е.

хесо.

Информационное

множество

Х{

называется существенным

для И/(),

если некоторая позиция

xeX

возможна

для

ы,().

Множество позиций, возможных для м

(

(), обозначим через Poss

«,(•),

семейство информационных множеств, существенных

для

«/(•),— через

Rel иД).

Лемма.

Позиция

хеХвозможна для м,()

тогда

только

тогда,

когда

«,(•)

выбирает

альтернативы,

лежащие

на

отрезке партии

со

от

до

во

всех своих

информационных

множествах,

пересека-

ющих

со

Доказательство. Пусть xePossu

(). Тогда существует ситу-

ация м(-), содержащая «,(•), такая,

что

партия

со,

реализовавшаяся

в этой ситуации, проходит через

х: а это и

означает,

что на

своих

информационных множествах, пересекающих отрезок партии

со

стратегия м,() выбирает альтернативы (дуги), принадлежащие

со

Пусть теперь

щ()

выбирает все альтернативы игрока i в

со

Для

того чтобы доказать возможность

х для

ы*(), необходимо постро-

ить ситуацию «(•), содержащую «,(•),

которой партия проходила

бы через

х. Для

игрока кФг построим стратегию

щ(),

которая

на

информационных множествах

Х{,

пересекающих отрезок пути со

выбирает альтернативы (дуги), лежащие

на

этом пути,

а в

оста-

льном произвольна. Поскольку каждое информационное множество

пересекает путь

со

лить однажды,

это

всегда можно сделать. В

по-

лученной ситуации

и(-)

партия

со

обязательно пройдет через

х.

Следовательно,

мы

показали,

что

xePossM,().

212

8.2. Смешанные стратегии в многошаговой игре с неполной

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

конечных игр.

Определение.

Смешанной стратегией

ц, игрока i называется

вероятностное распределение

на

множестве

чистых

стратегий

иг-

рока i,

которое каждой

его

чистой стратегии

() ставит в соот-

ветствие

вероятность

() (в

дальнейшем

для простоты будем

писать просто

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

распределение вероятностей на всех партиях

со

(следовательно, и на

окончательных позициях

Х„

)

по формуле

где Р

(со)

если партия

со

реализуется в ситуации и(), и Р„(со)=0

в противном случае.

Лемма.

Обозначим через

РДх)

вероятность реализации позиции

х в

ситуации

ц.

Тогда имеет место формула

ЗД= Е _Яи,..Чи„=й I Яи, (8.1)

{u():xePossuj(), /-1,и) /-1 {и<:дсеРов«к,}

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

леммы п. 8.1.

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

ц равно

£,(/х)

= £ Ъ(х)Р„(х), (8.2)

xeX

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

Определение.

Позиция

хеХназывается

возможной

для

/х„

если

существует ситуация

ц в

смешанных

стратегиях,

содержащая

такая,

что

РДл:)>0.

Информационное множество

Х\

игрока

назы-

вается

существенным

для ц

если

некоторое

хеХ{ является воз-

можным

для ц,.

Множество возможных для /*, позиций обозначим через

Poss

а множество существенных для

и,

информационных множеств — че-

рез Rel/i,.

8.3.

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

213

(см.

3.3), мы показали, что выбор стратегии может осуществляться

на каждом шаге в соответствующей позиции игры, а при решении

конкретных задач необязательно (да и практически невозможно)

определять заранее стратегию, т. е. полный набор рекомендуемого

поведения во всех позициях (информационных множествах), по-

скольку такое правило (см. пример п. 2.2) «страдает сильной избы-

точностью». Можно ли сделать аналогичное упрощение в играх

с неполной информацией, т. е. строить стратегию не как заранее

фиксированное правило выбора во всех информационных множест-

вах, а формировать ее по мере попадания в соответствующее ин-

формационное множество? Оказывается, что в общем случае этого

сделать нельзя. Однако существует класс игр с неполной инфор-

мацией, где такое упрощение возможно. Введем понятие стратегии

поведения.

Определение. Под

стратегией

поведения ft, игрока i будем

понимать

правило,

которое каждому информационному множеству

Х\сА

игрока i ставит в соответствие систему из к чисел

b(X

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

2>(nv) = l,

где A

={x:\F

k).

Числа b(X{,

могут интерпретироваться как вероятности выбо-

ра альтернативы v в информационном множестве X{czA

, каждая

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

Любой набор P=(fi

...,

Р„)

стратегий поведения для л игроков

определяет вероятностное распределение на партиях игры и окон-

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

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

X'fp+0

уеш

Здесь произведение берется по всем Х\ и v таким, что Х{(~]соФ0,

и выбор в точке

Х{

(~)со

альтернативы с номером

приводит в пози-

цию,

принадлежащую пути

со.

В дальнейшем под понятием «путь» удобно подразумевать не

только набор составляющих его позиций, но и набор соответству-

ющих альтернатив (дуг).

Ожидаемый выигрыш E,(fi) в ситуации fi = (fi

...,

/?,,)

в стратеги-

ях поведения определяется как математическое ожидание

£,(/?)= £ ВДРДсоД 1=1 и,

где

со

— партия, завершающаяся позицией

хеХ

п+1

214

8.4. Каждой смешанной стратегии

ц,

можно сопоставить некото-

рую стратегию поведения

Р,.

Определение.

Стратегией поведения р„ соответствующей

сме-

шанной стратегии

n,=

} игрока

называется стратегия

поведе-

ния,

определенная следующим

образом.

Если

,eRelfi

то

Ъ{Х{,

v)={ч*,***чтУЪ-*)

(8-

I Чщ

Если AT^Relft, то на

множестве

Х\

стратегию

/?,

можно

опреде-

лить

произвольным,

отличным

от (8.4)

образом.

{В случае Af-^Rel

Hi знаменатель

выражении

(8.4)

обращается

нуль.)

Для

определен-

ности будем полагать

ЫХ{,у)= X 9и, (8.5)

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

Лемма. Пусть

/?,

—

стратегия поведения игрока

i, a #=

{?«<,}

—

смешанная

стратегия,

определяемая формулой

Тогда p

—

стратегия

поведения,

соответствующая

/*,.

8.5. Определение. Игра Г

называется игрой

полной памятью

для i-го игрока, если для любых

(-),

X\, x из условий AT{eRel

ы<

и xeX

следует,

что jcePossw,.

Из определения следует, что в игре с полной

памятью

для i-го

игрока

любая позиция из существенного для ы,() информационного

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

подчеркивает то обстоятельство, что, очутившись в любом своем

информационном множестве, i-й игрок может точно восстановить,

какие альтернативы (т. е. номера) он выбирал во всех своих

пре-

дыдущих ходах (в силу однозначного соответствия). Игра с полной

памятью для всех игроков превращается в игру с полной инфор-

мацией, если все ее информационные множества содержат по одной

вершине.

8.6. Лемма. Пусть Г —

игра с полной памятью

для всех

игроков;

со

—

некоторая партия

в Г. Пусть

xeX

—

последняя позиция

в пу-

ти

со,

которой

ходит игрок i, и пусть он

выбирает

в х дугу

veco.

215

Положим

(o))={u

eRdu„u,(X])

v}.

Если в

со

нет

позиций

из Х„ то через

{co)

обозначим множество

всех

чистых стратегий игрока

Тогда партия со реализуется

в тех

только

тех

ситуациях

и{) =

{и

{-),

••-,

и„{)),

для

которых

и,еТ

(

{со).

Доказательство. Достаточность. Достаточно доказать,

что если и,е

Т,{со),

то стратегия

и,

выбирает все дуги (альтернативы)

игрока

входящие в партию

со

(если, конечно, игрок / вообще имеет

ход в

со).

Однако если

ы,е

{co),

то .Y^eRel

щ,

и так как игра Г имеет

полную память, то хе Poss щ (хеш). Значит, согласно лемме п. 8.1,

стратегия

выбирает все альтернативы игрока г, входящие в пар-

тию

со.

Необходимость. Предположим, что партия со реализуется

в ситуации «(•), у которой и,фТ{со) для некоторого i. Поскольку

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

со

не реализует-

ся.

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

8.7. Лемма.

Пусть

Г —

игра с полной памятью

для всех

игроков.

Пусть

—

альтернатива {дуга)

партии

со,

инцидентная

xeX

где

хесо,

позиция игрока i

{если

она

существует)

в пути

со есть

уеХ,.

Рассмотрим множества

S и Т, где

S={u

:XieR

,u,{Xi)=v},

T={u,:X'!eRelu

Тогда

S=T.

Доказательство. Путь u,eS. Тогда A^eRel u

и так как Г име-

ет полную память, то xePoss u

. Следовательно, по лемме п. 8.1

стратегия

выбирает все дуги, инцидентные к позициям игрока

на

пути от х

до х и u

i)=v. Таким образом щ выбирает все дуги,

инцидентные к позициям игрока i на пути от х

до у, т. е.

Poss u

eRel

и ы,е Т.

Пусть ы

(

еТ. Тогда .У*eRel

щ,

и так как Г имеет полную память,

то j>ePoss щ. Однако это означает, что xePossu, и u

{X^)=v, т. е.

u,eS. Лемма доказана.

8.8. Теорема. Пусть Р —

ситуация

в стратегиях поведения,

соответствующая ситуации

смешанных стратегиях

ц в игре Г {в

которой все позиции имеют по крайней мере две

альтернативы).

216

Тогда

для того

чтобы

E,(P)=E,(n),i=U:.,n,

необходимо

достаточно,

чтобы

была игрой

полной

памятью

для всех

игроков.

Доказательство. Достаточность. Пусть

— игра с полной

памятью для всех игроков. Фиксируем произвольное ц. Достаточно

показать, что

Рр(со)=Р

(со)

для всех партий

со.

Если

со

существует

позиция игрока

принадлежащая несущественному

для ц

(

инфор-

мационному множеству,

то

найдется X

,eRelfi

Х{[\саФ0, такое,

что

для

стратегии поведения /?,, соответствующей

выполняется

равенство

b(X

]

v)=0,

где

veto. Отсюда имеем РД<») = 0. Справед-

ливость соотношения Р

(ш)=0

этом случае очевидна.

Будем теперь считать,

что все

информационные множества

1-го

игрока, через которые проходит партия

со,

существенны

для

2, ...,

и. Пусть игрок

i в

партии

со

ходит

по

порядку

пози-

циях, принадлежащих множествам

Х\,.... Х\,

и выбирает в множест-

ве

Х{

альтернативу

Vj,

j=\, ..., s.

Тогда согласно формуле

(8.4)

и лемме п.

8.7

имеем

Ub(Xivj)=

£ q

J-l И(бГ,(ш)

Действительно, поскольку

партии

со

игрок

свой

1-й

ход делает из

множества

X), оно

является существенным

для

всех м<(-), поэтому

знаменатель

формуле

(8.4) для b(X\, Vj)

равен единице. Далее

в силу леммы

п. 8.7 в

формулах

(8.4)

числитель

Ь(Х{, у,)

равен

знаменателю

Ь(Х{

J+1

),j=l,

...,

Согласно формуле

(8.3)

окон-

чательно получим

«-1 u,eTt(fo)

где

Т,(со)

определено

лемме п.

8.6.

то

же время

на

основании леммы п.

8.6

Р,Н

Ев..,-9чЛ(а»)=

.4m.

"О

щеЩа)

т.

е.

(со)=Р^(ю),

достаточность доказана.

Необходимость. Пусть

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

для всех игроков. Тогда существуют игрок

стратегия щ, инфор-

217

мационное множество A^eRel и, и две позиции х,

yeX

такие, что

xePoss и„ уфPoss и,. Пусть

и',

— стратегия игрока г, для которой

у £

Poss u'„ и со— соответствующая партия, проходящая через

у в ситуации и'. Обозначим через ц, смешанную стратегию игрока /,

которая предписывает с вероятностью 1/2 выбирать стратегию

и, либо и,. Тогда P

ulltl

{y)-P

uUi

{co)=\j2 (здесь и'Ц/z,— ситуация,

в которой чистая стратегия и, заменена на смешанную /z,). Из

условия у

Poss и, следует, что путь

со,

реализующийся в ситуации

и'\\и„ не проходит через у. Это означает, что существует Х

такое,

что Х

[)со

[)соФ0 и u,(A

f)^u,(A

f). Отсюда, в частности, следу-

ет A"feRel

u„

eRel

и,.

Пусть

/?,

— стратегия поведения, соответст-

вующая ц,. Тогда b(X

, M,(A

f)) = l/2. He ограничивая общности,

можно считать, что и,(Х'^фщ{X

,). Тогда Ъ(Х\, м,(Х§) = 1/2. Обозна-

чим через /? ситуацию в стратегиях поведения, соответствующую

ситуации в смешанных стратегиях и'\\ц,. Тогда -РДсо)<1/4, в то

время как P

(co)= 1/2. Теорема доказана.

Из теоремы п. 8.8, в частности, следует, что для нахождения

ситуации равновесия в играх с полной памятью достаточно ограни-

читься классом стратегий поведения.

§ 9. ФУНКЦИОНАЛЬНЫЕ УРАВНЕНИЯ

ДЛЯ ОДНОВРЕМЕННЫХ МНОГОШАГОВЫХ ИГР

Теорема о стратегиях поведения, доказанная в предыдущем

параграфе, в общем случае не дает возможности непосредственно

решать многошаговые игры с полной памятью, однако при простой

структуре информационных множеств она обосновывает вывод фу-

нкциональных уравнений для значения игры и основанные на этих

уравнениях методы нахождения оптимальных стратегий. Наиболее

простыми играми с полной памятью, не считая игр с полной

информацией, являются так называемые одновременные многошаго-

а) 5}

Рис.28

218

вые

игры.

Выведем функциональное уравнение для значения таких

игр и рассмотрим несколько широко известных

[5,

11]

примеров, где

эти уравнения поддаются решению.

9.1.

Содержательно одновременная многошаговая игра пред-

ставляет собой антагонистическую многошаговую игру, в которой

на каждом шаге игры игроки 1 и 2 выбирают свои действия одно-

временно, т. е. не имея информации о выборе противником позиции

в этот момент. После того как выборы сделаны, они становятся

известными обоим игрокам, и игроки вновь совершают одновре-

менный выбор и т. д.

Условно такую игру будем изображать с помощью графа, име-

ющего одно из двух представлений (рис. 28, а, б). Граф изображает

поочередную игру с четным числом

ходов,

в которой информацион-

ные множества игрока, совершающего первый ход, являются одно-

элементными, а информационные множества другого игрока двух-

элементными. В такой игре Г оба игрока обладают полной памя-

тью,

поэтому в ней согласно теореме п. 8.8 при отыскании ситуации

равновесия можно ограничиться классом стратегий поведения.

Пусть, для определенности, в Г первым ходит игрок 1. С каж-

дым xeXi связывается подыгра Г

с той же информационной

структурой, что и игра Г. Нормальная форма любой антагонисти-

ческой конечно-шаговой игры с неполной информацией представля-

ет собой матричную игру, т. е. антагонистическую игру с конечным

числом стратегий, поэтому во всех подыграх Г

, хвХ^ (включая

игру Г=Г

Хо

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

стратегий. Согласно теореме п. 8.8 такая ситуация равновесия суще-

ствует и в классе стратегий поведения и значения игры (т. е.

значения функции выигрыша в ситуации равновесия в классе сме-

шанных стратегий и в классе стратегий поведения) равны между

собой.

Обозначим значение игры Г

через v(x), хеХ

и составим

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

Для каждого

xeX

следующая позиция х

, в которой ходит

игрок 1 (если таковая вообще существует), принадлежит множеству

. Позиция х' реализуется в результате двух последовательных

выборов: игроком 1 — дуги, инцидентной к вершине х, и игроком

2 — дуги в позициях

yeF

образующих информационные множест-

ва игрока 2. Поэтому можно считать, что позиция

х?

получается

в результате отображения Т

, зависящего от выборов а,

игроков

2 и 2, т. е.

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

Так как число различных альтернатив а и Р конечно, то можно

рассмотреть для каждого

xeX

матричную игру с матрицей выиг-

219