Принцип однократного отклонения
 | Эта статья может быть слишком технической для понимания большинства читателей . ( Март 2014 г. ) |
Принцип однократного отклонения (также известный как свойство однократного отклонения). [1] ) — принцип оптимальности динамического программирования применительно к теории игр . [2] В нем говорится, что профиль стратегии конечной многоэтапной игры расширенной формы с наблюдаемыми действиями представляет собой идеальное равновесие подигры (SPE) тогда и только тогда, когда не существует единственного прибыльного отклонения для каждой подигры и каждого игрока. [1] [3] Проще говоря, если ни один игрок не может увеличить свой ожидаемый выигрыш, отклонившись от своей первоначальной стратегии одним действием (всего за один этап игры), то профиль стратегии представляет собой SPE. Другими словами, ни один игрок не сможет получить прибыль, отклонившись от стратегии в течение одного периода, а затем вернувшись к ней.
Более того, принцип одноразового отклонения очень важен для игр с бесконечным горизонтом, в которых этот принцип обычно не соблюдается. [4] поскольку для решения невозможно рассматривать бесконечное количество стратегий и выигрышей. В игре с бесконечным горизонтом, где коэффициент дисконтирования меньше 1, профиль стратегии является идеальным равновесием в подигре тогда и только тогда, когда он удовлетворяет принципу одноразового отклонения. [5]
Определения
[ редактировать ]Ниже приводится перефразированное определение Уотсона (2013). [1]
Чтобы проверить, является ли стратегия s идеальным равновесием Нэша в подигре, мы должны спросить каждого игрока i и каждую подигру, существует ли с учетом s стратегия s' , которая дает игроку i строго более высокий выигрыш, чем s в подигре. В конечной многоэтапной игре с наблюдаемыми действиями этот анализ эквивалентен рассмотрению отдельных отклонений от s , что означает, что s' отличается от s только в одном наборе информации (за один этап). Обратите внимание, что выбор, связанный с s и s', одинаков на всех узлах, которые являются преемниками узлов в информационном наборе, где s и s' предписывают разные действия.
Пример
[ редактировать ]Рассмотрим симметричную игру с двумя игроками, в которой каждый игрок принимает решения о бинарном выборе A или B на каждом из трех этапов. На каждом этапе игроки наблюдают за выбором, сделанным на предыдущих этапах (если таковой был). Обратите внимание, что у каждого игрока есть 21 набор информации: один на первом этапе, четыре на втором этапе (поскольку игроки наблюдают за результатом первого этапа, одной из четырех комбинаций действий) и 16 на третьем этапе (4 раза по 4 истории комбинации действий из первых двух этапов). Условие однократного отклонения требует проверки каждого из этих наборов информации, задавая в каждом случае вопрос, будет ли строго увеличиваться ожидаемый выигрыш игрока на ходу при отклонении только от этого набора информации.
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с Уотсон, Джоэл (2013). Стратегия: введение в теорию игр . Нью-Йорк: WW Norton & Company. п. 194. ИСБН 978-0393123876 .
- ^ Блэквелл, Дэвид (1965). «Скидка на динамическое программирование» . Анналы математической статистики . 36 : 226–235. дои : 10.1214/aoms/1177700285 .
- ^ Тироль, Жан; Фуденберг, Дрю (1991). Теория игр (6-е издание. Изд.). Кембридж, Массачусетс. [утро]: MIT Press. ISBN 978-0-262-06141-4 .
- ^ Обара, И. (2012). Подигра «Идеальное равновесие» [документ в формате PDF]. Слайд 13. Получено с http://www.econ.ucla.edu/iobara/SPE201B.pdf.
- ^ Оздаглар, А. (2010). Повторные игры [документ PDF]. Слайд 13. Получено с https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-254-game-theory-with-engineering-applications-spring-2010/lecture-notes/MIT6_254S10_lec15 . .pdf