Лекция 11. Равновесия Нэша в смешанных стра­тегиях

Рандомизированные стратегии. Классическое применение теоремы Нэ­ша относится к существованию равновесий в смешанных расширениях, или смешанных стратегиях. Как уже говорилось, многие игры не имеют равно­весия (в чистых стратегиях). Рассмотрим игру

Знание игроком 1 хода игрока 2 позволяет ему добиться преимущества и по­лучать выигрыш. Значит 2-му (как и первому) нужно скрыть свои намерения. Но где взять гарантии, что ваш противник не узнает ваш ход?

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

Формально это означает, что игрок от множества "чистых" стратегий 5^ переходит к множеству "смешанных" стратегий А(5^). Выигрыши определя­ются с помощью ожидаемой полезности. Собственно, здесь впервые становят­ся важными численные значения выигрышей, а не соответствующие предпо­чтения. Переход от игры С = (]У, (щ)) к игре Ст = (]У, (Д (,%)), {Щ)) называется смешанным расширением. Мы уже говорили об этом в Лекции 4.

Смешанные равновесия. Так называются равновесия Нэша в смешан­ном расширении, или равновесия в рандомизированных стратегиях. Вообще, полезно сравнить исходную игру С с ее смешанным расширением Ст. Напри­мер, как изменятся щ и /%? Нас же интересуют равновесия Нэша. Положение дел с равновесиями проясняют следующие утверждения.

А) Лемма. Каждое равновесие в игре С является равновесием в сме­шанном расширении Ст.

В самом деле, пусть .%• д- - равновесие в 6?, т.е.

щ( *     *  \ "*>      (        * \для любой (чистой) стратегии игрока г. Нужно проверить, что то же будет для любой смешанной стратегии а^. Но

5^) = ^ 5^)сф0 < 5^) ^ = иг(вЬ ви)П

Б) Если профиль чистых стратегий вдг является равновесием в Ст, то в]у - равновесие в исходной игре СП

Эти два утверждения можно выразить одной формулой

= ЫЕ(Ст) П 5дг.

В) Могут появиться новые смешанные равновесия. Рассмотрим приведен­ную выше игру "орлянка", в которой нет чистых равновесий. В смешанных стратегиях равновесие есть: нужно первому использовать стратегию 0.5 ® б1 + 0.5 ® з2, а второму также с равными шансами замешивать И и VI.

Г) Принципиальным фактом является то, что в рандомизированых стра­тегиях равновесия всегда существуют.

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

В самом деле, стратегические множества Д(<%) игры Ст - выпуклые ком­пакты, а функции выигрыша Щ аффинны (значит вогнуты) по переменной а. и непрерывны. Значит применима предыдущая теорема.□

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

зирр(сг) = {вг £ 5^ (ф») > 0}.

Более того, если (г,- - лучший ответ на а-;, то выигрыш при (г,- равен выигрышу при использовании любой чистой стратегии из носителя а^.

Это очень важное место! Оказывается, у игрока г (почти) нет никаких сти­мулов, чтобы выбирать именно равновесный набор вероятностей из 8ирр(сг*). Все стратегии из Д(зирр((Т*)) являются наилучшими ответами на сг*^. Это дает основания сомневаться в практической значимости смешанных равно­весий. Если в игре нет чистых равновесий, это обычно говорит о том, что задача плохо поставлена.

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

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

Если Мэри будет удваивать только при хорошей карте, это будет явным сигналом для Джона, что у нее хорошая карта, и он будет пасовать. В ре­зультате при хорошей карте Мэри выигрывает 1, а при плохой - проигрывает 1 (в среднем). Для получения более лучшего результата ей нужно блефовать, т.е. удваивать иногда и при плохой карте. Как часто - об этом и говорит смешанное равновесие.

Видимо, смешанные равновесия представляют интерес только в подобных многократно повторяющихся играх.

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

1) Первое из них - все то же исключение доминируемых стратегий. Иногда полезно использовать симметрию.

2) Второе связано в перебором вариантов. Множество тех чистых стра­тегий, которые входят с ненулевой вероятностью в равновесные стратегии (т.е. носитель), есть важный качественный аспект равновесия. Для нахожде­ния равновесий можно для начала перебирать все подмножества Di С Si и для каждого пытаться решить соответствующую систему равенств (и нера­венств), приравнивая выигрыши некоторому (искомому) значению ш^. Более подробно, для каждого г мы имеем следующую систему равенствдля любых    у Е 1), и условия

вирр^) С А

(плюс, конечно, неравенства Щ(х,а^) > Щ(г,а^) для л ^ 1^). Каждое г дает I), — 1 уравнение, так что уравнений столько же, сколько неизвестных. Получаются в общем случае нелинейные уравнения. Тем не менее в общем случае у них конечное число решений.

Конечно, для больших игр такой алгоритм работает плохо.

3) Положение чуть упрощается, если всего два игрока. Тогда приведенные выше уравнения (и неравенства) являются линейными. При этом если П% ф 1)2? то (снова в общем случае) решений нет. В самом деле, если П% > 1?2, то мы получаем подсистему из 1)\ уравнений с !)■> неизвестными.

4) Пусть снова два игрока, причем у второго всего две стратегии - t и V'. Смешанная стратегия второго - точка г на отрезке Тогда стратегии первого можно изображать как аффинные функции на этом отрезке, э^). Конечно, для любого г есть наилучший ответ в*(г), единственный в случае общего г. И если г, в свою очередь, является наилучшим ответом на в*(г), мы получаем равновесие (в общем случае такое может случиться только когда г = Ь или £'). Но в некоторых точках будет два (опять в общем случае) наилучших ответа первого игрока. Тогда нужно проверить это все на предмет наилучших ответов второго.