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

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

Распространенным методом определения идеального равновесия для подыгры в случае конечной игры является обратная индукция . Здесь сначала рассматриваются последние действия в игре и определяются действия, которые должен предпринять последний игрок в каждой возможной ситуации, чтобы максимизировать свою полезность . Затем предполагается, что эти действия будет выполнять последний субъект, и рассматриваются предпоследние действия, снова выбирая те, которые максимизируют полезность этого субъекта. Этот процесс продолжается до тех пор, пока не будет сделан первый ход игры. Остающиеся стратегии представляют собой совокупность совершенных равновесий всех подигр для обширных игр с совершенной информацией с конечным горизонтом. [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) как часть своей стратегии. [3]

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

Пунктирная линия указывает на то, что игрок 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).

Повторные игры [ править ]

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

Нахождение идеального равновесия для подыгры [ править ]

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

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

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

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

См. Также [ править ]

  • Сороконожка игра
  • Динамическая несогласованность
  • Глоссарий теории игр
  • Теорема о минимаксе
  • Ретроградный анализ
  • Концепция решения

Ссылки [ править ]

  1. ^ a b Осборн, MJ (2004). Введение в теорию игр . Издательство Оксфордского университета.
  2. ^ Кун, Гарольд Уильям; Такер, Альберт Уильям (2 марта 2016 г.). Вклад в теорию игр (AM-28), том II . Издательство Принстонского университета. ISBN 978-1-4008-8197-0.
  3. ^ a b Джоэл., Уотсон (2013-05-09). Стратегия: введение в теорию игр (Третье изд.). Нью-Йорк. ISBN 9780393918380. OCLC  842323069 .
  4. ^ Йылдыз, Мухамет (2012). «12 повторных игр» . 14.12. Экономические приложения теории игр . Массачусетский технологический институт: MIT OpenCourseWare . Проверено 27 апреля 2021 года .
  5. ↑ Такако, Фудзивара-Греве. Некооперативная теория игр . Токио. ISBN 9784431556442. OCLC  911616270 .

Внешние ссылки [ править ]

  • Селтен, Р. (1965). Spieltheoretische Behandlung eines oligopolmodells mit nachfrageträgheit. Zeitschrift für die gesamte Staatswissenschaft / Журнал институциональной и теоретической экономики , (H. 2), 301-324, 667-689. [на немецком языке - часть 1 , часть 2 ]
  • Пример игр с расширенной формой с несовершенной информацией
  • Java-апплет для поиска идеального решения равновесия Нэша для игр с расширенными формами от gametheory.net.
  • Java-апплет для поиска идеального решения равновесия Нэша для игр с расширенными формами от gametheory.net.
  • Камински, М.М. Обобщенная обратная индукция: обоснование народного алгоритма . Игры 2019, 10, 34.