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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Равновесие, совершенное по подыграм

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

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

Обратная индукция столь же стара, сколь и сама теория игр. Джон фон Нейман и Оскар Моргенштерн применяли её для решения антагонистических игр. Их работа 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. Third edition, 1953. (First edition, 1944.)
  5. Mathematics of Chess, webpage by John MacQuarrie.