Ядро, значение Шепли и кооперативные концепции

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

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

Примеры: распределение прибыли в совместном предприятии; разделение затрат на строительство совместной инфраструктуры; распределение власти в политической коалиции.

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

TU-игра (с трансферабельной полезностью) задаётся парой (N, v): N = {1, ..., n} — игроки; v: 2^N → ℝ — характеристическая функция (v(S) — максимальный совместный выигрыш коалиции S). Обычно v(∅) = 0.

Супераддитивность: v(S∪T) ≥ v(S) + v(T) при S∩T = ∅. Это условие «объединяться выгодно» — стандартное для большинства экономических приложений.

Числовой пример: N = {1, 2, 3}, v({1}) = 1, v({2}) = 2, v({3}) = 0, v({1,2}) = 4, v({1,3}) = 3, v({2,3}) = 3, v(N) = 6.

Ядро: устойчивое распределение

Распределение (imputation) x = (x₁, x₂, x₃) удовлетворяет: x₁+x₂+x₃ = 6 (эффективность); xᵢ ≥ v({i}) (индивидуальная рациональность). Значит: x₁≥1, x₂≥2, x₃≥0, Σxᵢ=6.

Ядро — множество распределений, которые не могут быть «заблокированы» ни одной коалицией: x ∈ Core(v) тогда и только тогда, когда для всех S ⊆ N: Σᵢ∈S xᵢ ≥ v(S).

Для нашего примера условия ядра: x₁+x₂ ≥ 4, x₁+x₃ ≥ 3, x₂+x₃ ≥ 3, и Σxᵢ = 6.

Из x₁+x₂ ≥ 4 и x₁+x₂+x₃ = 6: x₃ ≤ 2. Из x₂+x₃ ≥ 3 и x₃ ≤ 2: x₂ ≥ 1. Итого x₂ ∈ [1, 3], x₃ ∈ [0, 2], x₁ = 6 − x₂ − x₃. Ядро непусто! Например: (2, 3, 1) ∈ Core.

Значение Шепли: справедливое распределение

Шепли (1953) нашёл единственное распределение, удовлетворяющее четырём «разумным» аксиомам.

Аксиомы: Эффективность: Σᵢ φᵢ(v) = v(N). Симметрия: взаимозаменяемые игроки получают поровну. Фиктивный игрок: «нулевой» игрок (не вносит вклад) получает 0. Аддитивность: φ(v+w) = φ(v) + φ(w).

Формула: φᵢ(v) = Σ_{S⊆N{i}} [|S|!(n−|S|−1)!/n!] · [v(S∪{i}) − v(S)]

Интерпретация: представим, что игроки вступают в большую коалицию в случайном порядке. Предельный вклад игрока i — это v(S∪{i}) − v(S), где S — случайная коалиция, уже сформировавшаяся к его приходу. Значение Шепли = ожидаемый предельный вклад при равномерно случайном порядке.

Вычисление для примера (6 перестановок трёх игроков):

Порядки и предельные вклады i=1: (1,2,3): v({1})−0=1; (1,3,2): 1; (2,1,3): v({1,2})−v({2})=2; (2,3,1): v(N)−v({2,3})=3; (3,1,2): v({1,3})−v({3})=3; (3,2,1): v(N)−v({2,3})=3. φ₁ = (1+1+2+3+3+3)/6 = 13/6 ≈ 2.17.

Аналогично: φ₂ ≈ 2.5, φ₃ ≈ 1.33. Проверка: 2.17+2.5+1.33 = 6 ✓.

Нуклеолюс: минимизация недовольства

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

Нуклеолюс единственен. Если ядро непусто, нуклеолюс в нём.

Приложения

Распределение затрат в инфраструктуре: Три города (A, B, C) строят аэропорт. Стоимость для каждого: v({A}) = 100, v({B}) = 150, v({C}) = 200, v({A,B}) = 180, v({A,C}) = 250, v({B,C}) = 290, v(N) = 350. Значение Шепли даёт «справедливую» долю затрат каждого города на основе его предельного вклада.

Распределение акций при слиянии: Если компании A и B сливаются и создают синергию (v(AB) > v(A)+v(B)), значение Шепли определяет «справедливый» обменный курс акций.

Индекс власти в политике: В парламенте коалиции нужен минимум голосов. Значение Шепли (индекс Шепли–Шубика) показывает, насколько часто партия является «поворотной» — меняет исход голосования. Это и есть её реальная власть.

Альтернативные индексы власти: Индекс Банцафа — альтернатива Шепли–Шубика, основанная на числе «критических» участий: игрок i критичен для коалиции S, если S выигрывает, а S {i} — нет. Индекс Банцафа не предполагает равновероятного порядка вступления и даёт иное распределение власти. В Европейском совете оба индекса используются для анализа влияния государств-членов при квалифицированном большинстве.

Значение Шепли в корпоративном управлении и политической экономии

Значение Шепли нашло широкое применение за пределами абстрактной теории. В корпоративном управлении оно используется для оценки влияния акционеров при голосовании: если один акционер владеет 40% голосов при требовании простого большинства, его индекс Шепли–Шубика значительно превышает долю голосов, поскольку он необходим в любой выигрышной коалиции. В политической науке значение Шепли анализирует силу отдельных государств в международных организациях и голосов в парламентских коалициях. В экономике инфраструктуры значение Шепли применяется при разделении затрат на строительство совместного объекта (аэропорта, водохранилища) между несколькими муниципалитетами — это справедливое распределение, основанное на предельном вкладе каждого. Нобелевские лауреаты Роберт Ауман и Ллойд Шепли разработали ключевые результаты кооперативной теории игр, включая аксиоматизацию значения Шепли (аксиомы эффективности, симметрии, нулевого игрока и аддитивности), что придало ему статус уникального справедливого распределения. Современные алгоритмы объяснимого ИИ (SHAP — SHapley Additive exPlanations) напрямую используют значение Шепли для объяснения вклада каждого признака в предсказание модели машинного обучения.

На практике значение Шепли вычисляется численно для больших игр через метод Монте-Карло: случайные перестановки игроков аппроксимируют среднее предельное вклада с точностью O(1/√N) за N выборок. Именно так SHAP вычисляет важность признаков в случайных лесах и нейросетях с тысячами параметров — полный перебор всех 2ⁿ коалиций невозможен, но случайная выборка перестановок даёт хорошее приближение за приемлемое время.

Задание: N = {1,2,3}: v({1}) = 1, v({2}) = 2, v({3}) = 0, v({1,2}) = 4, v({1,3}) = 3, v({2,3}) = 3, v(N) = 6. Найдите значение Шепли для каждого игрока. Входит ли оно в ядро?