Концепция решения

Избранные уточнения равновесия в теории игр. Стрелки указывают от уточнения к более общей концепции (например, ESS собственно).${\ displaystyle \ subset}$

В теории игр , концепция решения является формальным правилом для прогнозирования , как будет играть игра. Эти прогнозы называются «решениями» и описывают, какие стратегии будут приняты игроками и, следовательно, результат игры. Наиболее часто используемые концепции решения - это концепции равновесия , наиболее известная из которых - равновесие по Нэшу .

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

Формальное определение [ править ]

Пусть класс всех игр , и для каждой игры , пусть множество стратегических профилей из . Концепция решения является элементом прямого произведения , т.е. ., Функция такая , что для всех${\ displaystyle \ Gamma}$${\ Displaystyle G \ in \ Gamma}$${\ displaystyle S_ {G}}$${\ displaystyle G}$${\ Displaystyle \ Pi _ {G \ in \ Gamma} 2 ^ {S_ {G}};}$ ${\ Displaystyle F: \ Gamma \ rightarrow \ bigcup \ nolimits _ {G \ in \ Gamma} 2 ^ {S_ {G}}}$${\ Displaystyle F (G) \ substeq S_ {G}}$${\ displaystyle G \ in \ Gamma.}$

Рационализируемость и повторное доминирование [ править ]

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

Равновесие Нэша [ править ]

Равновесие Нэша - это профиль стратегии ( профиль стратегии определяет стратегию для каждого игрока, например, в приведенной выше игре дилеммы заключенного ( сотрудничать , дефект ) указано, что заключенный 1 играет в сотрудничестве, а заключенный 2 играет в дефект ), в котором каждая стратегия является наилучшей. ответ на любую другую сыгранную стратегию. Стратегия игрока - лучший ответ на стратегию другого игрока, если нет другой стратегии, которую можно было бы разыграть, которая принесла бы более высокую отдачу в любой ситуации, в которой разыгрывается стратегия другого игрока.

Обратная индукция [ править ]

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

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

Если участник входит, лучший ответ действующего оператора - приспособиться. Если действующий оператор соглашается, лучший ответ новичка - войти (и получить прибыль). Следовательно, профиль стратегии, в котором действующий участник приспосабливается, если участник входит, и участник входит, если действующий участник приспосабливается, является равновесием по Нэшу. Однако, если действующий игрок собирается драться, лучший ответ участника - не входить. Если участник не входит, не имеет значения, что решит сделать действующий президент (поскольку нет другой фирмы, которая могла бы это сделать - обратите внимание, что если участник не входит, борьба и уступка принесут одинаковые выплаты обоим игрокам; действующий участник не будет снижать цены, если участник не войдет). Следовательно, бой можно рассматривать как лучший ответ действующего президента, если участник не входит.Следовательно, профиль стратегии, в котором действующий участник борется, если участник не входит, и участник не входит, если действующий участник борется, является равновесием по Нэшу. Поскольку игра динамична, любое заявление действующего президента о том, что она будет сражаться, представляет собой невероятную угрозу, потому что к тому времени, когда будет достигнут узел принятия решения, в котором он может принять решение о сражении (т.е. участник вошел), было бы нерационально делать это. Следовательно, это равновесие по Нэшу может быть устранено обратной индукцией.Следовательно, это равновесие по Нэшу может быть устранено обратной индукцией.Следовательно, это равновесие по Нэшу может быть устранено обратной индукцией.

Смотрите также:

• Теория денежно-кредитной политики
• Соревнование Штакельберга

Подигра идеальное равновесие по Нэшу [ править ]

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

Идеальное байесовское равновесие [ править ]

Иногда совершенствование вспомогательной игры не накладывает достаточно больших ограничений на необоснованные результаты. Например, поскольку вспомогательные игры не могут прорезать информационные наборы , игра с несовершенной информацией может иметь только одну вспомогательную игру - саму себя - и, следовательно, совершенство вспомогательной игры не может использоваться для устранения любого равновесия по Нэшу. Идеальное байесовское равновесие (PBE) - это спецификация стратегий и убеждений игроков о том, какой узел в информационном наборе был достигнут в ходе игры. Убеждение об узле решения - это вероятность того, что конкретный игрок считает, что этот узел участвует или будет в игре (на пути равновесия).). В частности, интуиция PBE заключается в том, что он определяет стратегии игрока, которые являются рациональными с учетом определенных им убеждений игрока, и те убеждения, которые он определяет, согласуются со стратегиями, которые он определяет.

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

