Равновесие, совершенное по подыграм¶

Равновесие, совершенное по подыграм — это понятие теории игр, обозначающее такой профиль стратегий в многошаговой игре (или игре с последовательными ходами), который является равновесием Нэша в каждой подыгре исходной игры. Иными словами, это уточнение (или «усиление») равновесия Нэша, требующее, чтобы стратегии игроков оставались оптимальными не только в начале игры, но и в любой её возможной точке — независимо от того, была ли она достигнута в ходе реального развития событий.

¶История и происхождение понятия

Теория игр как математическая дисциплина начала формироваться в середине XX века. Основополагающую роль сыграла работа Джона фон Неймана и Оскара Моргенштерна «Теория игр и экономического поведения» (1944). В 1950 году Джон Нэш ввёл понятие равновесия Нэша — ситуации, в которой ни один игрок не может улучшить свой выигрыш, изменив свою стратегию в одностороннем порядке. Однако равновесие Нэша не учитывает динамику игры: в многошаговых играх оно может включать «неправдоподобные» угрозы, которые игроки не станут выполнять при реальном развитии событий.

Понятие равновесия, совершенного по подыграм, было формализовано в 1965 году Райнхардом Зельтеном. В своей работе «Spieltheoretische Behandlung eines Oligopolmodells mit Nachfrageträgheit» (нем. «Теоретико-игровая обработка модели олигополии с инерцией спроса») он предложил этот критерий для устранения нереалистичных равновесий Нэша в последовательных играх. За вклад в теорию игр Зельтен, наряду с Джоном Нэшем и Джоном Харсаньи, получил Нобелевскую премию по экономике в 1994 году.

¶Основные определения

¶Игра с совершенной информацией

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

¶Подыгра

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

¶Равновесие, совершенное по подыграм

Формально: профиль стратегий \( s \) является равновесием, совершенным по подыграм, если для каждой подыгры \( G' \) исходной игры \( G \) ограничение \( s \) на \( G' \) является равновесием Нэша в \( G' \). Это означает, что стратегии игроков должны быть взаимно оптимальными в любой точке игры, включая те, которые не были достигнуты в ходе реального развития (так называемые «неравновесные» пути).

¶Метод нахождения: обратная индукция

Для конечных игр с совершенной информацией равновесие, совершенное по подыграм, находится с помощью обратной индукции. Алгоритм:

1. Рассматриваются последние ходы игры (конечные узлы).
2. Для каждого предпоследнего узла определяется, какой ход выберет игрок, максимизирующий свой выигрыш (с учётом того, что в последующих узлах игроки также будут действовать рационально).
3. Процесс повторяется, двигаясь от конца игры к началу.

В результате получается набор стратегий, которые являются оптимальными на каждом шаге. Этот метод гарантирует, что угрозы, не являющиеся правдоподобными (например, обещание наказать соперника ценой собственного проигрыша), не войдут в равновесие.

¶Примеры

¶Пример 1: «Ультиматум»

Рассмотрим игру, в которой первый игрок предлагает разделить 100 рублей, а второй может либо принять предложение, либо отвергнуть его (в случае отказа оба получают 0). Если первый предлагает \( x \) рублей второму, а себе оставляет \( 100 - x \), то:

• Второй игрок в подыгре, где ему предложили \( x \), выбирает: принять (выигрыш \( x \)) или отвергнуть (выигрыш 0). Рациональный выбор — принять, если \( x > 0 \), и безразлично, если \( x = 0 \) (обычно предполагается, что при равенстве игрок выбирает принятие).
• Первый игрок, зная это, предложит минимально возможную положительную сумму, например 1 рубль, и получит 99 рублей.

Равновесие, совершенное по подыграм: первый предлагает 1 рубль, второй принимает. В этом равновесии нет неправдоподобных угроз (например, второй не угрожает отвергнуть предложение, если оно меньше 50 рублей, так как это нерационально).

¶Пример 2: «Вход на рынок»

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

• B не входит: A получает 10, B — 0.
• B входит, A сосуществует: A — 5, B — 5.
• B входит, A начинает войну: A — 1, B — -1.

Равновесие Нэша: существует два равновесия — (B входит, A сосуществует) и (B не входит, A начинает войну). Однако второе равновесие основано на угрозе A начать войну, что нерационально: если B уже вошёл, A выгоднее сосуществовать (5 > 1). Поэтому равновесие, совершенное по подыграм, только одно: B входит, A сосуществует.

¶Свойства и ограничения

¶Существование

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

¶Единственность

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

¶Критика

• Предположение о рациональности: метод обратной индукции требует, чтобы все игроки были абсолютно рациональны и знали о рациональности других. В реальных ситуациях люди могут отклоняться от такого поведения (например, в экспериментах с игрой «Ультиматум» игроки часто отвергают несправедливые предложения).
• Несовершенная информация: в играх с несовершенной информацией (например, когда игроки не знают точных выигрышей друг друга) понятие равновесия, совершенного по подыграм, требует дополнительных уточнений, таких как секвенциальное равновесие или совершенное байесовское равновесие.

¶Применение

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

• Экономика: анализ олигополистических рынков, переговоров, аукционов, контрактов.
• Политология: моделирование международных конфликтов, выборов, законодательных процессов.
• Биология: эволюционная теория игр, анализ поведения животных (например, в играх типа «ястреб — голубь»).
• Информатика: алгоритмы для многоагентных систем, искусственный интеллект (например, в покере или шахматах).

¶Связь с другими понятиями

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

¶Источники

• Зельтен Р. «Spieltheoretische Behandlung eines Oligopolmodells mit Nachfrageträgheit» (1965).
• Нэш Дж. «Equilibrium Points in N-Person Games» (1950).
• Майерсон Р. «Game Theory: Analysis of Conflict» (1991).
• Осборн М., Рубинштейн А. «A Course in Game Theory» (1994).
• Фуденберг Д., Тироль Ж. «Game Theory» (1991).