Лекция 12. Равновесия Нэша (окончание)

Например, в ситуации на рисунке есть два "подозрительных" значения г.

Особенно просто все, когда и у первого две стратегии. Тут надо рисо­вать трехзвенные зигзаги. Мулен разбивает общие такие игры на три класса. Первый - когда у кого-то есть доминирующая стратегия (нетипичный пред­ставитель - Дилемма Заключенных). Второй - когда нет чистых равновесий (это "орел-решка"). Тут появляется одно смешанное равновесие. Третий - ко­гда есть два чистых равновесия (типичный представитель - "семейный спор"). Кроме двух чистых, есть еще одно смешанное равновесие.

5) В случае антагонистической игры, если у одного (второго) игрока всего две стратегии, равновесия можно искать способом, приведенным в лекции 6.

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

Пример. У хозяина работает работник; он может работать хорошо (X) или сачковать (С). Хозяин может либо проверять его (П), либо нет (Н). Таблица выигрышей такова

 

X

С

п

10,2

4,0

н

10,2

4,3

В этой игре два равновесия, но, конечно, хозяину лучше проверять.

Представим теперь, что у хозяина два работника, но проверить он может только одного (а выигрыши для хозяина складываются). Тогда у него есть два равновесия: проверять первого работника (и тогда первый старается, а второй сачкует; выигрыш хозяина равен 14) или проверять второго. Но представим, что хозяин использует смешанную стратегию и с равными вероятностями проверяет того и другого. Как легко понять, в этом случае каждый работник будет стараться, и хозяин получит выигрыш 20.

Не противоречит ли этот пример сделанному выше замечанию, что смешанная страте­гия не может дать больше чистой?

Я думал закончить с равновесиями Нэша, но кое-какая мелочь осталась, и не хотелось бы бросать.

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

В любой игре сильно доминируемая стратегия не может входить в равно­весие по Нэшу. Иначе говоря, если «д- = (в^) £ ЛГЕ'(С), то для любого игрока г стратегия в* не строго доминируется. Это очевидно.

Второе замечание относится уже к смешанному расширению. Пусть О"1 -смешанное расширение (конечной) игры С Пусть и а[ - две (смешанные) стратегии игрока г. Как понимать что доминирует на чистых стратегиях остальных, или на любых смешанных? Очевидно, что все равно как.

Третье замечание. Если в смешанную стратегию входит с ненулевой ве­роятностью сильно доминируемая стратегия, то и смешанная сильно доми­нируется. В самом деле, пусть а = а ® в + (1 — си)т, а > О и стратегия в доминируется стратегией в' (можно даже смешанной). Тогда смешанная стратегия а' = а ® в' + (1 — а)т (сильно) доминирует стратегию а.

