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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
Равновесие, совершенное по подыграм

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

С точки зрения математической оптимизации, точнее динамического программирования обратная индукция — один из методов решения уравнения Беллмана[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.