Обратная индукция: обязательства, шпионы и преимущество первого хода

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

Суть простыми словами

Ходить первым выгодно не всегда. Первый ход выручает, только если его нельзя отменить и соперник его видит. Иногда лучше ходить вторым и сначала посмотреть на чужой ход. А иногда лишнее знание даже вредит: если соперник знает, что ты подглядываешь, он покажет тебе то, что выгодно ему.

Что было на лекции

• Полак сделал модель Курно пошаговой: фирма 1 выбирает объём выпуска первой, фирма 2 видит его и отвечает (модель Штакельберга). Решают с конца.
• Опросы. Большинство верно решило, что фирма 1 будет выпускать и зарабатывать больше. Довод студента: старый объём ей доступен, раз она его сменила, значит, так выгоднее. Про общий выпуск зал разделился. Студент Энди решил по наклону графика: фирма 1 добавляет больше, чем убирает фирма 2. Цена падает, фирма 2 теряет, покупатели выигрывают.
• Расчёт: лидер выпускает (A−C)/2B, последователь (A−C)/4B, при одновременных ходах каждый (A−C)/3B.
• Объявить объём заранее мало: нет надёжного обязательства (студент Патрик). Мердок и владелец NBC открывают газеты в новом городе: обещания не в счёт, нужна построенная типография. Невозвратные затраты делают обязательство настоящим.
• Шпион. У Мердока свой человек в совете директоров NBC, и NBC об этом знает. Крис предложил подсунуть ложный план. Усман предложил ответ лучше: теперь NBC фактически ходит первой. Строй большую типографию, шпион передаст, и Мердоку придётся уступить. Шпион навредил хозяину.
• Выводы. Одновременность или очерёдность игры задаёт информация, а не время. В играх лишняя информация, как и лишние варианты (сожжённые корабли с прошлой лекции), может навредить.
• Полак высмеял бизнес-книжки, где первым быть выгодно всегда. В «камень, ножницы, бумагу» лучше ходить вторым. Вторым выгодно покупать новую технику или выходить на новый рынок: учишься на чужих ошибках. В дележе «я режу, ты выбираешь» преимущества нет ни у кого.
• Ним: две кучки камней, за ход берёшь сколько угодно из одной, кто взял последний, победил. Кучки 7 и 4: первым ходил именинник и победил. Кучки 13 и 7: Кристин ходила первой, каждым ходом уравнивала кучки и победила. Правило от студента: кучки неравны, ходи первым и уравнивай; равны, будь вторым.

Главные понятия

• Обратная индукция (backward induction) — решаем игру с конца: сначала ответ последнего игрока, потом выбор тех, кто ходил раньше.
• Модель Штакельберга (Stackelberg model) — лидер выбирает выпуск первым, последователь отвечает. Лидер выпускает и зарабатывает больше.
• Обязательство (commitment) — ход, который нельзя отменить. Без него «первый ход» остаётся пустыми словами.
• Невозвратные затраты (sunk costs) — деньги, которые уже не вернуть. Они делают обязательство правдоподобным.
• Преимущество первого и второго хода (first-/second-mover advantage) — где-то выгодно начинать, где-то отвечать, а где-то всё равно.

Зерно для создателя игр

• Порядок ходов служит рычагом баланса. Проверь, кому выгодно начинать в твоей игре. В го белые получают коми, бонусные очки за то, что чёрные начинают. В Hex есть «правило пирога»: первый делает ход, второй решает, забрать его себе или нет. Это то же «я режу, ты выбираешь».
• Вес решения рождается из необратимости. Если постройку можно бесплатно отменить, первый ход ничего не значит. Важный выбор делай дорогим, видимым и окончательным. Объявления в чате дёшевы, как слова Мердока.
• Одновременность создаёт сокрытие, а не таймер. Если оба кладут карты рубашкой вверх и вскрывают вместе, преимущество второго хода исчезает. Онлайн-игре в «камень, ножницы, бумагу» нужно прятать выбор первого.
• Разведка обоюдоостра: если соперник знает, что ты его видишь, он нарочно покажет решимость. Оставь место для блефа.
• Простой трюк убивает игру. Кто понял, что в Ниме надо уравнивать кучки, тому скучно. Головоломке такое открытие дарит радостное «ага», а соревновательной игре вредит. Ищи такие трюки на плейтестах.

Мини-игра для урока

«Ним на двух кучках» (игра Полака). 2 игрока, 20 монет или палочек, 10 минут.

• Две кучки. За ход берёшь из одной кучки сколько угодно предметов, хотя бы один. Забрал последний, победил.
• Раунд 1: кучки 7 и 4, три партии, меняясь, кто начинает. Раунд 2: кучки 5 и 5, ещё три партии.
• Вопрос со звёздочкой: один раскладывает 12 предметов на две кучки, другой выбирает, ходить первым или вторым. Как разложить, чтобы не проиграть?
• Что заметить: исход решён до первого хода. При неравных кучках первый побеждает, если уравнивает их каждым ходом. При равных побеждает второй, зеркально повторяя ходы. Выгода первого хода зависит от стартовой позиции. В вопросе со звёздочкой раскладчик всегда проигрывает знающему трюк: «правило пирога» честно, только пока игру нельзя просчитать.
• В браузере: компьютер знает трюк и предлагает ученику выбрать, кто начинает.

Ошибки и заблуждения

• «Первым ходить всегда выгодно». Нет: в «камень, ножницы, бумагу» выгоднее отвечать, а в Ниме всё решает стартовая позиция.
• «Я объявил план, значит, уже сходил первым». Слова ничего не стоят. Преимущество даёт только видимый и необратимый шаг.
• «Знать больше всегда лучше». Одному человеку да, в игре нет: если соперник знает про твоего шпиона, он сам выберет, что тебе показать.

Для продвинутых

• Генрих фон Штакельберг, «Marktform und Gleichgewicht» (1934). Суммарный выпуск у Штакельберга 3(A−C)/4B, у Курно 2(A−C)/3B.
• В задаче одного человека бесплатная информация не вредит, в игре может. Классика о пользе обязательств и «связанных рук»: Томас Шеллинг, «Стратегия конфликта» (1960), Нобелевская премия 2005 года.
• Ним с любым числом кучек решил Чарльз Бутон (1901) через побитовое «исключающее или» (ним-сумму). Общая теория таких игр: теорема Шпрага–Гранди (1935–1939).