Кооперативная теория игр: вектор Шепли, ядро и распределение коалиционного выигрыша

Математической основой любой кооперативной игры является характеристическая функция (v), которая ставит в соответствие каждой возможной коалиции игроков (подмножеству общего множества участников) определенное числовое значение — гарантированный выигрыш, который эта коалиция может получить своими силами, независимо от действий остальных игроков. Фундаментальным свойством характеристической функции является субаддитивность (или супераддитивность в терминах прибыли): выигрыш от объединения двух непересекающихся коалиций всегда больше или равен сумме выигрышей, которые они могли бы получить по отдельности. Это свойство гарантирует, что формирование Гранд-коалиции (объединения всех без исключения игроков) является экономически наиболее эффективным исходом.

Для того чтобы Гранд-коалиция оставалась стабильной, распределение итоговой прибыли должно удовлетворять принципу индивидуальной и групповой рациональности. Это означает, что ни одна подгруппа игроков не должна получать в общем деле меньше, чем она могла бы заработать, отделившись в самостоятельную структуру. Множество всех распределений выигрыша (дележей), удовлетворяющих этому жесткому условию, называется Ядром игры (The Core). Геометрически ядро представляет собой выпуклый многогранник в многомерном пространстве. Если дележ находится внутри ядра, никто не захочет разрушать союз. Проблема заключается в том, что во многих играх ядро может быть абсолютно пустым (не существует ни одного стабильного распределения), либо, наоборот, содержать бесконечное множество вариантов, не давая однозначного ответа.

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

Алгебраический смысл вектора Шепли заключается в расчете ожидаемого предельного (маржинального) вклада каждого игрока. Представим, что игроки заходят в комнату для формирования коалиции по одному, в случайном порядке. Каждый входящий игрок увеличивает ценность уже собравшейся в комнате группы на определенную величину. Вектор Шепли вычисляет математическое ожидание этого маржинального вклада для каждого участника, усредненное по абсолютно всем возможным перестановкам (порядкам входа). Вычисление вектора Шепли для n игроков требует анализа факториала от n перестановок, что делает алгоритм невероятно ресурсоемким. Тем не менее, сегодня этот аппарат активно используется в машинном обучении (SHAP values) для интерпретации сложных нейросетей, позволяя математически точно определить, какой именно вклад каждый признак (фича) внес в финальное предсказание искусственного интеллекта.