Обратная индукция

Равновесие, совершенное по подыграм

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

С точки зрения математической оптимизации, точнее динамического программирования обратная индукция — один из методов решения уравнения Беллмана[1][2]. В теории игр позволяет найти равновесие, совершенное по подыграм последовательной игры[3]. Для поиска равновесия необходимо охарактеризовать оптимальные стратегии всех игроков, то есть применить обратную индукцию к каждому из индивидуальных деревьев, либо сконструировать общее дерево. В автоматическом планировании и диспетчеризации и автоматическом доказательстве теорем метод обратной индукции называется «обратным поиском» или «обратным выводом». В шахматной терминологии обратную индукцию называют ретроградным анализом.

Обратная индукция столь же стара, сколь и сама теория игр. Джон фон Нейман и Оскар Моргенштерн применяли её для решения антагонистических игр. Их работа Theory of Games and Economic Behavior (1944) считается основополагающим текстом теории игр[4][5].

См. также

Примечания

  1. ↑ Jerome Adda and Russell Cooper, "Dynamic Economics: Quantitative Methods and Applications", Section 3.2.1, page 28. MIT Press, 2003.
  2. ↑ Mario Miranda and Paul Fackler, "Applied Computational Economics and Finance", Section 7.3.1, page 164. MIT Press, 2002.
  3. ↑ Drew Fudenberg and Jean Tirole, "Game Theory", Section 3.5, page 92. MIT Press, 1991.
  4. ↑ John von Neumann and Oskar Morgenstern, "Theory of Games and Economic Behavior", Section 15.3.1. Princeton University Press. (First edition, 1944.)
  5. ↑ Mathematics of Chess Архивная копия от 12 ноября 2017 на Wayback Machine, webpage by John MacQuarrie.