Теория игр

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

Историческое развитие

Понимание исторического контекста помогает оценить значение основных концепций теории игр.

Основы теории игр заложил Джон фон Нейман с публикацией теоремы о минимаксе в 1928 году, доказав, что в любой конечной антагонистической игре существует оптимальная стратегия [2]. Фундаментальная монография «Теория игр и экономическое поведение» была написана фон Неймаром совместно с Оскаром Моргенштерном в 1944 году, став отправной точкой для всей современной теории [3].

Джон Нэш в 1950 году доказал существование равновесия в смешанных стратегиях для произвольных конечных игр (не только антагонистических), концепция которого получила его имя и стала центральной в современной теории [1]. За эту работу Нэш был удостоен Нобелевской премии по экономике в 1994 году.

Джон Мейнард Смит развил теорию эволюционных игр в 1970-х годах, применив игровые модели к биологии и популяционной динамике [4]. Эти идеи позже вдохновили исследования в области адаптивных и самообучающихся систем.

В современной информатике теория игр получила новое значение с развитием мультиагентных систем и обучения с подкреплением. Алгоритмы AlphaGo и pokerbots демонстрируют, что игровые концепции критичны для разработки мощных ИИ-систем.

Основные понятия

Формальная модель игры

Игра в нормальной форме — это кортеж:

$G = (N, \{S_i\}_{i \in N}, \{u_i\}_{i \in N})$

где:

$N = \{1, 2, \ldots, n\}$ — множество игроков;
$S_i$ — множество чистых стратегий игрока $i$ ;
$u_i : S_1 \times S_2 \times \dots \times S_n \to \mathbb{R}$ — функция выигрыша (полезности) игрока $i$ .

Каждый игрок независимо выбирает стратегию $s_i \in S_i$ . Совместный выбор $s = (s_1, \dots, s_n)$ определяет выигрыш $u_i(s)$ для каждого игрока.

Равновесие Нэша

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

$u_i(s_i^*, s_{-i}^*) \geq u_i(s_i, s_{-i}^*) \quad \forall s_i \in S_i, \ \forall i \in N$

где $s_{-i}^* = (s_1^*, \dots, s_{i-1}^*, s_{i+1}^*, \dots, s_n^*)$ — набор стратегий всех игроков, кроме $i$ .

Интуиция: в равновесии каждый игрок играет лучший ответ на стратегии других игроков.

Чистые и смешанные стратегии

Чистая стратегия — конкретный выбор из $S_i$ .

Смешанная стратегия — вероятностное распределение над чистыми стратегиями:

$\sigma_i \in \Delta(S_i)$

где $\Delta(S_i)$ — множество всех вероятностных распределений на $S_i$ .

Центральная теорема: каждая конечная игра имеет хотя бы одно равновесие в смешанных стратегиях [1].

Доминирование стратегий

Стратегия $s_i'$ строго доминирует стратегию $s_i$ , если:

$u_i(s_i', s_{-i}) > u_i(s_i, s_{-i}) \quad \forall s_{-i}$

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

Практические примеры

Дилемма заключённого

Это классический пример, демонстрирующий центральный парадокс теории игр: конфликт между индивидуальной и коллективной рациональностью.

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

	Сотрудничество (молчание)	Предательство
Сотрудничество	-1, -1	-3, 0
Предательство	0, -3	-2, -2

Анализ: Если противник выбирает молчание, предательство даёт 0 вместо -1 (выгодно). Если противник предаёт, предательство даёт -2 вместо -3 (выгодно). Таким образом, предательство — доминирующая стратегия для обоих игроков.

Единственное равновесие Нэша: (Предательство, Предательство) с выигрышами (-2, -2).

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

Равновесие Нэша выделено рамкой

Игра «Ястреб–Голубь»

Модель биологической конкуренции за ресурс. Два животных встречаются; каждое может проявить агрессию (Ястреб) или избежать конфликта (Голубь).

	Ястреб	Голубь
Ястреб	(V-C)/2, (V-C)/2	V, 0
Голубь	0, V	V/2, V/2

где $V$ — стоимость ресурса, $C$ — стоимость боевого ранения.

Интерпретация: Если оба агрессивны, оба несут убытки. Если один агрессивен, другой покоряется. Чистого равновесия обычно нет (кроме граничных случаев).

Смешанное равновесие: в популяции сосуществуют оба типа в пропорции

$p^* = \frac{V}{C}$

Эта модель объясняет биологическое разнообразие поведения в популяции и применяется в эволюционной биологии и экологии [4].

Теория игр в машинном обучении

Связь между теорией игр и ML глубока и многослойна. Рассмотрим ключевые приложения.

Многоагентное обучение с подкреплением (MARL)

Обучение с подкреплением в мультиагентной среде сводится к поиску равновесия Нэша в стохастической игре. Каждый агент учится максимизировать кумулятивное вознаграждение:

$J_i = \mathbb{E}\left[\sum_{t=0}^{\infty} \gamma^t r_i(s_t, a_1(t), \dots, a_n(t))\right]$

где $a_i(t)$ — действие агента $i$ , $\gamma$ — дисконт-фактор [5].

Задача усложняется: выигрыш каждого зависит от политик других агентов, которые одновременно обучаются. Стандартные алгоритмы (Q-обучение) адаптируются:

Independent Q-Learning — каждый агент обновляет значения, игнорируя других (неустойчиво);
Joint Action Learners — совместное обновление с моделью поведения других агентов;
Алгоритмы, ищущие равновесие Нэша — сходятся к равновесию в определённых классах игр.

Практическое применение: роботы-конкуренты, торговые агенты, сетевые протоколы.

Генеративно-состязательные сети (GAN)

GAN — элегантное применение антагонистической игры к генеративному моделированию [6].

Две нейросети играют друг против друга:

Генератор $G: z \to x$ преобразует шум $z$ в синтетические данные $x$ ;
Дискриминатор $D: x \to [0, 1]$ различает реальные и поддельные данные.

Функция потерь формулируется как антагонистическая игра:

$\min_G \max_D \mathbb{E}_{x \sim p_{\text{real}}}[\log D(x)] + \mathbb{E}_{z \sim p_z}[\log(1 - D(G(z)))]$

Идеально, при равновесии Нэша, генератор создаёт неотличимые от реальных данные, а дискриминатор — несмещённый классификатор.

Вызовы: сходимость не гарантирована; часто наблюдается нестабильность. Модификации (WGAN, Spectral Normalization) вводят альтернативные функции потерь и регуляризацию, опираясь на глубокое понимание игровой динамики.

Значение Шепли и объяснимость моделей

Из кооперативной теории игр берётся концепция значения Шепли — справедливое распределение вклада каждого игрока в общий результат [7].

В контексте ML (SHAP — SHapley Additive exPlanations) значение Шепли показывает маржинальный вклад каждого признака в прогноз:

$\phi_i(f) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|! (n - |S| - 1)!}{n!} [f(S \cup \{i\}) - f(S)]$

