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

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

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

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

Формальное определение

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

Рационализация и повторяющееся доминирование

Основная статья: Рационализируемость

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

	Заключенный 2 Сотрудничать	Дефект Узника 2
Заключенный 1 Сотрудничать	−0.5, −0.5	−10, 0
Заключенный 1 Дефект	0, −10	−2, −2

Равновесие Нэша

Основная статья: Равновесие Нэша

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

Обратная индукция

Основная статья: Обратная индукция

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

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

Лучший ответ для действующего игрока, если участник примет участие, — это приспособиться, а лучший ответ для участника, если действующий игрок примет, — это войти. Это приводит к равновесию по Нэшу. Однако, если действующий президент решит бороться, лучшим ответом для участника будет не вступать. Если участник не участвует, не имеет значения, что решит сделать действующий участник. Следовательно, борьба может считаться лучшим ответом для действующего президента, если участник не вступит, что приведет к новому равновесию Нэша.

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

См. также:

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

Идеальное равновесие Нэша в подыграх

Основная статья: Идеальное равновесие в подигре

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

Идеальное байесовское равновесие

Основная статья: Байесовская игра

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

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

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

Прямая индукция

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

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

Прямая индукция дает уникальное решение для игры с горящими деньгами .

См. также

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

Ссылки

• Чо, Индиана; Крепс, Д.М. (1987). «Сигнальные игры и устойчивые равновесия». Ежеквартальный экономический журнал . 102 (2): 179–221. CiteSeerX   10.1.1.407.5013 . дои : 10.2307/1885060 . JSTOR   1885060 . S2CID   154404556 .
• Фуденберг, Дрю ; Тироль, Жан (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, № 4, ноябрь [2]
• Нольдеке Г. и Самуэльсон Л. (1993) Эволюционный анализ обратной и прямой индукции . Игры и экономическое поведение 5: 425–454.
• Мейнард Смит, Дж. (1982) Эволюция и теория игр . ISBN   0-521-28884-3
• Осборн, Мартин Дж.; Рубинштейн, Ариэль (1994). Курс теории игр . МТИ Пресс . ISBN  978-0-262-65040-3 . .
• Селтен, Р. (1983) Эволюционная стабильность в обширных играх двух человек . Математика. Соц. наук. 5:269–363.
• Селтен, Р. (1988) Эволюционная стабильность в обширных играх для двух человек – коррекция и дальнейшее развитие . Математика. Соц. наук. 16: 223–266
• Шохам, Йоав; Лейтон-Браун, Кевин (2009). Мультиагентные системы: алгоритмические, теоретико-игровые и логические основы . Нью-Йорк: Издательство Кембриджского университета . ISBN  978-0-521-89943-7 .
• Томас, Б. (1985a) Об эволюционно стабильных множествах. Дж. Математика. Биол. 22:105–115.
• Томас, Б. (1985b) Эволюционные стабильные множества в моделях смешанных стратегов . Теор. Поп. Биол. 28: 332–341