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

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

Эталонный расчёт — ультиматум: делёж $100$ рублей. Отвечающий сравнивает предложение $x>0$ с нулём и принимает любое положительное, значит предлагающему выгоден минимум $x=1$, и он оставляет себе $99$. Результат спорит с экспериментами: люди наказывают жадность, — но логика дерева безупречна. Теорема Зермело добавляет: конечные игры с полной информацией решаются в чистых стратегиях. Структура дерева — в статье дерево игры, формы игры — во введении в теорию игр, обходы вершин — в материале деревья и алгоритмы, итоговый профиль — в статье равновесие Нэша.