Академия. Теория игр. Неделя 3.
Чем дальше я продвигаюсь в изучении курса "Теория игр" от Высшей школы экономики, тем больше начинаю понимать полезность проекта Вторая академия. Учёба захватывает, всё свободное время стремишься посвятить просмотру видолекций и выполнению заданий. На мой взгляд идея @ontofractal об организации такого взаимодействия пользователей с образовательной средой Coursera оказалась весьма удачной.
Мы уже знакомы с двумя концепциями решения игр: равновесия в доминирующих стратегиях и равновесия, полученного исключением доминируемых стратегий. Сегодня нам предстоит познакомиться с ещё одной концепцией.
РАВНОВЕСИЕ НЭША: ТЕОРИЯ
Если в предыдущих стратегиях мы делали вывод о том, какую стратегию сыграет игрок, в результате наложения некоторых условий на их стратегии, то теперь мы будем накладывать требования на профили стратегий.Вернёмся к "Битве полов". На матрице игры видно, что ни у одного из игроков нет доминирующей стратегии:
Однако есть профили стратегий, которые более выгодны остальных. Например, профиль (футбол, футбол), в котором каждый из игроков играет оптимальную стратегию в ответ на стратегию другого игрока. Значит, если вдруг кто-то из игроков узнает намерение другого сыграть именно этот профиль, то он не станет менять свою стратегию на другую, менее выгодную. Тем же свойством обладает и профиль (балет, балет). Можно сказать, что эти два профиля являются устойчивыми или некоторыми равновесиями. Будут ли два оставшихся профиля игры обладать этими же свойствами устойчивости? Очевидно, что нет. Например, если выбирается профиль (футбол, балет), то жене выгоднее поменять балет на футбол, а мужу - футбол на балет, так как в этих случаях их платежи увеличатся. Аналогичный вывод можно сделать и о последней стратегии (балет, футбол).
Итак, в игре есть два вида профилей:
1) в которых каждый игрок играет оптимально в ответ на стратегию соперника - (футбол, футбол) и (балет, балет),
2) в которых по крайней мере один из игроков играет неоптимально в ответ на стратегию соперника - (футбол, балет) и (балет, футбол).
То есть равновесие Нэша — это такой профиль стратегий, в котором ни одному из игроков не выгодно менять свою стратегию при фиксированных стратегиях всех остальных игроков. Если хотя бы одному игроку выгодно отклониться от выбранной стратегии, то этот профиль не является равновесием Нэша.
Эта концепция названа в честь американского математика Джона Форбса Нэша, который будет известен тем читателям, которые смотрели фильм Рона Ховарда "Игры разума". А если не смотрели - рекомендую, картина заслужена получила четыре "Оскара" и "Золотой глобус".
Если в игре участвует конечное количество игроков, и у каждого из них есть конечное количество стратегий, то все равновесия Нэша можно найти, придерживаясь довольно простого алгоритма. Для упрощения ситуации условимся, что у нас два игрока. Тогда в матрице игры нам необходимо проделать следующее:
Лучше всего понять работу алгоритма на конкретном примере. Пусть в некотором городе есть два университета, конкурирующих в том, чтобы именно их выпускники были востребованы на местном рынке труда. А работодатели при выборе работников ориентируются на их средний балл в дипломе. Условимся, что у университетов есть две возможные стратегии: завышать балл своим студентам (З) или не завышать (Н). Рассмотрим матрицу игры:
Проанализировав её, нетрудно заметить, что в этой игре у каждого из университетов есть одинаковые доминирующие стратегии - "завышать", а, значит, и существует равновесие в доминирующих стратегиях.
Но это же равновесие является и равновесием Нэша, поскольку в случае выбора каждым из университетов стратегии "завышать" любая другая стратегия приведёт к меньшим платежам, и им не выгодно отклоняться от неё. В реальной жизни подобная ситуация является ловушкой, выбраться из которой весьма проблематично.
Совпадение равновесия в доминирующих стратегиях и равновесия Нэша в рассмотренном примере не является случайностью.
Между рассмотренными ранее концепциями и равновесием Нэша существуют следующие связи:
1. Если в игре существует равновесие в строго доминирующих стратегиях, то оно всегда так же будет и равновесием Нэша, и других равновесий Нэша в этой игре нет.
2. Если в игре существует равновесие в слабо доминирующих стратегиях, то оно всегда так же будет и равновесием Нэша, но в этой игре могут быть и другие равновесия Нэша.
3. Если в игре существует равновесие, полученное исключением строго доминируемых стратегий, то оно всегда так же будет и равновесием Нэша, и других равновесий Нэша в этой игре нет
4. Само равновесие Нэша не обязательно является равновесием в доминирующих стратегиях или равновесием, получаемым исключением доминируемых стратегий.
Кроме того бывают ситуации, когда в игре вообще нет ни одного равновесия Нэша:
или когда все профиля являются равновесиями Нэша:
РАВНОВЕСИЕ НЭША: ПРИМЕРЫ
1. Любимая забава всех политиков - выборы. Поэтому первый пример для рассмотрения равновесия Нэша - финансирование избирательной кампании. Итак, в одном уездном городе N намечаются выборы мэра, есть два кандидата, и единственным условием, влияющим на исход кампании, является финансирование каждого из претендентов на пост мэра. Победа будет за тем кандидатом, который привлечёт наибольшее количество средств. В случае, если оба кандидата добиваются одинакового финансирования, то бросается монетка: "орёл" - побеждает один, "решка" - другой. Стратегией в этой игре будет решение о том, какая сумма потраченных денег будет оптимальной.
Пусть у первого сумма равно с1, а у второго - с2. Каковы возможные платежи? Гарантированная победа с вероятностью 1, победа с вероятностью 1/2 (бросание монетки) и поражение. И при этом каждый хотел бы потратить как можно меньше. Какие могут быть профили стратегий?
1. с1>с2, то есть первый гарантированно побеждает. Однако, эта ситуация не будет равновесной, поскольку он в этом случае играет неоптимально. Ведь он мог бы потратить немного меньше денег, чем с1, но больше, чем с2. Получается, что ему всё-таки выгодно отклониться от этого профиля.
2. с2>с1, всё аналогично, но только для второго кандидата - равновесия нет.
3. с1=с2, то есть кто-то из них победит с вероятностью не 1 , а только 1/2. В этом случае каждому из кандидатов выгоднее немного увеличить своё финансирование, чтобы победа стала гарантированной. Выходит, что опять каждому выгоднее отклониться и сыграть другую стратегию.
Итак, в этой игре нет равновисия Нэша.
2. Следующий пример - игра "В сумме - 100". Правила таковы: - играют два человека, каждый пишет на бумажке независимо друг от друга некоторое неотрицательное число,- если сумма этих чисел не превосходит 100, то каждый получает количество денег, равное написанному им числу,- если сумма превосходит 100, то никто ничего не получает.
Поищем в этой игре равновесия Нэша. Пусть первый игрок написал число х, а второй - у. Рассмотрим все возможные варианты профиля (х; у). Их можно подвергнуть следующей классификации:
1. х+у=100. Это может быть вариант (50; 50) или (2; 98). Выгодно ли игрокам отклоняться от этого профиля? Нет. Потому что, если любой из них увеличит своё число, то сумма превысит 100, и никто из них не получит ничего, то есть никто не увеличивает свой платёж. И если любой из них уменьшит своё число, то, опять же, он не улучшает свой платёж, поскольку он уменьшается. Значит это будет равновесие Нэша.
2. х+у<100. Здесь явно каждому из игроков выгодно уклониться к другой стратегии, увеличив своё число так, чтобы сумма двух чисел не превысила 100. Значит, это не равновесие Нэша.
3. х>100, y<100 (x<100, y>100). В этом случае тот, кто пишет число, превосходящее 100 - явно не в себе, поэтому ему надо бы отказаться от такой стратегии, а подобный профиль, естественно, не будет равновесным.
4. х<=100, у<=100. Ни одному из игроков при таком раскладе не выгодно отклоняться к другой стратегии, поскольку уменьшая или увеличивая своё число, при фиксированном варианте противника, он не сделает сумму двух чисел меньшей или равной 100. То есть, по-любому, он ничего не получает. Это - равновесие Нэша.
5. х>100, y>100. Здесь, как и в третьем варианте, игроки не в адеквате (причём - оба). Но это равновесная ситуация: отклонение любого из них при фиксированной стратегии другого не увеличивают ему платежи, поскольку сумма двух чисел гарантированно остаётся больше 100.
Вывод: в различных равновесиях Нэша игроки могут получать различные суммы платежей, то есть равновесие Нэша может быть неоптимальным.
3. Далее вернёмся к уже знакомой для вас "Дилемма заключённого". В матрице игры видно, что у каждого игрока есть доминирующая стратегия "предать":
Профиль (предать, предать) является равновесием в доминирующих стратегиях и равновесием Нэша. Вызывает вопросы другой профиль - (молчать, молчать), который приносит обоим игрокам большие платежи. Но для выбора этого профиля у игроков нет связующих обязательств. Даже если до ограбления они договорились: в случае поимки - молчать, никто из них не может быть уверен в том, что другой выполнит эту договорённость. Более выгодным остаётся профиль (предать, предать), то есть равновесие Нэша.
Другое дело, если на свободе остаётся третий игрок, который следит за выполнением договорённости "молчать". Но в этом случае это будет уже другая игра с другими платежами и другие оптимальные стратегии.
4. Ещё один пример неоптимального равновесия по Нэшу - раскладка клавиатуры. Сейчас мы используем раскладку QWERTY, которая была придумана ещё для печатных машинок. Принцип расположения букв преследовал одну цель - чтобы рычажки с буквами не переклинивали друг друга. Для этого часто встречающие в словах подряд идущие буквы были разнесены подальше друг от друга. Но для печати на современной клавиатуре этот принцип, наоборот, является фактором, затрудняющем печать. Была разработана другая раскладка - Dvorak, но на неё не стали переходить, поскольку люди не захотели бы переучиваться, и такие клавиатуры просто никто бы не покупал (при условии, что кто-то бы продолжал выпускать QWERTY). И хотя выгоднее было бы отклониться от QWERTY, но старая раскладка оказалась неоптимальным равновесием Нэша, поэтому я сейчас и набираю этот текст именно в ней.
ИНТЕРПРЕТАЦИЯ РАВНОВЕСИЯ НЭША
Итак, равновесие Нэша - это концепция, позволяющая найти профили, в которых каждый игрок играет оптимальную стратегию в ответ на стратегии соперников. Она позволяет решать более широкий спектр игр по сравнению с рассмотренными ранее равновесием в доминирующих стратегиях и равновесием, полученном исключением доминируемых стратегий. Ведь, если у игроков нет доминирующих или доминируемых стратегий, то и применить соответствующие концепции не получится. Однако, в некоторых случаях нас выручит равновесие по Нэшу. Но решение, получаемое с помощью этой концепции, будет обладать более слабыми свойствами.
Вывод: из трёх рассмотренных концепций равновесие по Нэшу - самая сильная по широте охватываемых игр, но самая слабая по свойствам получаемых решений.
ЧТО ДЛЯ МЕНЯ БЫЛО НАИБОЛЕЕ ИНТЕРЕСНЫМ ИЗ ЭТОЙ НЕДЕЛИ КУРСА
Ещё одна концепция решения игр - равновесие Нэша - позволяет искать оптимальные стратегии в ситуациях, с которыми не справляются концепции, основанные на доминирующих и доминируемых стратегиях. Автор этой концепции оказался неожиданно знаком мне по виденному когда-то художественному фильму, рассказывающему удивительную историю его жизни. Однако, рассматриваемое равновесие также не идеально и обладает определёнными недостатками.