Cheatsheet
Теория игр — all topics on one page
Стратегические игры и равновесие Нэша
Основы теории игр: игроки, стратегии, выигрыши и равновесие Нэша
Когда ваш успех зависит от чужих решений → Формальное определение стратегической игры → Классификация игр → Знаковые примеры с матрицами выигрышей → Стратегии: чистые и смешанные → Числовой пример: Камень–Ножницы–Бумага → Приложения теории игр → Теория игр в стратегическом менеджменте и государственном управлении
Definitions
| Молчать (П2) | Предать (П2) | |
|---|---|---|
| -- | -- | -- |
| **Молчать (П1)** | (−1, −1) | (−5, 0) |
| **Предать (П1)** | (0, −5) | (−3, −3) |
| Свернуть | Не сворачивать | |
|---|---|---|
| -- | -- | -- |
| **Свернуть** | (0, 0) | (−1, +1) |
| **Не сворачивать** | (+1, −1) | (−10, −10) |
| К | Н | Б | |
|---|---|---|---|
| -- | -- | -- | -- |
| **К** | (0,0) | (+1,−1) | (−1,+1) |
| **Н** | (−1,+1) | (0,0) | (+1,−1) |
| **Б** | (+1,−1) | (−1,+1) | (0,0) |
- •N — конечное множество игроков {1, 2, ..., n}
- •Sᵢ — множество стратегий игрока i; стратегический профиль S = S₁ × S₂ × ... × Sₙ
- •uᵢ: S → ℝ — функция выигрыша каждого игрока i
Большинство жизненных задач решаются в одиночку: сколько учиться, как распределить бюджет, когда лечь спать. Но целый класс решений принципиально отличается — их результат зависит не только от ваших действий, но и от действий других людей. Водитель на дороге, компания при назначении цен, страна н...
Теория игр — математическая наука о принятии решений в ситуациях взаимозависимости. Основы заложили Джон фон Нейман и Оскар Моргенштерн в книге «Теория игр и экономическое поведение» (1944). Джон Нэш в 1950 году предложил концепцию равновесия, а в 1994 году получил за это Нобелевскую премию по эк...
Каждый игрок i выбирает стратегию sᵢ ∈ Sᵢ, и его выигрыш uᵢ(s₁, s₂, ..., sₙ) зависит от стратегий всех участников. Игрок стремится максимизировать свой выигрыш, зная, что остальные делают то же самое.
По сумме выигрышей: игры с нулевой суммой — выигрыш одного равен проигрышу другого (шахматы, покер); игры с ненулевой суммой — возможен взаимный выигрыш или проигрыш (переговоры, торговля).
Что такое «устойчивый» исход игры? → Теорема существования Нэша (1950) → Метод нахождения равновесия в смешанных стратегиях: принцип безразличия → Задача олигополии Курно: пример вычисления → Множественность равновесий и уточнения → Равновесие Нэша в реальной политике и бизнесе → Равновесие Нэша в антимонопольной практике и корпоративной стратегии
| Орёл (П2) | Решка (П2) | |
|---|---|---|
| -- | -- | -- |
| **Орёл (П1)** | (+1, −1) | (−1, +1) |
| **Решка (П1)** | (−1, +1) | (+1, −1) |
Представьте, что все игроки уже объявили свои стратегии. Когда никому не выгодно в одностороннем порядке менять свою стратегию? Именно это состояние и называется равновесием Нэша. Это не обязательно «лучший» исход для всех — это устойчивый, в том смысле, что у каждого есть стимул придерживаться е...
Формально, профиль стратегий s* = (s₁*, ..., sₙ*) является равновесием Нэша, если для каждого игрока i:
Здесь s₋ᵢ* означает стратегии всех остальных игроков, кроме i. Иными словами: при фиксированных стратегиях соперников sᵢ* — наилучший ответ для i.
Теорема: Любая конечная стратегическая игра (конечное число игроков и стратегий) имеет равновесие в смешанных стратегиях.
Логика «отсечения невыгодных действий» → Строгое и слабое доминирование → Алгоритм IESDS → Числовой пример: матрица 3×3 → Дилемма заключённого через доминирование → Ограниченная глубина стратегического мышления → Реальное приложение: ценообразование в авиации → Доминантные стратегии в проектировании рынков и аукционов
Definitions
| L | C | R | |
|---|---|---|---|
| -- | -- | -- | -- |
| **T** | (4,3) | (5,1) | (6,2) |
| **M** | (2,1) | (8,4) | (3,6) |
| **B** | (3,0) | (9,6) | (2,8) |
| L | R | |
|---|---|---|
| -- | -- | -- |
| **T** | (4,3) | (6,2) |
| **M** | (2,1) | (3,6) |
| **B** | (3,0) | (2,8) |
| L | R | |
|---|---|---|
| -- | -- | -- |
| **T** | (4,3) | (6,2) |
| **M** | (2,1) | (3,6) |
Прежде чем искать равновесие Нэша, полезно задать более простой вопрос: есть ли стратегии, которые никогда не выгодно применять? Такие стратегии называются доминируемыми: что бы ни делали соперники, другая стратегия всегда лучше. Рациональный игрок никогда не выберет доминируемую стратегию — можн...
Повторяя эту процедуру итерационно, мы иногда приходим к единственному исходу — равновесию. Этот метод требует не только рациональности каждого игрока, но и общего знания рациональности: я знаю, что ты рационален; ты знаешь, что я знаю; и так далее.
Строгое доминирование: Стратегия sᵢ строго доминирует sᵢ', если для всех s₋ᵢ ∈ S₋ᵢ: uᵢ(sᵢ, s₋ᵢ) > uᵢ(sᵢ', s₋ᵢ). Строго доминируемая стратегия никогда не выбирается рациональным игроком, вне зависимости от убеждений о соперниках.
Слабое доминирование: uᵢ(sᵢ, s₋ᵢ) ≥ uᵢ(sᵢ', s₋ᵢ) для всех s₋ᵢ, и хотя бы для одного s₋ᵢ неравенство строгое. Слабо доминируемые стратегии требуют более аккуратного обращения — устранение может зависеть от порядка.
Динамические игры и игры с неполной информацией
Деревья игр, обратная индукция, байесовские игры и совершенное равновесие
Почему статических игр недостаточно? → Игры в развёрнутой форме и деревья → Обратная индукция → Числовой пример: вход на рынок → Совершенное равновесие по подыграм → Повторяющиеся игры и кооперация → SPNE в корпоративной стратегии и переговорах → Совершенное равновесие по подыграм в корпоративной стратегии
Definitions
В реальном бизнесе и политике решения принимаются последовательно, причём более поздние игроки наблюдают ранние ходы. Компания решает выйти на рынок, зная, что действующая фирма затем может устроить ценовую войну. Стороны поочерёдно делают предложения на переговорах. Страны вводят санкции в ответ...
В таких ситуациях равновесие Нэша допускает «пустые угрозы» — действия, о которых объявлено, но которые не будут выполнены рационально. Концепция совершенного равновесия по подыграм (SPNE) устраняет такие угрозы.
Динамическая игра изображается деревом: узлы — точки принятия решений, рёбра — действия, листья — выигрыши. Дополнительно: информационные множества (узлы, между которыми игрок не может различить) описывают неполную информацию о ходе игры.
Подыгра — фрагмент дерева, начинающийся в одном узле (singleton информационное множество) и включающий все его поддеревья. Подыгра должна быть «замкнутой»: нельзя разрывать информационные множества.
Когда соперник — «загадка» → Тип, байесовская игра и байесовское равновесие → Числовой пример: аукцион первой цены → Сигнализация и скрининг → Рынок «лимонов» Акерлофа → Механизмы борьбы с асимметрией информации → Байесовские игры в финансах и корпоративном управлении → Байесовские игры в финансах и регулировании
- •Высокопроизводительный получает образование: W_H − c_H·e ≥ W_L
- •Низкопроизводительный не получает: W_L ≥ W_H − c_L·e
В реальных играх информация часто асимметрична: страховая компания не знает состояние здоровья клиента, инвестор — намерения менеджера, покупатель — себестоимость товара. Как анализировать стратегическое взаимодействие, когда игроки имеют частную информацию?
Хасаньи (Нобелевская премия 1994) предложил элегантное решение: ввести понятие типа игрока — его частной информации — и моделировать неполную информацию как случайный выбор природой типа каждого игрока.
Тип θᵢ игрока i — его частная характеристика (готовность платить, производственная функция, предпочтения к риску). Пространство типов Θᵢ; природа «выбирает» θ из совместного распределения μ(θ).
Байесовская игра в нормальной форме: ⟨N, (Sᵢ), (Θᵢ), μ, (uᵢ)⟩. Стратегия bᵢ: Θᵢ → Sᵢ — правило действия для каждого возможного типа.
Тень будущего меняет всё → Структура повторяющейся игры → Ключевые стратегии и числовой пример → Народная теорема → Олигополия и молчаливый сговор → Повторяющиеся игры и институциональное доверие → Устойчивость кооперации в международных отношениях и международной торговле
| С (сотрудничество) | П (предательство) | |
|---|---|---|
| -- | -- | -- |
| **С** | (3, 3) | (0, 5) |
| **П** | (5, 0) | (1, 1) |
Когда два агента взаимодействуют один раз, дилемма заключённого ведёт к взаимному предательству. Но в реальных бизнес-отношениях компании встречаются снова и снова — квартальные переговоры, повторные закупки, долгосрочные контракты. В таких условиях «тень будущего» — ожидание повторных взаимодейс...
Повторяющиеся игры — модель, формализующая этот механизм. Они объясняют, почему честность может быть стратегически выгодна, а молчаливый сговор возникает без явных договорённостей.
Стандартная игра G (stage game) играется в периоды t = 1, 2, 3, ... Игрок i дисконтирует будущее с фактором δᵢ ∈ (0, 1): выигрыш в следующем периоде стоит сейчас δ раз меньше. Общий (нормированный) выигрыш:
Нормировка на (1−δ) делает Vᵢ сопоставимым с выигрышем в одной стадии. При δ → 1: игрок терпелив, высоко ценит будущее. При δ → 0: «живёт только сегодня», будущее не важно.
Кооперативная теория игр
Ядро, значение Шепли, нуклеолюс и концепции устойчивости коалиций
Когда переговоры важнее стратегии → Характеристическая функция → Ядро: устойчивое распределение → Значение Шепли: справедливое распределение → Нуклеолюс: минимизация недовольства → Приложения → Значение Шепли в корпоративном управлении и политической экономии
Definitions
В кооперативной теории игр вопрос другой: не «как игроки стратегически взаимодействуют», а «как они делят совместно созданный выигрыш». Предполагается, что игроки могут заключать обязывающие соглашения — главный вопрос в том, какое распределение «справедливо» и «устойчиво».
Примеры: распределение прибыли в совместном предприятии; разделение затрат на строительство совместной инфраструктуры; распределение власти в политической коалиции.
TU-игра (с трансферабельной полезностью) задаётся парой (N, v): N = {1, ..., n} — игроки; v: 2^N → ℝ — характеристическая функция (v(S) — максимальный совместный выигрыш коалиции S). Обычно v(∅) = 0.
Супераддитивность: v(S∪T) ≥ v(S) + v(T) при S∩T = ∅. Это условие «объединяться выгодно» — стандартное для большинства экономических приложений.
Когда ядро недостаточно → Нуклеолюс: минимизация недовольства → Устойчивые множества фон Неймана–Моргенштерна → Теория паросочетаний: рынки без цен → Ядро и нуклеолюс в разделе затрат и переговорах о слиянии
Definitions
- •Внутренняя устойчивость: Никакое распределение x ∈ V не доминирует y ∈ V (через некоторую коалицию S: Σᵢ∈S xᵢ ≤ v(S) и xᵢ > yᵢ для всех i ∈ S)
- •Внешняя устойчивость: Для каждого x ∉ V найдётся y ∈ V, доминирующее x
Ядро — привлекательная концепция, но у неё есть два недостатка: оно может быть пустым (никакое устойчивое распределение не существует) и неединственным (много устойчивых распределений). Нуклеолюс и устойчивые множества — альтернативные концепции, каждая с особой логикой.
Для распределения x и коалиции S определим избыток e(S, x) = v(S) − Σᵢ∈S xᵢ. Положительный избыток: коалиция S может «сделать лучше» для себя, если отколется. Отрицательный: коалиция «в проигрыше» при отколе.
Нуклеолюс — распределение x, лексикографически минимизирующее вектор избытков всех коалиций, упорядоченных по убыванию. Сначала минимизируем максимальный избыток, затем при фиксированных максимально «довольных» — следующий, и т.д.
Шмайдлер (1969): нуклеолюс существует и единственен для любой игры. Если ядро непусто — нуклеолюс в нём.
Рынки, где «деньги не всё» → Формальная постановка задачи о стабильном браке → Алгоритм Гейла–Шепли → Числовой пример (полное решение) → Стратегические свойства → Реальные применения → Двусторонние рынки: платформенная экономика и стратегический дизайн
На большинстве рынков цена уравновешивает спрос и предложение. Но существуют рынки, где денежные переводы невозможны или нежелательны по этическим или правовым причинам: распределение студентов по школам, резидентов по больницам, донорских органов по пациентам. Здесь нужны механизмы, обеспечивающ...
Теория паросочетаний — математический инструмент для таких рынков. Алвин Рот и Ллойд Шепли получили Нобелевскую премию 2012 года за её развитие и практическое применение.
Дано n мужчин M = {m₁, ..., mₙ} и n женщин W = {w₁, ..., wₙ}. Каждый мужчин mᵢ имеет строгое линейное упорядочение предпочтений над W; каждая женщина wⱼ — над M.
Паросочетание μ: M → W ∪ {∅} — взаимно однозначное отображение (каждый получает не более одного партнёра).
Механизм-дизайн и теория аукционов
Проектирование правил игры, теорема откровения, аукционные форматы
«Инженерная» ветвь теории игр → Проблема: частная информация → Принцип откровения → VCG-механизм → Теорема Майерсона–Сэттертвейта → Аукционы спектра — теория в действии → Механизм VCG в интернет-рекламе и аукционах спектра
Formulas
Классическая теория игр анализирует существующие правила: каков равновесный исход? Механизм-дизайн решает обратную задачу: какие правила ввести, чтобы рациональное поведение игроков привело к желаемому социальному результату?
Аналогия: классическая теория игр — физика (описывает мир), механизм-дизайн — инженерия (проектирует мир). Леонид Гурвич, Эрик Маскин и Роджер Майерсон получили Нобелевскую премию 2007 года за основополагающие вклады.
Примеры задач механизм-дизайна: как продать государственные частоты телевидения с максимальной выручкой? Как организовать торги на электрическом рынке для минимизации затрат? Как распределить ресурсы здравоохранения «справедливо» при частной информации пациентов?
Ключевой барьер — агенты имеют частную информацию (тип θᵢ), которую планировщик не наблюдает: готовность платить, производственная функция, склонность к риску. Агенты могут лгать о своём типе ради выгоды.
Аукционы как механизмы распределения → Основные форматы аукционов → Теорема об эквивалентности выручки → Оптимальный аукцион Майерсона → Проклятие победителя → Аукционная теория в оценке бизнеса и прокьюременте
Аукционы существуют тысячи лет: рабы в Вавилоне, рыба в японских гаванях, казначейские облигации, частоты спектра, интернет-реклама. Современная аукционная теория — точная математика о том, как участники ставят ставки и сколько выручает продавец.
Ключевой вопрос: при одних и тех же предпочтениях участников разные форматы аукциона дают одинаковую или разную выручку продавцу? Интуиция: «большие ставки = больше выручки» не всегда верна — форматы аукциона глубоко влияют на стратегии.
Аукцион первой цены (FPSB): Закрытые ставки; побеждает максимальная, победитель платит свою ставку. Стратегия: нет доминирующей — нужно «жать» ставку ниже оценки. Оптимальное жатие зависит от числа участников и распределения оценок.
Аукцион второй цены (Vickrey, 1961): Закрытые ставки; побеждает максимальная, победитель платит вторую по величине. Доминантная стратегия: ставить истинную оценку θᵢ! Это DSIC-механизм. Почему: при ставке выше θᵢ — риск выиграть и переплатить. При ставке ниже — риск упустить выгодную сделку. Став...
Границы возможного: что нельзя достичь правилами → Теорема Эрроу о невозможности (1951, Нобель 1972) → Теорема Гиббарда–Сэттертвейта → Механизм-дизайн при ограниченной рациональности → Оптимальное регулирование монополии → Теория голосования в избирательном праве и корпоративном управлении
Механизм-дизайн сталкивается с фундаментальными барьерами. Даже при самом умном дизайне правил есть вещи, которые невозможно реализовать при стратегически мыслящих агентах. Теоремы невозможности очерчивают, что принципиально недостижимо.
Это не просто абстрактная математика: теоремы Эрроу и Гиббарда–Сэттертвейта объясняют, почему «идеальной» системы голосования не существует, и позволяют сознательно выбирать, какие несовершенства допустимы.
Контекст: n ≥ 2 избирателей, m ≥ 3 альтернатив. Нужна «рациональная» агрегация индивидуальных предпочтений в социальный выбор.
Четыре аксиомы: 1. Полнота и транзитивность результата. 2. Принцип Парето: если все предпочитают x над y → социальный порядок предпочитает x над y. 3. IIA (независимость нерелевантных альтернатив): социальный выбор между x и y зависит только от индивидуальных предпочтений x vs y, не от позиций др...
Эволюционная теория игр
ЭСС, динамика репликатора, обучение в играх и поведенческие расширения
Эволюция вместо рациональности → Эволюционно стабильные стратегии (ЭСС) → Динамика репликатора → Числовой пример: игра «Ястреб–Голубь» → Многопопуляционные игры и применения → Эволюционная теория игр в биологии и экономике
| Ястреб | Голубь | |
|---|---|---|
| -- | -- | -- |
| **Ястреб** | (V−C)/2 = −1 | V = 4 |
| **Голубь** | 0 | V/2 = 2 |
Классическая теория игр предполагает полностью рациональных игроков, знающих равновесие. Эволюционная теория игр (ЭТИ) предлагает альтернативный фундамент: вместо рациональности — отбор. Особи с более высокой приспособленностью (выигрышем) размножаются быстрее. Равновесие возникает не из рассужде...
Мэйнард Смит и Прайс (1973) разработали ЭТИ для объяснения поведения животных. Затем концепции перенесли на экономику, социологию, информатику. Главный вопрос: какие стратегии «выживают» в популяции?
Определение: Стратегия σ* является ЭСС, если при достаточно малом вторжении мутантов со стратегией σ ≠ σ* «резидентная» популяция σ* «вытесняет» мутантов:
Условия ЭСС (достаточные): 1. u(σ*, σ*) > u(σ, σ*) для всех σ ≠ σ* — строгое равновесие Нэша, ИЛИ 2. u(σ*, σ*) = u(σ, σ*) И u(σ*, σ) > u(σ, σ) — при «ничьей» против резидентов σ* лучше против мутантов
Как игроки «находят» равновесие? → Фиктивная игра (Fictitious Play) → Регрет-минимизация → Алгоритм Multiplicative Weights Update (MWU) → Поведенческая теория игр → Реальные приложения → Обучение в играх и поведенческая экономика в практике
| L | R | |
|---|---|---|
| -- | -- | -- |
| **T** | (2,2) | (0,0) |
| **B** | (0,0) | (1,1) |
Теория говорит, что в равновесии Нэша никому не выгодно отклоняться. Но как игроки попадают в равновесие? Вряд ли каждый заранее решает систему уравнений. Реальный процесс — адаптивное обучение: наблюдение за прошлым, корректировка стратегии, постепенное приближение к равновесию.
Модели обучения разрушают представление о мгновенно рациональных агентах. Вместо этого — итеративный процесс, который может сходиться к равновесию или нет.
Правило: В каждом периоде t игрок i: (1) наблюдает частоты прошлых действий соперников; (2) формирует убеждения как эмпирические частоты; (3) выбирает наилучший ответ на эти убеждения.
Формально: пусть n_j^t(s) — число раз, когда j сыграл s до t. Убеждение: π_j^t(s) = n_j^t(s)/t. Выбор: a_i^t = argmax_s u_i(s, π_{-i}^t).
От абстракции к практике → Олигополия: два канонических подхода → Входные барьеры и угроза входа → Отраслевая стратегия: матрица конкурентов → Переговоры через теорию игр: модель Рубинштейна → Аукционы на практике: дизайн частотных торгов → Теория игр в стратегическом менеджменте и регуляторной политике
| R&D (конкурент) | Нет R&D (конкурент) | |
|---|---|---|
| -- | -- | -- |
| **R&D (мы)** | (2, 2) | (7, 0) |
| **Нет R&D** | (0, 7) | (4, 4) |
Все концепции теории игр — равновесие Нэша, SPNE, ЭСС, механизм-дизайн — разрабатывались как абстрактные инструменты анализа. Но их настоящая ценность раскрывается в приложениях: объяснение реального рыночного поведения и формирование стратегических решений компаний.
Модель Курно (конкуренция по выпуску): Фирмы одновременно выбирают объём производства q₁, q₂. Равновесие: q* = (a−c)/(3b) для двух фирм; цена P* = (a+2c)/3. При n фирмах: P → c при n → ∞ (сходимость к конкурентному рынку). Применение: нефтяная отрасль, авиация (выбор мощностей/рейсов).
Модель Бертрана (конкуренция по ценам): Фирмы выбирают цену; покупатели идут к более дешёвому. При однородном товаре равновесие: P = c (конкурентная цена!) — «Парадокс Бертрана». Двух фирм достаточно для конкурентного рынка. Применение: рынок авиабилетов онлайн, банковские депозиты, рынок товаров...
Конкуренция Штакельберга: Фирма-лидер первой выбирает q₁, наблюдатель–последователь выбирает q₂ зная q₁. SPNE: лидер q₁* = (a−c)/(2b) (больше, чем в Курно!), последователь q₂* = (a−c)/4b. Лидер-преимущество: первый ход даёт больший выпуск и прибыль.