Собирая все вместе, мы получаем утверждение, обобщающее приведенный ранее факт: пусть множества Б[ содержатся б ^ и получены удалением сильно доминируемых стратегий. Тогда

ЫЕ(С'т) = ЫЕ(Ст).

Если же мы удаляем слабо доминируемые стратегии, то имеет место фор­мула

ЫЕ(С'т) = ЫЕ(Ст) П Ст.

Эффект фокальной точки. Как показывает игра "семейный спор", рав­новесий может быть много. Позже мы рассмотрим несколько утоньчений (ра­финирований) Нэша, но даже эти рафинации могут быть множественными.

Когда равновесий много, позиции теоретика становятся шаткими. Любое из равновесий, ожидаемое игроками, обладает самооправдывающим свой­ством. Что же могло бы заставить игроков имплементировать некоторое спе-циальное равновесие? Да любая вещь, заставляющая их фокусировать вни­мание именно на этом равновесии. Шеллинг в книге The Strategy of Conflict, Cambridge (1960), назвал это эффектом фокальной точки. Это любое свой­ство, выделяющее конкретное равновесие среди всех остальных. Им могут быть традиции, статус кво и т.п., то есть как правило, внемодельные вещи.

Фокальное равновесие может определяться и свойствами функций полез­ности. Рассмотрим игру - дележка долларов. Есть 100 долларов; каждый называет число от 0 до 100. Если сумма < 100, каждый получает что просил; иначе по нулям. Есть масса равновесий (например, (91,9) и даже (100,100)), но среди них есть и фокальное: (50, 50), т.к. каждый игрок понимает, что это эффективное и справедливое решение. Конечно, это не значит, что любой эффективный и справедливый исход может быть равновесием.

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

Бесконечные стратегии. До сих пор мы в основном рассматривали ко­нечные игры. Сделано это было главным образом для простоты, чтобы из­бежать математических усложнений. Теперь мы кратко рассмотрим случай, когда множества стратегий Si - метрические компакты. Грубо говоря, "все" результаты для конечных множеств остаются верными, когда условия конеч­ности заменяются на компактность.

Прежде всего, нам нужно перенести определение А(Х) с конечных мно­жеств x на метрические компакты. Наметим вкратце, как это сделать. Пер­вое: определим простые лотереи на x как конечные "выпуклые" комбинации J2i °~i ® xi > 0? Yl °~i = 1); множество простых лотерей обозначим Aq(X). Второе - перенесем на Aq(X) метрику р с x. Делается это так. Пусть ржу -две такие лотереи (или распределенные единичные массы). Расстояние между ними - это минимальная стоимость перевозки массы р в v\ стоимость берется в "тонно-километрах". Наконец, А(х) - это пополнение Ао(Х) в этой метри­ке. Мы автоматически получаем на А(Х) метрику (продолжающую метрику р на x и называемую продолжением Канторовича-Рубинштейна) и компакт­ность А(Х).

Мы утверждаем, что если все стратегические множества Si являются мет­рическими компактами (участников по-прежнему конечное число), а функ­ции выигрыша непрерывны на произведении (в топологии произведения), то существует (смешанное) равновесие Нэша.

Теорема (Гликсберг, 1952). Если стратегические множества ком­пактны, а полезности щ непрерывны, то существует равновесие Нэша в рандомизированных стратегиях.

Доказательство. Можно воспользоваться "бесконечномерным" обобщением теоремы Ка-кутани. Однако есть и более элементарный путь, который мы наметим в общих чертах. Он основан на конечной аппроксимации нашей (бесконечной) игры. Здесь полезно следующее понятие. Скажем, что ситуация      является е-равновесием, если для любого игрока г и

ЛЮбоЙ 8{

щ(в^ , ^ щ{8{) £.

Приступим к доказательству. Так как функции выигрыша и, непрерывные, они рав­номерно непрерывны, т.е. для любого е > 0 существует 6 > 0, что — < Е при р(8,з') < 6. Возьмем для каждого игрока г конечную 5-сеть С Si. Тогда можно рассмотреть конечную игру (М, (Х^, (щ\х{)) и в ней некоторое (смешанное) равновесие ам € Х{А(Х{). Конечно, этот профиль смешанных стратегий не обязан быть равновеси­ем в исходной игре (точнее, в ее смешанном расширении). Однако, как легко понять, ам является е-равновесием в (,'"'.

В самом деле, пусть <т,- - произвольная стратегия из А (>'(): мы утверждаем, что

Щ(<71, <Т_г) - Е < Щ(<71, <7_г). ЯСНО, ЧТО МЫ МОЖеМ СЧИТаТЬ 0{ ПРОСТОЙ СМеСЬЮ, ТО еСТЬ 0{ = X] а00300; гДе а0) ' ве"

са, а е Si. Если для каждой точки взять ближайшую к ней точку х(]) из Х^ и образовать о\ = ^о-(])х(]), то щ{<71,<7^) отличается от щ(а[, а^) менее чем на е. А щ(а[, а_г) < щ(аг,а-г) уже из определения равновесия.

Итак, для каждого : > 0 мы нашли е-равновесие. Остается устремить е к нулю и воспользоваться компактностью Л(,!?).□

Пример. Китайский покер. Чтобы вы не обольщались, приведу стандарт­ный пример бесконечной игры, где равновесий (даже смешанных) нет. Два игрока, каждый называет натуральное число; назвавший меньшее число пла­тит 1 рубль другому. Здесь множество Б чистых стратегий - М, конечно, это некомпактное множество. Ясно, что чистых равновесий здесь нет, и каждая стратегия (слабо) доминируется. Но в действительности нет и смешанных равновесий.

Отметим, что тут совершенно ясно, что считать смешанной стратегий, так что проблема не в этом. Смешанная стратегия а - это последовательность (сг(гг)) неотрицательных чисел, таких что ^2по~(п) = 1.

Почему же нет равновесий? Пусть ваш противник использует смешанную стратегию т. Ваша стратегия будет наилучшим ответом только тогда, когда носитель вашей стратегии а расположен выше носителя г; в противном слу­чае вы можете улучшить свой ожидаемый выигрыш. В самом деле, пусть ваш (ожидаемый) выигрыш равен 1-е, где е > 0. Возьмите целое число птакое что т(п) + т(п + 1) + ... < е/2 и примените чистую стратегию п. Ваш выигрыш в этом случае будет равен

т(1) + ... + т(п - 1) - т(п + 1) - ... ,

что строго больше, чем 1 — е/2 — е/2 = 1-е. Итак, если у вас есть наилучший ответ, то носитель вашей стратегии расположен выше носителя противника. Но тогда ваш противник использует не оптимальную стратегию. Так что рав­новесий нет.

Равновесия в разрывных играх В чем же дело? Что тут не подходит под теорему Гликсберга? Проще всего сказать, что множество N некомпактно. А если его компактифицировать? Тогда функции выигрыша будут разрывны.

Тем не менее даже в случае разрывных функций иногда бывают равнове­сия. Не претендуя на охват темы, рассмотрим один пример - "дикий" аукцион доллара, или "платят все". Есть п > 1 участников, они называют числа> 0. Назвавший наибольшее число получает доллар (считается, что ценность его для всех равна 1), и каждый (!) платит х\. Таким образом, выигрыш участ­ника (мы пренебрегаем связками) г равен

—х;.     если     < х*^ 1 —       если     > х*^ '

где х*^ = m&x(xjlj г). (Похожие функции выигрыша будут в олигополии Бертрана.) Довольно легко понять, что использовать числа > 1 смысла нет (хотя в реальных розыгрышах этой игры народ часто платил за доллар го­раздо больше доллара!), поэтому в качестве множества стратегий 5^ можно принять отрезок [0,1].

Ясно, что равновесий в чистых стратегиях нет. Однако смешанные рав­новесия существуют; приведем одно. Оно будет симметричным и более того, размазанным по всему отрезку [0,1]. Пусть Р(х) - функция распределения искомой смешанной стратегии (т.е. вероятность того, что х\ < х). Найдем ожидаемый выигрыш игрока г, когда он использует (чистую) стратегию х. Его выигрыш равен 1 — ж, если все остальные назвали числа, меньшие х (а вероятность этого равна Р(х)п^1), и равен —х в противном случае. Таким образом,

Ещ(х) = (1 - х)Р(х)п^ - х(1 - Р(х)п^1) = Р(х)п^ - х.

Игрок включает в свою равновесную стратегию те ж, которые дают ему мак­симум этой функции. По условию все х должны быть равновыгодными, т.е.все должны давать НУЛЕВОЙ ожидаемый выигрыш. Так мы получаем, что

.Р(ж)"'^1 = х, или .Р(ж) = х1^п~1\

Как легко посчитать, Ех\ = 1/п (грубо говоря, каждому игроку нужно называть примерно так что Е{^2цХ^) = 1 и устроитель аукциона в

среднем ничего не выигрывает! К сожалению (?), в жизни люди редко ведут себя в соответствии с этим правилом.