Концепция решения - Solution concept

Избранные уточнения равновесия в теории игр. Стрелки указывают от уточнения к более общей концепции (т. Е. 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.}$

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

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

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

равновесие по Нэшу

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

использованная литература

Чо, И-К .; Крепс, Д. М. (1987). «Сигнальные игры и стабильное равновесие». Ежеквартальный журнал экономики. 102 (2): 179–221. CiteSeerX 10.1.1.407.5013. Дои:10.2307/1885060. JSTOR 1885060.CS1 maint: ref = harv (ссылка на сайт)
Фуденберг, Дрю; Тироль, Жан (1991). Теория игры. Кембридж, Массачусетс: MIT Press. ISBN 9780262061414. Предварительный просмотр книги.
Харшани, Дж. (1973) Странность количества точек равновесия: новое доказательство. Международный журнал теории игр 2:235–250.
Говиндан, Шрихари и Роберт Уилсон, 2008. «Уточнения равновесия по Нэшу», Новый экономический словарь Палгрейва, 2-е издание.[1]
Хайнс, В. Г. С. (1987) Эволюционно стабильные стратегии: обзор основ теории. Теоретическая популяционная биология 31:195–272.
Кольберг, Илон и Жан-Франсуа Мертенс, 1986 г. "О стратегической устойчивости равновесий, "Econometrica, Econometric Society, том 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

Темы в теория игры
Определения	Кооперативная игра Решительность Эскалация обязательств Игра в расширенной форме Победа первого и второго игрока Сложность игры Графическая игра Иерархия убеждений Информационный набор Игра в нормальной форме Предпочтение Последовательная игра Одновременная игра Выбор одновременного действия Решенная игра Лаконичная игра
Равновесие концепции	равновесие по Нэшу Совершенство подигры Устойчивое равновесие по Мертенсу Байесовское равновесие по Нэшу Идеальное байесовское равновесие Дрожащая рука Правильное равновесие Эпсилон-равновесие Коррелированное равновесие Последовательное равновесие Квази-совершенное равновесие Эволюционно устойчивая стратегия Доминирование риска Ядро Значение Шепли Парето эффективность Равновесие Гиббса Квантовое равновесие отклика Самоподтверждающееся равновесие Сильное равновесие по Нэшу Марковское идеальное равновесие
Стратегии	Доминирующие стратегии Чистая стратегия Смешанная стратегия Аргумент кражи стратегии Око за око Мрачный спусковой крючок Сговор Обратная индукция Прямая индукция Марковская стратегия Затенение ставки
Классы игр	Симметричная игра Идеальная информация Повторная игра Сигнальная игра Показ игры Дешевый разговор Игра с нулевой суммой Конструкция механизма Проблема торга Стохастическая игра Среднее поле игры п-игровая игра Большая игра Пуассона Нетранзитивная игра Глобальная игра Строго определенная игра Возможная игра
Игры	Идти Шахматы Бесконечные шахматы Шашки Крестики-нолики Дилемма заключенного Игра по обмену подарками Необязательная дилемма заключенного Дилемма путешественника Координационная игра Курица Сороконожка игра Дилемма волонтера Долларовый аукцион Битва полов Охота на оленя Соответствующие пенни Ультиматум игра Камень ножницы Бумага Пиратская игра Игра диктатора Игра в общественные блага Блотто игра Война на истощение Проблема с баром Эль Фарол Справедливое деление Ярмарка нарезки торта Игра Курно Тупик Дилемма закусочной Угадайте 2/3 среднего Покер куна Игра Нэша в торг Индукционные пазлы Доверительная игра Игра принцесс и монстров Проблема рандеву
Теоремы	Теорема о невозможности Эрроу Теорема согласия Ауманна Народная теорема Теорема о минимаксе Теорема Нэша Теорема очищения Принцип откровения Теорема Цермело
Ключ цифры	Альберт В. Такер Амос Тверски Антуан Огюстен Курно Ариэль Рубинштейн Клод Шеннон Даниэль Канеман Дэвид К. Левин Дэвид М. Крепс Дональд Б. Гиллис Дрю Фуденберг Эрик Маскин Гарольд В. Кун Герберт Саймон Эрве Мулен Жан Тироль Жан-Франсуа Мертенс Дженнифер Тур Чейес Джон Харсаньи Джон Мейнард Смит Джон Нэш Джон фон Нейман Кеннет Эрроу Кеннет Бинмор Леонид Гурвич Ллойд Шепли Мелвин Дрешер Меррилл М. Флуд Ольга Бондарева Оскар Моргенштерн Пол Милгром Пейтон Янг Райнхард Зельтен Роберт Аксельрод Роберт Ауманн Роберт Б. Уилсон Роджер Майерсон Сэмюэл Боулз Сюзанна Скотчмер Томас Шеллинг Уильям Викри
Смотрите также	All-pay аукцион Альфа – бета обрезка Парадокс Бертрана Ограниченная рациональность Комбинаторная теория игр Анализ конфронтации Сотрудничество Эволюционная теория игр Преимущество первого хода в шахматах Игровая механика Глоссарий теории игр Список теоретиков игр Список игр по теории игр Безвыигрышная ситуация Решение шахмат Топологическая игра Трагедия общественного достояния Тирания маленьких решений