Кооперативные дифференциальные игры и распределение выигрыша

Кооперативные дифференциальные игры и распределение выигрыша

Когда вместе выгоднее

Nash-равновесие описывает «ситуацию без договорённостей»: каждый за себя. Но в реальности игроки часто могут договариваться о совместных стратегиях и делить выигрыш. Рыболовные государства договариваются об ограничении вылова. Страны создают климатические соглашения. Компании объединяются в консорциумы. Кооперативные игры изучают, когда кооперация выгодна и как справедливо распределить совместный выигрыш.

Характеристическая функция

Для каждого подмножества игроков S ⊆ N (коалиции) определяется:

v(S) = максимальный суммарный выигрыш, который S может гарантировать себе совместными действиями

Супераддитивность: v(S ∪ T) ≥ v(S) + v(T) при S ∩ T = ∅. Если есть «синергия» от кооперации — объединяться выгодно.

При супераддитивности: v(N) ≥ Σᵢ v({i}) — объединяться всем вместе выгоднее, чем действовать поодиночке.

Шепли-значение

Вопрос: как справедливо распределить v(N) между игроками?

Шепли-значение (Shapley, 1953): φᵢ — «справедливый» вклад игрока i:

φᵢ(v) = Σ_{S ⊆ N{i}} |S|!(N−|S|−1)!/N! · [v(S∪{i}) − v(S)]

Смысл: усредняем «предельный вклад» i при присоединении к коалиции S по всем возможным порядкам присоединения.

Аксиоматизация: единственное распределение, удовлетворяющее:

1. Эффективность: Σᵢ φᵢ = v(N)
2. Симметрия: если i и j заменяемы в v — φᵢ = φⱼ
3. Нулевой игрок: если v(S∪{i}) = v(S) для всех S — φᵢ = 0
4. Аддитивность: φᵢ(v+w) = φᵢ(v) + φᵢ(w)

Ядро игры (Core)

Ядро — набор распределений (x₁,...,xN) с:

• Эффективность: Σᵢ xᵢ = v(N)
• Групповая рациональность: Σᵢ∈S xᵢ ≥ v(S) для всех S

Ни одна коалиция не захочет «выйти» из большой коалиции. Стабильное распределение.

Ядро может быть пустым! Например, игра трёх игроков, где v(1,2) = v(1,3) = v(2,3) = 1, v(1,2,3) = 1, v(i) = 0. Ядро пусто: любое распределение (x₁,x₂,x₃) с Σxᵢ=1 нарушает некоторое ограничение.

Шепли-значение всегда существует, ядро — нет.

Динамическая согласованность

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

Пример: государства договорились в начале игры об ограничениях по CO₂. Через 10 лет страна A обнаруживает, что ей выгоднее «выйти» из соглашения. Договорённость «нестабильна» — не является динамически согласованной.

Динамически согласованное распределение (Yeung-Petrosyan, 2001): траектория выплат β(t) такая, что в каждый момент t игрокам по-прежнему выгодно придерживаться соглашения.

Это накладывает ограничение: «платёжный механизм» (IDP — Incremental Distribution Procedure) должен выплачивать игрокам их долю так, чтобы ценность «оставшейся игры» всегда соответствовала договорённости.

Применение: управление рыбными ресурсами

Модель: N государств рыбачат в общем океане. Биомасса рыбы: ẋ = r x(1 − x/K) − Σᵢ uᵢ (логистический рост − суммарный вылов).

Выигрыш i: Jᵢ = ∫₀^∞ e^{−ρt} (uᵢ − c uᵢ²/(2x)) dt (прибыль от вылова с учётом издержек).

Nash (не кооперативное): каждый государство вылавливает слишком много → «трагедия общего» (Hardin). Ресурс истощается.

Кооперативное решение: максимизируем Σᵢ Jᵢ → меньший суммарный вылов → больший суммарный выигрыш! Шепли-значение распределяет его справедливо.

Динамическая согласованность: IDP обеспечивает, что каждое государство получает выплаты так, что «уход» из соглашения никогда не выгоден.

Полный разбор: трёхигровая модель

Задача: v({1}) = 2, v({2}) = 3, v({3}) = 4, v({1,2}) = 7, v({1,3}) = 8, v({2,3}) = 9, v({1,2,3}) = 12.

Шепли-значение:

φ₁: смотрим порядки: (1,2,3): вклад = 2-0=2; (1,3,2): вклад = 2; (2,1,3): вклад = 7-3=4; (2,3,1): вклад = 12-9=3; (3,1,2): вклад = 8-4=4; (3,2,1): вклад = 12-9=3. Среднее: (2+2+4+3+4+3)/6 = 18/6 = 3.

φ₂: аналогично = (5+3+3+5+3+3)/6 = 22/6 ≈ 3.67.

φ₃: 12 − 3 − 3.67 = 5.33 (из Σφᵢ = v(N) = 12).

Ядро: ищем (x₁,x₂,x₃) с Σ=12, x₁ ≥ 2, x₂ ≥ 3, x₃ ≥ 4, x₁+x₂ ≥ 7, x₁+x₃ ≥ 8, x₂+x₃ ≥ 9. Например, (3, 4, 5): проверяем все ограничения: 3≥2✓, 4≥3✓, 5≥4✓, 7≥7✓, 8≥8✓, 9≥9✓. Ядро непустое!

Кооперативные игры: формирование коалиций

В кооперативной теории игроки могут заключать обязывающие соглашения. Центральное понятие — характеристическая функция v(S), задающая значение коалиции S ⊆ N. Для дифференциальных игр v(S) — это значение игры, где члены S кооперируются, а NS играют против них (или решают свою подзадачу).

Свойства характеристической функции:

• Супераддитивность: v(S ∪ T) ≥ v(S) + v(T) для непересекающихся S, T — кооперация выгоднее
• Выпуклость: v(S ∪ T) + v(S ∩ T) ≥ v(S) + v(T) — гарантирует устойчивость

Концепции дележа

• Ядро (core): множество дележей, где никакая коалиция не может улучшить положение, выйдя из соглашения
• Вектор Шепли: φ_i = (1/n!) Σ_π [v(S_π_i ∪ {i}) − v(S_π_i)] — средний вклад игрока i по всем порядкам присоединения
• Нуклеолус (Шмайдлер): минимизирует «недовольство» наименее довольной коалиции
• τ-значение (Тийс): компромисс между минимальными правами и максимальными претензиями

Динамическая устойчивость

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

Применения

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