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

Обратная индукция — метод нахождения оптимальной последовательности действий. Предполагает обратную хронологию: первым определяется оптимальное действие на последнем шаге, затем определяются предшествующие оптимумы. Последним обнаруживается то действие, которое следует совершить в самом начале игры. Процедура продолжается до тех пор, пока не будет найден оптимум в каждом из информационных множеств, то есть в каждой из игровых ситуаций, доступных для восприятия игроком. С точки зрения математической оптимизации, точнее динамического программирования обратная индукция — один из методов решения уравнения Беллмана. В теории игр позволяет найти равновесие, совершенное по подыграм последовательной игры. Для поиска равновесия необходимо охарактеризовать оптимальные стратегии всех игроков, то есть применить обратную индукцию к каждому из индивидуальных деревьев, либо сконструировать общее дерево. В автоматическом планировании и диспетчеризации и автоматическом доказательстве теорем метод обратной индукции называется «обратным поиском» или «обратным выводом». В шахматной терминологии обратную индукцию называют ретроградным анализом. Обратная индукция столь же стара, сколь и сама теория игр. Джон фон Нейман и Оскар Моргенштерн применяли её для решения антагонистических игр. Их работа Theory of Games and Economic Behavior (1944) считается основополагающим текстом теории игр.