Лекция 14. Секвенциальные равновесия

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

+ 0,2

и

 

1,1

0,-1   -1,0 -1,-1

По существу, это та же игра, однако теперь в ней нет собственных подыгр. Рассмотрим еще один пример (Селтен (1975)):

(3,3,0)

 

1  у /

(4,4,4) (1,1,1) (5,5,0) (2,2,2)

В ней имеется равновесие (I), а, V). Это равновесие совершенно, но только потому, что здесь нет собственных подыгр. Однако выбор вторым игроком стратегии а странен. Ведь если он уверен, что 3-й будет использовать Ь7 то ему надо было бы выбрать о1. Пусть даже шанс сделать ход для 2-го ничтожен, но о1 лучше а\ И если он выберет о17 то 1-й переключится на Л, а тогда 3-й переключится на Я. Но тогда 2-й вернется к а, 1-й останется на А, и это дает второе равновесие (А, а, Я).

Здесь нет подыгр, и буква определения молчит, но дух совершенства тре­бует определенно и ясно: игрок в любой позиции должен действовать оп­тималъно, даже если маловероятно, что удастся попасть в эту позицию. Как же придать этому смысл?

Рациональность и веры. Нужно ясно понимать, в чем заключается пре­пятствие к понятию оптимального поведения в некоторой позиции. Мы уже отмечали, что выигрыш игрока г (контролирующего ход в позиции х) зависит от стратегий остальных. Но не это препятствие, потому что в духе равнове­сия Нэша тут предполагается, что стратегии всех остальных игроков фикси­рованы и известны. Главное препятствие в том, что выбор хода в позиции х автоматически меняет ход и во всех позициях из информационного множе­ства Н(х). А значит и выигрыши на тех путях игры, которые проходят через другие позиции х' £ Н(х). Поэтому мы не можем просто начать "подыгру" с позиции ж, нужно начинать ее из информационного множества к.

Теперь основная неопределенность нашего игрока г заключается в том, в какой из позиций в // находится игра. Тут ничего не поделаешь, для разре­шения этой неопределенности нужно задаваться "верой" на Н. То есть игрок г должен задаться некоторой вероятностной мерой //(/г) £ А(К). Как только такая вера задана, то можно образовывать ожидаемые выигрыши (в зависи­мости, скажем, от хода в К) и оценивать оптимальность используемого хода в Н.

Заметим, что информационные множества других игроков могут "пере­секать" нашу "подыгру" С (/г), начинающуюся из /г, но это нас не должно волновать: ведь стратегии таких игроков фиксированы. А вот если информа­ционные множества того же игрока г начнут вылезать из С (/г), это могло бы стать источником неприятностей. К счастью, для игр с совершенной памятью (см. Лекцию 4) такого произойти не может.

Одним словом, чтобы говорить об оптимальности в каждой позиции, нуж­но задаться не только стратегиями а. но и верами //. И эти данные - стратегии и веры - должны быть согласованы друг с другом. Мы скажем подробнее об этом чуть ниже, а пока заметим только, что и классическое равновесие Нэ­ша можно воспринимать в таком же духе. Предположим, что для каждого игрока г заданы стратегия £ Д(<%) и вера щ £ А(Б^); они образуют рав­новесие Нэша, если: а) - наилучший ответ при вере и б) каждая вера /// совпадает с :.;/;^;- Мы видим здесь согласование двоякого вида. Условия а) выражают рациональность каждого игрока при имеющихся верах. Усло­вия б) говорят о формировании вер - они в точности совпадают с тем, чтоделают остальные, можно сказать - истинные. В этом случае веры однознач­но восстанавливаются по стратегиям (других игроков, заметьте!), и поэтому их можно исключить из определения. Однако в принципе можно было бы вместо б) накладывать и менее жесткие условия, например, что носитель содержится в носителе     (или наоборот).

Слабое секвенциальное равновесие. Как уже было сказано, секвен­циальное равновесие состоит из данных двух типов - стратегий и вер. Бо­лее формально, профиль (поведенческих) стратегий образует семейство а = (сг/1,, к £ Н)7 где к пробегает множество Н информационных множеств на­шей развернутой игры, а 0}г £ А(М(/г)) (напомним, что М(к) - множество ходов или акций, доступных в информационном множестве К). Системой вер называется семейство \х = (//(/г), к £ Я), где р(к) £ Д(/г).

Чтобы быть секвенциальным равновесием, пара (<т, р) должна удовлетво­рять двум условиям вроде а) и б). Первое условие требует рациональность поведения каждого игрока в каждом "своем" информационном множестве. Предположим, что дано информационное множество /го, контролируемое иг­роком го, и некоторая вера ро £ Д(/го). Пусть также задан некоторый про­филь поведенческих стратегий а = (сгн)-

Определение. Скажем, что игрок го секвенциально рационален в инфо-мационном множестве ко при вере //о, если, при фиксированных стратеги­ях остальных игроков, ожидаемый при вере ро выигрыш игрока го в поды-гре С (/го), начинающейся в /го, достигает максимума именно на стратегии (с% к £ Щ).

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

Например, в игре "ослик Селтена" стратегический профиль (I), а, V) усло­вию рациональности в вершине 2 не удовлетворяет: если 2-й игрок считает, что 3-й играет     то он выберет о17 а не а.

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

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

Такой набор (<т, ц) называется слабым секвенциальным равновесием. По существу это понятие (в сильном варианте) было введено Крепсом и Уилсо-ном в 1982 г. Отметим, что условие на веру р(к) в информационном множе­стве к накладывают только смешанные ходы в множествах Ы, располо­женных ранее к.

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

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

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

Так мы получаем следующее утверждение (более подробное доказатель­ство можно найти у Майерсона или у Масколея и др., Предложение 9.С.1):

Теорема. Профиль поведенческих стратегии а является равновесием Нэша т. и т.т., когда найдется такая система вер р, что (г) система р слабо согласована с профилем а;

 (п) профиль а секвенциально рационален (при верах ц) во всех информа­ционных множествах, лежащих на пути игры.

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

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

 

И пусть первый играет и. Каковы могут быть веры у 2-го? Так как 1-й не различа­ет эти состояния (правое и левое), он и отклоняться в них должен одинаково. Поэтому естественно считать, что веры 2-го - это .2 и .8.

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

Определение. Система вер /л называется сильно согласованной с профилем стратегий а, если существует последовательность вполне смешанных стратегических профилей ап, такая что ап сходится к а, а соответствующие веры /лп = /л(ап) сходятся к /л.

Секвенциальное равновесие - это пара (а, /л), что /л сильно согласована с а, а а секвен­циально рациональна относительно /л.

Следующий пример демонстрирует слабое секвенциальное равновесие, которое не силь­ное секвенциальное.

 (0,0,0)

■о

 

2

о-

(1Д,2)

 

3

 

(0,0,0) (0,0,1)

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

Пусть третий игрок верит, что реализуется левая вершина в его информационном мно­жестве. Такая вера вместе со стратегиями (К, А, г) является слабым секвенциальным рав­новесием. Однако оно не является сильным секвенциальным равновесием, потому что вера третьего, сильно согласованная со стратегиями К и А, указывает на правую вершину в информационном множестве 3. Сильным секвенциальным равновесием (единственным?) здесь будет (/7. /). /).

Теорема. Любая конечная, игра, (в развернутой форме и с совершенной памятью) имеет сильное секвенциальное равновесия.

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

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