Академия: "Теория игр". Блок #3

Конспект курса лекций для Академии

• Конспект модуля №1. Стратегические взаимодействия
• Конспект модуля №2. Доминирующие и доминируемые стратегии

В этом блоке речь пойдёт об одной из самых важных концепций в решении игр — равновесии Нэша.

Конспект модуля №3. Равновесие Нэша

1. Определение равновесия Нэша

Равновесие Нэша — набор стратегий, в котором ни один из участников не в состоянии увеличить свой выигрыш, изменив свою стратегию, если другие участники не меняют своих стратегий (фиксированные). При условии, что все игроки рациональны, значит каждый выбирает ту стратегию, которая даст ему наибольший платёж. Такие предположения и называются равновесием Нэша. Если как минимум одному игроку выгодно отклониться от выбранной стратегии, то такой профиль не является равновесием Нэша. (Джон Форбс Нэш)

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

Поясним на знакомом нам примере "Битва полов":

• В прошлом блоке мы выяснили, что ни один из игроков не имеет доминирующей стратегии.
• Но есть профили стратегий, которые более выгодны, чем другие. Это профили футбол-футбол и балет-балет, при условии, что второму игроку будет известен выбор первого, то есть каждый из игроков играет свою оптимальную стратегию в ответ на стратегию другого игрока. Это равновесие Нэша.
• Оставшийся профили футбол-балет и балет-футбол, будут менее выгодны, так как в них другому игроку будет выгодно отклониться от выбранной стратегии, чтобы получить больший платёж. Это НЕ равновесие Нэша.

Формальная форма

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

2. Алгоритмы поиска равновесия Нэша

Строим матрицу игры:

• Для каждой стратегии игрока 2 пометим точками наилучшие ответы игрока 1.
• Для каждой стратегии игрока 1 пометим звёздочками наилучшие ответы игрока 2.
• Профили, одновременно помеченные точками и звёздочками являются равновесиями Нэша.
• Профили, где только звёздочка или только точка, не являются равновесиями Нэша.

Пример (конкуренция двух университетов)

Условия

• В городе есть два университета
• Выпускники будут конкурентами на рынке труда
• Работодатели будут их оценивать только по среднему балу
• Каждый университет будет завышать балы студентам для лучшей статистики среди этих университетов

Стратегии универститов

• Завышать балы студентам (З)
• Не завышать балы студентам (Н)

Матрица

Мы видим что ...