Байесовский во имя этого понятия решение намекает на то , что игроки обновить свои убеждения в соответствии с теоремой Байеса . Они вычисляют вероятности с учетом того, что уже произошло в игре.

Прямая индукция [ править ]

Прямая индукция называется так потому, что так же, как обратная индукция предполагает, что будущая игра будет рациональной, прямая индукция предполагает, что прошлая игра была рациональной. Если игрок не знает, к какому типу принадлежит другой игрок (т. Е. Имеется несовершенная и асимметричная информация), этот игрок может сформировать представление о том, к какому типу принадлежит этот игрок, наблюдая за прошлыми действиями этого игрока. Следовательно, сформированное этим игроком убеждение в том, что вероятность того, что противник принадлежит к определенному типу, основано на рациональности прошлой игры этого противника. Игрок может по своему выбору сигнализировать о своем типе своими действиями.

Кольберг и Мертенс (1986) ввели понятие решения стабильного равновесия, уточнение, которое удовлетворяет прямой индукции. Был найден контрпример, когда такое устойчивое равновесие не удовлетворяло обратной индукции. Чтобы решить эту проблему, Жан-Франсуа Мертенс ввел то, что теоретики игр теперь называют концепцией стабильного равновесия по Мертенсу, вероятно, первую концепцию решения, удовлетворяющую как прямой, так и обратной индукции.

См. Также [ править ]

• Обширная игра формы
• Равновесие дрожащих рук
• « Интуитивный критерий » ( Чо и Крепс, 1987 )

Ссылки [ править ]

• Чо, ИК .; Крепс, Д.М. (1987). «Сигнальные игры и стабильные равновесия». Ежеквартальный журнал экономики . 102 (2): 179–221. CiteSeerX  10.1.1.407.5013 . DOI : 10.2307 / 1885060 . JSTOR  1885060 .CS1 maint: ref = harv ( ссылка )
• Фуденберг, Дрю ; Тироль, Жан (1991). Теория игр . Кембридж, Массачусетс: MIT Press . ISBN 9780262061414. Предварительный просмотр книги.
• Харшани, Дж. (1973) Странность количества точек равновесия: новое доказательство . Международный журнал теории игр 2: 235–250.
• Говиндан, Шрихари и Роберт Уилсон, 2008. «Уточнения равновесия по Нэшу», Новый экономический словарь Палгрейва, 2-е издание. [1]
• Хайнс, WGS (1987) Эволюционно стабильные стратегии: обзор базовой теории . Теоретическая популяционная биология 31: 195–272.
• Кольберг, Илон и Жан-Франсуа Мертенс, 1986. « О стратегической стабильности равновесий », Econometrica, Econometric Society, vol. 54 (5), страницы 1003-37, сентябрь.
• Лейтон-Браун, Кевин; Шохам, Йоав (2008). Основы теории игр: краткое, междисциплинарное введение . Сан-Рафаэль, Калифорния: Издательство Morgan & Claypool. ISBN 978-1-59829-593-1.
• Мертенс, Жан-Франсуа, 1989. "Стабильные равновесия - переформулировка. Часть 1 Основные определения и свойства", Математика исследования операций, Vol. 14, No. 4, ноябрь [2]
• Нолдеке, Г. и Самуэльсон, Л. (1993) Эволюционный анализ обратной и прямой индукции . Игры и экономическое поведение 5: 425–454.
• Мейнард Смит, Дж. (1982) Эволюция и теория игр . ISBN 0-521-28884-3 
• Осборн, Мартин Дж .; Рубинштейн, Ариэль (1994). Курс теории игр . MIT Press . ISBN 978-0-262-65040-3..
• Селтен, Р. (1983) Эволюционная устойчивость в обширных играх двух лиц . Математика. Soc. Sci. 5: 269–363.
• Селтен, Р. (1988) Эволюционная устойчивость в обширных играх для двух лиц - исправление и дальнейшее развитие . Математика. Soc. Sci. 16: 223–266
• Шохам, Йоав; Лейтон-Браун, Кевин (2009). Мультиагентные системы: алгоритмические, теоретико-игровые и логические основы . Нью-Йорк: Издательство Кембриджского университета . ISBN 978-0-521-89943-7.
• Томас Б. (1985a) Об эволюционно устойчивых множествах. J. Math. Биол. 22: 105–115.
• Томас Б. (1985b) Эволюционные устойчивые множества в моделях смешанной стратегии . Теор. Поп. Биол. 28: 332–341