Лекция 15. Совершенные равновесия для нор­мальной формы

Дрожащая рука. Как предыдущие понятия и идеи реализовать для игр в нормальной форме? Понятие секвенциального равновесия подсказывает, что искомое равновесие должно получаться как предел невырожденных "почти-равновесных" ситуаций.

Почему невырожденных? Здесь обычно рассказывают сказку про дрожа­щую руку. Что любой игрок может совершить ошибку и с малой вероятно­стью отклониться от равновесия. И мы интересуемся равновесиями, которые устойчивы к таким малым отклонениям.

Поясним это на примере. Рассмотрим игру

 

tl

t2

si

10,0

м

s2

10,10

0,10

Профиль (s2,£l) равновесен; 1-й счастлив со стратегией s2, пока 2-й не ис­пользует t2 (заметим, правда, что это равновесие вовлекает слабо доминируе­мую стратегию s2). Но представим, что (например, из-за случайной ошибки) второй игрок использует стратегию t2. Тогда s2 становится неоптимальной, и игрок 1 довольно резко переключается на si. А тогда и 2-й переключает­ся на t2. И они сваливаются в равновесие (si, £2) (с худшими, надо сказать, выигрышами).

Эта идея формализуется следующим образом (Селтен, 1975):

Определение. (Смешанный) профиль стратегий а\- = (а;) называется совершенным (относительно дрожащей руки) равновесием, если существует последовательность (<Тдг, п = 1,2,...) вполне смешанных стратегий, которая сходится к (Ту. и такая, что для каждого игрока inn стратегия а; есть наи­лучший ответ на профиль сг'!_-г

Смешанная стратегия а £ Д(<%) называется вполне смешанной, если она принадлежит внутренности симплекса Д(5^), то есть с ненулевыми вероят­ностями использует все чистые стратегии.

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

Предложение. Каждое совершенное равновесие является равновесием Нэша. □

Довольно очевидно, что слабо доминируемые стратегии не входят в совер­шенное равновесие. Крепе считает отсутствие слабо доминируемых стратегий в равновесии важной чертой "хорошего", очищенного равновесия.

Существование совершенных равновесий.

Теорема. Для любой конечной игры существует совершенное равновесие.

Доказательство. Обозначим для "большого" числа к через Ак симплекс в Д чуть мень­шего размера (когда все координаты > 1/к). Ограничим нашу (смешанную) игру на эти симплексы и обозначим получившуюся игру Ск. У нее, конечно, есть равновесия, которые мы обозначим а%. В силу компактности можно считать, что ок сходятся (при к —У оо) к некоторым стратегиям 0{ е А(Б{). Мы хотим показать, что для любого игрока г страте­гия 0{ будет наилучшим ответом на ок_^ при всех (достаточно больших) к. Тогда то мы

ПОЛуЧИМ Совершенное равновесие Одт.

Сразу этого утверждать нельзя. Однако в силу конечности числа граней у симплекса можно выбрать подпоследовательность к, такую что о\ лежат на "одной и той же" грани симплекса Л;'* (>',)• Ясно, что предельная стратегия <т,- тоже лежит на "той же" грани Л (>'(). Покажем теперь, что стратегия п, будет наилучшим ответом на ок_^. Для этого напомним, что функции полезности а^) аффинны, и если они достигают максимума в некоторой точке ак, то они принимают те же максимальные значения во всех вершинах этой грани Ак(Б^. Но эта грань параллельна соответствующей грани А(Б^. Значит функция £т^г) принимает максимальные значения на той же грани симплекса Л (>'(). и в частности, <т,- -наилучший ответ на ок_^. □

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

Лемма. Пусть а - совершенное равновесие в С Тогда существует такой вектор вер [л, что (а, /л) - секвенциальное равновесие в Г.

Идея доказательства. По определению совершенного равновесия существует последо­вательность £Тдг стратегий (в С или Г), которые сходятся к ам, которые невырождены ит.п. В силу невырожденности о"|г можно однозначно определить набор вер fj,k, согласу­ющихся с а%. Остается устремить li^ в пределу /л. Так как стратегия Oi игрока г была наилучшим ответом на ок_^, она будет оптимальным ответом при системе вер /л^, и при их пределе /л. □

Следствие. Пусть Г - конечная игра с совершенной памятью. Тогда в ней существу­ют сильные секвенциальные равновесия. □