Теория игр

Набор стратегий, при котором ни один игрок не выигрывает от одностороннего отклонения. Джон Нэш (1950). Нобелевская премия (1994). Фильм «Игры разума».

Английский (восходящий), голландский (нисходящий), закрытый первой/второй цены (Викри). Теорема эквивалентности доходов. Нобелевская: Вильсон и Милгром (2020).

Нормальная, или стратегическая, форма записывает игру через игроков, множество стратегий каждого и выигрыш каждого возможного сочетания выбранных стратегий. Она удобна, когда игроки выбирают одновременно или каждый не видит выбор другого; матрица «строки—столбцы» — самый простой пример такого представления.

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

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

Такое представление сохраняет порядок ходов и позволяет анализировать продолжение игры после каждого события. Его можно преобразовать в нормальную форму, но при этом дерево и временная структура выбора могут стать менее наглядными.

Чистая стратегия — полный план игрока, задающий одно действие в каждом информационном множестве, где ему может понадобиться ход. В игре с одним ходом это выбор действия; в развернутой игре план охватывает также ситуации, которые фактически не возникнут. При совершенной информации каждому информационному множеству соответствует один узел, поэтому «действие в каждом узле» допустимо лишь в этом частном случае.

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

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

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

Наилучший ответ — стратегия игрока, максимизирующая его выигрыш при заданных стратегиях остальных. Соперники могут использовать чистые или смешанные стратегии; тогда выигрыш понимается как ожидаемый. Если несколько стратегий дают один максимальный результат, каждая из них является наилучшим ответом.

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

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

Доминирующая стратегия остаётся лучшей независимо от того, что выберут другие, но во многих играх её нет. Равновесие, построенное для всех доминирующих стратегий, требует больше, чем обычное равновесие Нэша.

Итеративное исключение доминируемых стратегий упрощает игру, удаляя варианты, которые игроку невыгодны по сравнению с другой стратегией. После удаления анализ повторяют в сокращённой игре; иногда это приводит к единственному оставшемуся профилю.

Нужно уточнить, исключаются ли только строго или также слабо доминируемые стратегии. При слабом доминировании порядок удаления может менять итог, поэтому метод не всегда даёт единственное решение и не равен поиску равновесия Нэша.

Байесовская игра описывает ситуацию, когда участники не знают важную характеристику друг друга — например, издержки, качество товара или готовность к риску. Эту скрытую характеристику называют типом игрока; модель задаёт возможные типы и вероятности, с которыми участники считают их возможными.

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

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

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

Кооперативная теория игр изучает ситуации, в которых участники могут образовывать коалиции и совместно создавать ценность. Модель обычно задаёт, какой выигрыш доступен каждой коалиции, а затем анализирует его распределение; переговоры и принуждение к соглашению могут оставаться за пределами модели.

Ядро проверяет, существует ли распределение, от которого ни одна коалиция не предпочитает отклониться; значение Шепли делит ценность по средним предельным вкладам. Эти решения отвечают разным критериям и не описывают настольные игры, где участники совместно играют против игрового сценария.

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

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

Коррелированное равновесие возникает, когда игроки получают рекомендации от общего сигнала или устройства и каждому выгодно следовать своей рекомендации с учётом уже известного ему сигнала. Рекомендации могут быть связаны друг с другом, поэтому действия игроков не обязаны быть независимыми.

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

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

Такой результат отличается от одновременного выбора и зависит от возможности достоверно зафиксировать первый ход. Примеры используют для моделирования конкуренции фирм, но конкретные выводы зависят от функции спроса и других предположений модели.

Минимаксная теорема фон Неймана относится к конечным двухсторонним играм с нулевой суммой, где выигрыш одного игрока является потерей другого. При разрешённых смешанных стратегиях максимальный гарантированный результат одного игрока равен минимальному результату, который может навязать другой; это общее значение игры.

Теорема даёт математическое основание для оптимальных смешанных стратегий в таких играх. Условия важны: результат нельзя автоматически переносить на игры с несколькими сторонами или ненулевой суммой.

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

Для таких игр исследуют равновесия Нэша, Парето-эффективные исходы и модели переговоров. Эти критерии отвечают на разные вопросы и могут указывать на разные исходы, поэтому без дополнительного правила обычно нет единственного универсального решения.