Shapley Value

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

Определение и формальная модель

В кооперативной игре с множеством игроков \( N = \{1, 2, \dots, n\} \) и характеристической функцией \( v \), которая каждой коалиции \( S \subseteq N \) ставит в соответствие её выигрыш \( v(S) \) (при этом \( v(\emptyset) = 0 \)), значение Шепли для игрока \( i \) вычисляется по формуле:

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

Здесь \( v(S \cup \{i\}) - v(S) \) — предельный вклад игрока \( i \) в коалицию \( S \). Коэффициент \( \frac{|S|! (n - |S| - 1)!}{n!} \) представляет собой вероятность того, что игрок \( i \) присоединяется к коалиции \( S \) при случайном порядке формирования коалиции (все \( n! \) перестановок игроков равновероятны). Таким образом, значение Шепли — это средний предельный вклад игрока по всем возможным порядкам присоединения.

Аксиомы Шепли

Ллойд Шепли показал, что его значение является единственным, удовлетворяющим четырём аксиомам:

1. Аксиома эффективности (Efficiency): Сумма значений Шепли всех игроков равна общему выигрышу всей коалиции \( v(N) \). То есть вся выгода распределяется между участниками.
2. Аксиома симметрии (Symmetry): Если два игрока вносят одинаковый вклад в любую коалицию (т.е. \( v(S \cup \{i\}) = v(S \cup \{j\}) \) для всех \( S \subseteq N \setminus \{i,j\} \)), то их значения Шепли равны.
3. Аксиома болвана (Null player axiom): Если игрок не вносит никакого вклада ни в одну коалицию (т.е. \( v(S \cup \{i\}) = v(S) \) для всех \( S \subseteq N \setminus \{i\} \)), то его значение Шепли равно нулю.
4. Аксиома аддитивности (Additivity): Если игра состоит из двух независимых игр \( v \) и \( w \), то значение Шепли для объединённой игры \( v + w \) равно сумме значений Шепли для каждой из игр: \( \phi_i(v + w) = \phi_i(v) + \phi_i(w) \).

Эти аксиомы делают значение Шепли естественным и интуитивно понятным критерием справедливости.

Свойства и интерпретации

Значение Шепли обладает рядом важных свойств:

• Справедливость по вкладу: Каждый участник получает долю, пропорциональную его вкладу в общий результат, с учётом всех возможных комбинаций.
• Единственность: При выполнении аксиом Шепли решение является единственным.
• Линейность: Значение Шепли линейно по характеристической функции.
• Независимость от порядка: Результат не зависит от последовательности, в которой игроки присоединяются к коалиции.

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

Пример вычисления

Рассмотрим простую игру с тремя игроками \( A, B, C \). Пусть характеристическая функция задана так:

• \( v(\{A\}) = 1 \), \( v(\{B\}) = 2 \), \( v(\{C\}) = 3 \)
• \( v(\{A,B\}) = 4 \), \( v(\{A,C\}) = 5 \), \( v(\{B,C\}) = 6 \)
• \( v(\{A,B,C\}) = 10 \)

Вычислим значение Шепли для игрока \( A \). Всего возможны 6 перестановок игроков. Для каждой перестановки вычисляем предельный вклад \( A \):

1. Порядок \( A, B, C \): \( v(\{A\}) - v(\emptyset) = 1 - 0 = 1 \)
2. Порядок \( A, C, B \): \( v(\{A\}) - v(\emptyset) = 1 \)
3. Порядок \( B, A, C \): \( v(\{A,B\}) - v(\{B\}) = 4 - 2 = 2 \)
4. Порядок \( B, C, A \): \( v(\{A,B,C\}) - v(\{B,C\}) = 10 - 6 = 4 \)
5. Порядок \( C, A, B \): \( v(\{A,C\}) - v(\{C\}) = 5 - 3 = 2 \)
6. Порядок \( C, B, A \): \( v(\{A,B,C\}) - v(\{B,C\}) = 10 - 6 = 4 \)

Среднее арифметическое: \( (1 + 1 + 2 + 4 + 2 + 4) / 6 = 14 / 6 \approx 2.33 \). Аналогично для \( B \) и \( C \) получаем \( \phi_B \approx 3.33 \), \( \phi_C \approx 4.33 \). Сумма \( 2.33 + 3.33 + 4.33 = 10 \), что равно \( v(\{A,B,C\}) \).

Применение в машинном обучении

В последние десятилетия значение Шепли нашло широкое применение в интерпретации моделей машинного обучения. Метод SHAP (SHapley Additive exPlanations) использует значение Шепли для объяснения предсказаний модели. Каждый признак (игрок) получает вклад в предсказание (выигрыш), а значение Шепли показывает, насколько данный признак изменил предсказание относительно среднего. Это позволяет понять, какие признаки наиболее важны для конкретного прогноза.

SHAP-значения обладают свойствами, аналогичными аксиомам Шепли: локальная точность (сумма вкладов признаков равна разнице между предсказанием и средним), отсутствие вклада для неиспользуемых признаков и согласованность (если модель меняется так, что вклад признака не уменьшается, его SHAP-значение не уменьшается). Однако вычисление точных значений Шепли для большого числа признаков требует экспоненциального времени, поэтому на практике используются аппроксимации (например, KernelSHAP или TreeSHAP).

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

Несмотря на математическую строгость, значение Шепли имеет ряд ограничений:

• Вычислительная сложность: Точное вычисление требует перебора всех \( 2^n \) коалиций, что невозможно для больших \( n \). Для практических задач (например, в машинном обучении с сотнями признаков) применяются приближённые методы.
• Предположение о независимости: Значение Шепли предполагает, что все коалиции возможны, что не всегда реалистично (например, в экономике некоторые участники могут быть несовместимы).
• Невозможность учёта внешних эффектов: Классическая модель не учитывает динамику взаимодействия или влияние внешних факторов.
• Субъективность аксиом: Хотя аксиомы Шепли кажутся естественными, в некоторых контекстах (например, при распределении затрат) могут быть предпочтительны другие решения (например, ядро или вектор Шепли — Шубика).

Историческая справка

Ллойд Шепли (1923–2016) — американский математик и экономист, лауреат Нобелевской премии по экономике 2012 года (совместно с Элвином Ротом) за теорию стабильных распределений и практику рыночного дизайна. Значение Шепли было опубликовано в 1953 году в статье «A Value for n-Person Games». Впоследствии концепция была обобщена и дополнена, в частности, в работах Мартина Шубика (индекс Шепли — Шубика для взвешенных голосований) и в рамках теории кооперативных игр с нечёткой коалицией.

Связанные концепции

• Ядро (Core): Множество распределений, которые не могут быть улучшены никакой коалицией. В отличие от значения Шепли, ядро может быть пустым.
• Вектор Шепли — Шубика: Частный случай значения Шепли для игр с взвешенным голосованием, где каждый игрок имеет вес, а выигрыш равен 1, если коалиция набирает большинство голосов, и 0 в противном случае.
• Индекс Банцафа: Другой показатель влияния в голосовании, основанный на подсчёте «критических» голосов (когда голос игрока меняет исход). В отличие от индекса Шепли — Шубика, он не учитывает порядок присоединения.

Источники

• Shapley, L. S. (1953). A Value for n-Person Games. In Contributions to the Theory of Games, Volume II, Annals of Mathematical Studies, 28, 307–317.
• Roth, A. E. (1988). The Shapley Value: Essays in Honor of Lloyd S. Shapley. Cambridge University Press.
• Lundberg, S. M., & Lee, S. I. (2017). A Unified Approach to Interpreting Model Predictions. In Advances in Neural Information Processing Systems (NeurIPS).
• Osborne, M. J., & Rubinstein, A. (1994). A Course in Game Theory. MIT Press.