Это позволяет интерпретировать "чёрные ящики" (нейросети, ансамбли) и объяснять решения моделей. Значение Шепли имеет аксиоматическую обоснованность: это единственное решение, удовлетворяющее симметрии и маржинальности [7].

thumb|300px|SHAP beeswarm plot: вклад каждого признака в предсказание модели.

Аукционы и механизм дизайн

Теория игр применяется при проектировании рекомендательных систем, торговых платформ и систем распределения ресурсов. Участники имеют частную информацию о своих предпочтениях и стимулы исказить её. Теория раскрывает совместимые по стимулам механизмы, где честное сообщение информации — равновесие Нэша [1]. Эти идеи лежат в основе рекламных аукционов (Google, Facebook) и платформ маршрутизации.

Критика и ограничения

Классические модели опираются на нереалистичные предположения, и их применимость ограничена.

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

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

Множественность равновесий: Часто существует много равновесий; неясно, какое реализуется на практике. Требуются дополнительные концепции (рафинирование, равновесие в эволюционно стабильных стратегиях).

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

Поведенческая теория игр и экспериментальные исследования показывают отклонения от классических предсказаний [8]. Современные подходы интегрируют идеи из психологии, нейронауки и социологии.

Заключение

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

Литература

[1] Nash, J. F. (1950). "Equilibrium points in N-person games". Proceedings of the National Academy of Sciences, 36(1), 48–49.

[2] von Neumann, J. (1928). "Zur Theorie der Gesellschaftsspiele". Mathematische Annalen, 100(1), 295–320.

[3] von Neumann, J., & Morgenstern, O. (1944). Theory of Games and Economic Behavior. Princeton University Press.

[4] Maynard Smith, J. (1982). Evolution and the Theory of Games. Cambridge University Press.

[5] Buşoniu, L., Babuška, R., & De Schutter, B. (2008). "Multi-agent reinforcement learning: An overview". In Innovations in Multi-Agent Systems and Applications - 1 (pp. 183–221). Springer.

[6] Goodfellow, I., Pouget-Abadie, J., Mirza, M., et al. (2014). "Generative adversarial nets". In Advances in Neural Information Processing Systems (pp. 2672–2680). NIPS.

[7] Shapley, L. S. (1953). "A value for n-person games". Contributions to the Theory of Games, 2(28), 307–317.

[8] Camerer, C. F. (2003). Behavioral Game Theory: Experiments in Strategic Interaction. Princeton University Press.

Примечания

Полный промпт, использованный при создании этой статьи, доступен на странице обсуждения.

Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B8%D0%B3%D1%80»

Теория игр

Материал из MachineLearning.

Содержание

Теория игр

Историческое развитие

Основные понятия

Формальная модель игры

Равновесие Нэша

Чистые и смешанные стратегии

Доминирование стратегий

Практические примеры

Дилемма заключённого

Игра «Ястреб–Голубь»

Теория игр в машинном обучении

Многоагентное обучение с подкреплением (MARL)

Генеративно-состязательные сети (GAN)

Значение Шепли и объяснимость моделей

Аукционы и механизм дизайн

Критика и ограничения

Заключение

Литература

Примечания

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты