stringtranslate.com

Идеальное равновесие подигры

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

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

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

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

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

Пример

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

Рисунок 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) как часть своей стратегии. [3]

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

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

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

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

Решение подигры «Идеальное равновесие»

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

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

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

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

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

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

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

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

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

Ссылки

  1. ^ ab Osborne, MJ (2004). Введение в теорию игр . Oxford University Press.
  2. ^ Кун, Гарольд Уильям; Такер, Альберт Уильям (2 марта 2016 г.). Вклад в теорию игр (AM-28), том II. Princeton University Press. ISBN 978-1-4008-8197-0.
  3. ^ ab Joel., Watson (2013-05-09). Стратегия: введение в теорию игр (Третье изд.). Нью-Йорк. ISBN 9780393918380. OCLC  842323069.{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
  4. ^ Йылдыз, Мухамет (2012). «12 повторяющихся игр». 14.12 Экономические приложения теории игр . Массачусетский технологический институт: MIT OpenCourseWare . Получено 27 апреля 2021 г.
  5. ^ Такако, Фудзивара-Греве (27 июня 2015 г.). Некооперативная теория игр . Токио. ISBN 9784431556442. OCLC  911616270.{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

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