Подигра идеальное равновесие - Subgame perfect equilibrium

Подигра Идеальное равновесие
А концепция решения в теория игры
Отношение
Подмножестворавновесие по Нэшу
Пересекается сЭволюционно устойчивая стратегия
Значимость
ПредложеноРайнхард Зельтен
Используется дляИгры с расширенной формой
ПримерУльтиматум игра

В теория игры, а подигра идеальное равновесие (или же подигра идеальное равновесие по Нэшу) это уточнение из равновесие по Нэшу используется в динамические игры. А профиль стратегии является совершенным равновесием для подыгры, если оно представляет собой равновесие по Нэшу каждого вспомогательная игра оригинальной игры. Неформально это означает, что в любой момент игры поведение игроков, начиная с этого момента, должно представлять собой равновесие по Нэшу для продолжения игры (т. Е. Вспомогательной игры), независимо от того, что произошло раньше. Каждый конечная обширная игра с идеальным отзывом имеет идеальное равновесие подигры.[1]

Общий метод определения идеального равновесия для подыгры в случае конечной игры: обратная индукция. Здесь сначала рассматриваются последние действия в игре и определяются действия, которые должен предпринять последний игрок в каждой возможной ситуации, чтобы максимизировать его / ее. полезность. Затем предполагается, что эти действия будет выполнять последний актор, и учитываются предпоследние действия, снова выбирая те, которые максимизируют полезность этого актора. Этот процесс продолжается до тех пор, пока не будет сделан первый ход игры. Остающиеся стратегии - это совокупность совершенных равновесий всех подигр для обширных игр с совершенной информацией с конечным горизонтом.[1] Однако обратная индукция не может применяться к играм несовершенный или же неполная информация потому что это влечет за собой сокращение не синглетонов информационные наборы.

Совершенное равновесие в подыгре обязательно удовлетворяет принцип однократного отклонения.

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

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

Пример

Определение идеального равновесия во вспомогательной игре с использованием обратной индукции показано ниже на рисунке 1. Стратегии для Игрока 1 задаются как {Up, Uq, Dp, Dq}, тогда как у Игрока 2 есть следующие стратегии: {TL, TR, BL, BR}. В этом примере есть 4 подигры с 3 собственными подиграми.

Рисунок 1

Используя обратную индукцию, игроки будут выполнять следующие действия для каждой вспомогательной игры:

  • Подигра для действий p и q: Игрок 1 выполнит действие p с выигрышем (3, 3), чтобы максимизировать выигрыш Игрока 1, поэтому выигрыш за действие L станет (3,3).
  • Подигра для действий L и R: Игрок 2 выполнит действие L для 3> 2, поэтому выигрыш за действие D станет (3, 3).
  • Подигра для действий T и B: Игрок 2 выполнит действие T, чтобы максимизировать выигрыш Игрока 2, поэтому выигрыш за действие U станет (1, 4).
  • Подигра для действий U и D: Игрок 1 выполнит действие D, чтобы максимизировать выигрыш Игрока 1.

Таким образом, совершенное равновесие в подигре - это {Dp, TL} с выигрышем (3, 3).

Игра в расширенной форме с неполной информацией представлена ​​ниже на рисунке 2. Обратите внимание, что узел для Игрока 1 с действиями A и B и всеми последующими действиями является вспомогательной игрой. Узлы игрока 2 не являются вспомогательной игрой, поскольку они являются частью того же набора информации.

фигура 2

Первая игра в нормальной форме - это представление в нормальной форме всей игры в развернутой форме. На основании предоставленной информации (UA, X), (DA, Y) и (DB, Y) - все это равновесия Нэша для всей игры.

Вторая игра в нормальной форме - это представление в нормальной форме подигры, начиная со второго узла Игрока 1 с действиями A и B. Для второй игры в нормальной форме равновесие по Нэшу во вспомогательной игре равно (A, X).

Для всей игры равновесия по Нэшу (DA, Y) и (DB, Y) не являются идеальными уравнениями для подыгры, поскольку ход игрока 2 не составляет равновесия по Нэшу. Равновесие по Нэшу (UA, X) является совершенным по подыгре, потому что оно включает в себя равновесие по Нэшу (A, X) как часть своей стратегии.[2]

Чтобы решить эту игру, сначала найдите равновесие Нэша путем взаимного наилучшего отклика подигры 1. Затем используйте обратную индукцию и вставьте (A, X) → (3,4) так, чтобы (3,4) стали выигрышами для подигры 2.[2]

Пунктирная линия показывает, что игрок 2 не знает, сыграет ли игрок 1 A или B в одновременной игре.

Подигра 1 решена, и (3,4) заменяет всю Подигру 1, и игрок 1 выберет U -> (3,4) Решение для Подигры 1

Игрок 1 выбирает U, а не D, потому что 3> 2 для выигрыша Игрока 1. В результате получается равновесие (A, X) → (3,4).

Решение идеального равновесия в подигре

Таким образом, совершенное равновесие в подигре посредством обратной индукции - это (UA, X) с выигрышем (3, 4).

В конечно повторяющихся играх

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

Если сценическая игра в конечно повторяющейся игре имеет несколько равновесий по Нэшу, можно построить совершенные равновесия подигры для выполнения действий равновесия по Нэшу вне сценической игры посредством структуры «кнута и пряника». Один игрок может использовать равновесие по Нэшу в рамках одной поэтапной игры, чтобы стимулировать игру не по равновесию по Нэшу, в то же время используя равновесие по Нэшу в поэтапной игре с меньшим выигрышем для другого игрока, если он решит отказаться.[3]

Нахождение идеального равновесия по подиграм

Одна игра, в которой решение обратной индукции хорошо известно, это крестики-нолики

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

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

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

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

Рекомендации

  1. ^ а б Осборн, М. Дж. (2004). Введение в теорию игр. Издательство Оксфордского университета.
  2. ^ а б Джоэл., Ватсон (09.05.2013). Стратегия: введение в теорию игр (Третье изд.). Нью-Йорк. ISBN  9780393918380. OCLC  842323069.
  3. ^ Такако, Фудзивара-Греве. Некооперативная теория игр. Токио. ISBN  9784431556442. OCLC  911616270.

внешняя ссылка