Игры в развёрнутой форме

«Уволю работника, если он не согласится». «Мы введём санкции, если условия не выполнят». Угрозы в переговорах - повсюду. Но не все угрозы одинаково убедительны. Развёрнутая форма и обратная индукция дают математический ответ: угроза работает только если её выгодно выполнить. Это перевернуло теорию переговоров, дипломатию и корпоративную стратегию.

• **Переговоры о зарплате:** кто делает первое предложение (якорный эффект), кто имеет BATNA лучше - всё определяется структурой дерева игры и обратной индукцией
• **Антимонопольная политика:** Entry Deterrence - модель того, почему угроза ценовой войны иногда сдерживает конкурентов, а иногда нет (зависит от credibility)
• **Покер AI (Libratus, Pluribus):** бот Carnegie Mellon победил лучших игроков в мире, решая задачу с информационными множествами через Counterfactual Regret Minimization

Предварительные знания

• Zero-Sum Games

Дерево игры

Рассмотрим переговоры о зарплате: сначала работодатель делает предложение, потом кандидат принимает или отклоняет. Нормальная форма (матрица) не показывает, кто ходит первым. Развёрнутая форма - это дерево решений, где каждый узел - чья-то очередь ходить, каждое ребро - выбор действия, а листья - финальные выигрыши.

Определяется элементами: N - игроки, H - узлы истории, Z - терминальные узлы (листья), χ(h) - доступные действия в узле h, ρ(h) - чья очередь ходить, σ - информационные множества, u: Z → Rⁿ - выигрыши в листьях.

Ключевое отличие развёрнутой формы: она явно показывает **информацию** каждого игрока. В шахматах оба видят всю доску - это игра с совершенной информацией. В покере карты соперника скрыты - неполная информация. Структура информационных множеств принципиально меняет оптимальные стратегии.

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

Чтобы найти оптимальную стратегию в дереве игры, рассуждай с конца. В последних узлах выбор очевиден: каждый игрок выбирает действие с лучшим выигрышем. Зная это, можно «свернуть» дерево назад - предпоследние узлы решаются, зная, что будет дальше. И так до корня. Это обратная индукция (backward induction).

1. Найди все предтерминальные узлы (чьи дети - листья) 2. В каждом таком узле игрок выбирает действие с max выигрышем 3. Заменяй узел на соответствующий выигрыш 4. Повторяй до корня Результат: стратегический профиль - совершенное равновесие по подыграм (SPE).

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

Равновесие совершенное по подыграм (SPE)

Нормальная форма игры «Ультиматум» имеет много равновесий Нэша: например, игрок 1 предлагает 10%, игрок 2 угрожает отвергнуть всё меньше 50%. Но это NE нереалистично: если игрок 1 всё-таки предложил 10%, игроку 2 рациональнее принять (10% > 0%). Угроза была «пустой». Равновесие совершенное по подыграм (SPE) запрещает такие угрозы.

Подыгра (subgame) - часть дерева, начинающаяся с одного узла и включающая всех его потомков. Стратегический профиль является SPE, если он является равновесием Нэша в КАЖДОЙ подыгре. SPE ⊂ NE: каждое SPE - NE, но не каждое NE - SPE.

SPE введено Рейнхардом Зельтеном (Нобель 1994) как уточнение NE для игр с последовательными ходами. Оно устраняет равновесия, основанные на «пустых угрозах» - действиях, которые игроку невыгодно выполнять, когда до них доходит очередь.

Информационные множества

В покере игрок делает ставку, не зная карт соперника. С точки зрения теории игр: игрок не может различить несколько узлов дерева - «был ли у соперника туз или нет». Такая группа неразличимых узлов называется информационным множеством. Стратегия в игре с неполной информацией - план действий для каждого информационного множества.

Совершенная информация: каждое информационное множество содержит ровно один узел - игрок знает историю точно (шахматы, Go). Несовершенная информация: есть информационные множества из нескольких узлов (покер, переговоры). SPE применимо строго только к совершенной информации. Для несовершенной - Perfect Bayesian Equilibrium (PBE).

Информационные множества объясняют, почему блеф в покере рационален. Если игрок ставит только с сильной рукой - соперник всегда сбрасывает при ставке. Оптимальная стратегия: иногда блефовать с нужной частотой, чтобы соперник был безразличен между call и fold. Это классическое смешанное равновесие.

Ключевые идеи

• **Развёрнутая форма (дерево игры)** явно моделирует порядок ходов и информацию каждого игрока
• **Обратная индукция:** решение от листьев к корню - находит оптимальную стратегию в играх с совершенной информацией
• **SPE:** запрещает «нереалистичные угрозы» - действия, невыгодные к исполнению в соответствующей подыгре
• **Информационные множества:** моделируют неполную информацию; блеф в покере - рациональное смешанное равновесие

Связанные темы

Развёрнутая форма - основа для анализа последовательных переговоров и механизмов:

• Равновесие Нэша — SPE - уточнение NE для игр с порядком ходов
• Mechanism Design — Механизмы часто используют последовательные ходы и revelation principle
• Теория аукционов — Аукционы - игры с заявками при неполной информации о ценности соперников

Вопросы для размышления

• Рубинштейновский торг показывает: чем более нетерпелив игрок (высокий дисконт будущего), тем слабее его позиция на переговорах. Как это применимо к реальным переговорам о зарплате или сделкам M&A?
• «Пустые угрозы» в дипломатии - частое явление. Можно ли привести примеры, когда угроза оказалась non-credible? Почему это произошло?
• Покер - игра с несовершенной информацией. Почему человек-профессионал может иметь преимущество над простым ботом, но проигрывает Libratus? Что именно делает AI-бот принципиально по-другому?

Связанные уроки

• alg-21-dp