Кооперативные игры

Uber, Lyft и местное такси хотят объединиться для сокращения пробок. Три страны совместно финансируют спутник. Юридическая фирма принимает нового партнёра. Во всех случаях вопрос один: как справедливо поделить совместно созданную ценность? Кооперативная теория игр - математика справедливости, лежащая в основе SHAP, механизмов распределения ресурсов и теории альянсов.

• **SHAP (XAI):** значение Шепли - стандарт объяснимости ML-моделей в банках, медицине, юриспруденции. Каждый признак получает «свою долю» в предсказании
• **Деление затрат:** аэропорты, водоснабжение, телеком-сети - нуклеолус и значение Шепли используются для справедливого распределения инфраструктурных затрат
• **Matching markets:** алгоритм стабильных сопоставлений (Гейл-Шепли) определяет распределение студентов-медиков по больницам, детей по школам, органов по реципиентам

Предварительные знания

• Extensive Form Games

Коалиции и характеристическая функция

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

Кооперативная игра - пара (N, v), где: • N = {1, 2, ..., n} - игроки • v: 2^N → R - характеристическая функция: v(S) = выигрыш коалиции S при оптимальной кооперации внутри v(∅) = 0, v обычно супераддитивна: v(S ∪ T) ≥ v(S) + v(T) при S ∩ T = ∅

Ключевой вопрос кооперативной теории: **как делить v(N) между игроками?** Требования к справедливому дележу: каждый игрок получает не меньше своего индивидуального выигрыша v({i}), каждая коалиция не имеет стимула покинуть большую коалицию. Это называется **ядром** (core).

Значение Шепли

Допустим, игроки «входят» в коалицию по одному в случайном порядке. Каждый получает свой **предельный вклад** - насколько увеличивается выигрыш с его приходом. Значение Шепли - средний предельный вклад по всем возможным порядкам вхождения. Это единственный дележ, удовлетворяющий четырём «разумным» аксиомам.

φᵢ(v) = Σ_{S⊆N\{i}} [|S|!(|N|-|S|-1)! / |N|!] · [v(S∪{i}) - v(S)] Где v(S∪{i}) - v(S) - предельный вклад игрока i при присоединении к коалиции S. Аксиомы: эффективность (сумма φᵢ = v(N)), симметрия, нулевой игрок, аддитивность.

Значение Шепли нашло применение в ML: SHAP (SHapley Additive exPlanations) - стандарт объяснимости моделей. Каждый признак получает «значение Шепли» - его средний предельный вклад в предсказание при всех возможных комбинациях признаков.

Ядро (Core)

Дележ x = (x₁, ..., xₙ) «стабилен», если ни одна коалиция S не захочет отколоться. Точнее: если Σᵢ∈S xᵢ ≥ v(S) для каждой коалиции S - то у неё нет стимула уходить. Множество всех стабильных дележей называется ядром (core). Ядро может быть пустым - тогда «большая коалиция» нестабильна.

Дележ x ∈ Core если: 1. Σᵢ∈N xᵢ = v(N) - эффективность 2. Σᵢ∈S xᵢ ≥ v(S) для всех S ⊆ N - стабильность коалиций Ядро непусто ⟺ игра «сбалансирована» (теорема Бондарева-Шепли).

Ядро может быть пустым. Классический пример: «мажоритарные игры» (majority games), где любые двое могут победить одного. Нет дележа, который устраивает всех троих: одна пара всегда хочет переманить третьего. В этом случае нужны другие концепции решения - нуклеолус или value Шепли (которое всегда существует).

Нуклеолус

Когда ядро пусто, нужно другое решение. Нуклеолус - дележ, минимизирующий «максимальное недовольство» коалиций. Недовольство (excess) коалиции S - насколько она недополучает: e(S, x) = v(S) - Σᵢ∈S xᵢ. Нуклеолус лексикографически минимизирует вектор всех excess в убывающем порядке.

Для дележа x вектор excess: θ(x) = (e(S₁,x), ..., e(S_{2n},x)) - все коалиционные недовольства, отсортированные по убыванию. Нуклеолус: η = argmin_{x∈X} θ(x) - лексикографический минимум. Свойства: всегда единственен (в отличие от ядра), лежит в ядре если оно непусто, симметричен.

Нуклеолус используется в практических задачах распределения затрат: аэропортная игра (как делить стоимость взлётно-посадочной полосы между авиакомпаниями с разными типами самолётов), распределение затрат на водоснабжение между городами, дележ доходов в совместных предприятиях.

Ключевые идеи

• **Характеристическая функция v(S):** ценность коалиции S - базис кооперативной теории
• **Значение Шепли:** единственный дележ, удовлетворяющий 4 аксиомам справедливости - основа SHAP в ML
• **Ядро (Core):** стабильные дележи, при которых ни одна коалиция не хочет отколоться (может быть пустым)
• **Нуклеолус:** всегда единственен, минимизирует максимальное недовольство коалиций

Связанные темы

Кооперативные игры дополняют некооперативную теорию и лежат в основе механизмов:

• Дилемма заключённого — Кооперация в ДЗ - переход от некооперативного к кооперативному анализу
• Mechanism Design — Механизмы часто используют кооперативные концепции для дизайна систем с трансферами
• Теория игр в ML — SHAP - прямое применение значения Шепли в объяснимом AI

Вопросы для размышления

• В команде разработки один человек пишет 80% кода, другой делает архитектурные решения, третий общается с клиентами. Как распределить бонусы, используя логику значения Шепли?
• Ядро может быть пустым - нет стабильного дележа. Можете ли привести реальный пример (альянс, политическая коалиция), где это происходит? Как стороны справляются?
• SHAP объясняет предсказания ML через значение Шепли. Но вычисление точного Шепли - NP-hard для больших наборов признаков. Как работают на практике приближённые методы?

Связанные уроки

• stat-20-causal