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

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

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

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

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

Парадокс неожиданной казни

Примечания править

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

[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.

[1]

[2]

[3]

[4]

[5]