• Если оба университета выбирают одинаковые стратегии, то тогда их условия равны и платежи тоже.
• Если один университет завышает балы, а второй нет, тогда преимущество получают выпускники первого, а следовательно и сам университет увеличивает свой платёж.
• Это равновесие в доминирующих стратегиях (З)
• Это так же равновесие Нэша (ни одному игроку не выгодно отклоняться от своего решения (З)

3. Как связано равновесие Нэша и другие концепции

• Если игра имеет равновесие в строго доминирующих стратегиях, то оно всегда будет и равновесием Нэша. Так как каждый из игроков играет свою доминирующую стратегию и отклонившись, ни один из игроков не увеличит свой платеж при фиксированных стратегиях остальных.
• Если игра имеет равновесие в слабо доминирующих стратегиях, то оно всегда будет и равновесием Нэша, но в игре могут быть и другие равновесия Нэша.
• Если игра имеет равновесие, полученное исключением строго доминируемых стратегий, то оно всегда будет и равновесием Нэша без других.
• Само равновесие Нэша не обязательно является равновесием в доминирующих стратегиях или получаемым исключением таких стратегий.
• В игре все профили могут быть: всеми равновесиями Нэша или ни одного равновесия Нэша.

4. Примеры

Финансирование предвыборной компании
Условия

• В городе два кандидата соревнуются за кресло мэра
• Исход выборов зависит только от количества денег, который потратит больше средств, тот победит
• Если исход голосов 50/50, то они бросают монетку

Стратегии кандидатов

• Сколько средств привлечь?
• Один кандидат привлекает сумму C1, а второй C2

Платежи кандидатов

• Каждый хочет выиграть (платёж, 1)
• Чуть хуже набрать одинаковое кол-во голосов (платёж, 1/2)
• Проиграть выборы (платёж, 0)
• Каждый хочет потратить минимум средств, но победить

Ищем решение

• C1>C2 или победа первого. Но, это не будет оптимально, так как он мог потратить меньше, чем С1, но больше, чем C2. Ему выгоднее отклониться от этого профиля.

• C2>C1 то же самое, только для другого кандидата.

• C1=C2 или каждый победит при броске монетки с вероятностью 50/50. Но здесь тоже каждому выгоднее отклониться и сыграть другую стратегию, увеличить финансирование. Значит в игре нет равновесия Нэша.

В сумме 100
Условия

• В игре два игрока
• Каждый втайне пишет любое положительное число
• Если сумма этих чисел x+y ≤ 100, то каждый получает в платёж своё число
• Если сумма этих чисел x+y > 100, то у них ничья

Ищем равновесия

• х+у=100. Например (50; 50) или (20; 80). Если любой из них увеличит выбранное число, то сумма превысит 100, и никто из них не получит ничего, то есть никто не увеличивает свой платёж. Если кто-либо из них уменьшит выбранное число, то он так же не улучшает свой платёж. Равновесие Нэша.
• х+у<100. Тут каждому из них будет выгодно выбрать другую стратегию, увеличить своё число, чтобы их сумма не превысила 100. Не равновесие Нэша.
• х>100, y<100, x<100, y>100. Это не рационально, так как выбирать число <100 заведомо проигрышно. Выбор выгодно поменять. Не равновесие Нэша.
• x≥100. y≥100. Никому из игроков не выгодно выбрать другую стратегию, поскольку он не сделает сумму чисел ≤ 100. То есть, по-любому, он ничего не получает. Равновесие Нэша.
  В равновесиях Нэша игроки могут получать различные суммы платежей (не оптимальное равновесие Нэша)

Раскладка клавиатуры
В данный момент мы все пользуемся клавиатурами с раскладкой QWERTY, названной так по первым буквам на её верхней строчке. Начиная с XIX в буквы в печатных машинках были расположены именно в таком порядке, чтобы часто встречающиеся подряд в словах алфавита буквы не были расположены рядом. Уменьшали число сцепок при печатании. Если бы в наше время все использовали другую раскладку, которая позволяет печатать быстрее, то каждый получил бы больший платёж, и печатание занимало бы меньше времени. Но компаниям это не выгодно, так как их никто не будет покупать, ведь все уже привыкли и не хотят переучиваться . Следовательно, невозможно при фиксированных стратегиях всех остальных использовать для производства более удобную раскладку. Вот он, ещё один пример не оптимального равновесия по Нэшу.

изображение по лицензии Creative Commons CC0

5. Итог

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

Что для вас было наиболее интересным и впечатляющим в данной неделе курса?

Мне лично, равновесие Нэша хорошо знакомо по игре в покер. Хотя там и невозможно достичь идеального равновесия, за счёт большого количества переменных и не полной информации, но всё же очень помогает. Ведь в теории, если каждый игрок действует без ошибок, даже безлимитный холдем становится предсказуемой игрой с идентичными показателями у всех игроков на дистанции (количестве игр). Если максимально упростить, то можно объяснить на примере оллин/кол. По простому — ва-банк/уравнивание ставки.
Если мы знаем диапазон рук (перечень комбинаций карт, которые могут быть у игрока в конкретной игровой ситуации) с которыми соперник идёт оллин (ва-банк), то мы можем подстроить диапазон колов (поддержки его оллина). В конечном счёте, при дальнейшей подстройке, возникнет ситуация, когда спектры оллина и кола будут оптимальны друг для друга. Если кто-то изменит свою стратегию, то его ожидание (платёж) понизится. Это будет равновесием Нэша. У каждой покерной ситуации и покера в целом есть свое собственное равновесие Нэша.