Подигра идеальное равновесие

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

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

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

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

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

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

СОДЕРЖАНИЕ

  • 1 Пример
  • 2 Повторные игры
  • 3 Нахождение идеального равновесия по подиграм
  • 4 См. Также
  • 5 ссылки
  • 6 Внешние ссылки

Пример

Определение идеального равновесия во вспомогательной игре с использованием обратной индукции показано ниже на рисунке 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 для 3gt; 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) как часть своей стратегии.

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

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

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

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

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

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

Повторные игры

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

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

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

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

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

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

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

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

Внешние ссылки

Последняя правка сделана 2023-04-05 05:37:26
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте