Value Shapley
- Автор метода
- Lloyd Shapley
- Год
- 1953
- Тип
- algorithm
- Семейство
- Game-theoretic
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Value Shapley — это концепция решения для кооперативных игр, которая справедливо распределяет общий выигрыш между игроками на основе их предельного вклада в коалиции.
Введенное Ллойдом Шепли в 1953 году, Value Shapley является единственным распределением выигрыша, удовлетворяющим четырем интуитивно понятным аксиомам: эффективность (распределяется общий выигрыш), симметрия (идентичные игроки получают равный выигрыш), нулевой игрок (игроки, не вносящие вклад, ничего не получают) и аддитивность по играм.
Интуиция метода
Представьте группу работников, создающих совместное предприятие. Value Shapley задает вопрос: сколько должен заработать каждый работник? Ответ основан на среднем предельном вкладе, который каждый работник вносит при присоединении к командам разного размера. Для каждого возможного порядка присоединения работников (от нуля до всех) вычисляется, сколько каждый добавляет; затем эти вклады усредняются по всем возможным порядкам. Это дает каждому работнику выигрыш, отражающий его незаменимую роль без предвзятости по времени или размеру группы. Это единственное «справедливое» разделение, удовлетворяющее интуитивным аксиомам.
История
Ллойд Шепли ввел Value Shapley в 1953 году как единственное решение проблемы справедливого распределения в кооперативных играх. Его аксиоматический подход оказался преобразующим, установив кооперативную теорию игр как строгую область. Value Shapley применялся в различных областях от распределения затрат до присвоения кредитов и регулирования окружающей среды. Вклад Шепли в теорию игр принес ему Нобелевскую премию по экономике в 2012 году, признав основополагающее значение Value Shapley.
Когда применять
Использовать Value Shapley при справедливом распределении совместных выигрышей от формирования коалиций, таких как распределение прибыли в партнерствах, распределение кредитов в исследовательских командах или оценка индивидуального вклада в ансамблевые модели. Использовать, когда игроки имеют неоднородный вклад и рыночные цены не раскрывают индивидуальную ценность. Подходит, когда требуется аксиоматически обоснованное справедливое разделение, удовлетворяющее базовым принципам справедливости.
Ограничения и замечания
- Вычислительная сложность: требует перечисления всех 2^n коалиций для n игроков; невыполнимо для больших n.
- Требует полной информации: значения коалиций должны быть известны заранее для всех подмножеств.
- Может не удовлетворять индивидуальной рациональности: некоторые игроки могут заработать больше вне большой коалиции.
- Неоднозначность в играх с множеством коалиций: когда возможно множество коалиций, определение того, какая формируется, неоднозначно.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Аксиоматическая уникальность: единственное распределение, удовлетворяющее аксиомам эффективности, симметрии, нулевого игрока и аддитивности.
- Справедливость и теоретическая обоснованность: отражает средний предельный вклад каждого игрока по коалициям.
- Гибкость: применимо к любой кооперативной игре, где значения коалиций четко определены.
- Разложимость: может использоваться с любой функцией оценки, включая вероятностные и взвешенные версии.
Применение
- Бухгалтерский учет партнерства: справедливое распределение прибыли между бизнес-партнерами с различным вкладом.
- Признание в исследовательской команде: распределение благодарностей и признания между соавторами на основе величины вклада.
- Распределение затрат: определение того, как разделить затраты на инфраструктуру между пользователями с различными моделями использования.
- Управление водными ресурсами: справедливое распределение воды из общих рек между пользователями ниже по течению.
- Машинное обучение: атрибуция предсказаний модели к вкладу признаков с использованием SHAP (SHapley Additive exPlanations).
Как это работает
Как это работает
Определить все возможные подмножества (коалиции) игроков, которые могут сформироваться.
Для каждой коалиции S вычислить v(S) — общий выигрыш, который может достичь коалиция без внешних игроков.
Для каждого игрока i и коалиции S, не содержащей i, вычислить предельный вклад: v(S ∪ {i}) - v(S).
Усреднить предельный вклад игрока i по всем порядкам игроков, взвешивая по количеству коалиций каждого размера.
Частые ошибки
- Предполагается, что Value Shapley приводит к стабильным коалициям; значение определяет справедливое распределение выигрыша, а не обязательно структуру стабильной коалиции.
- Вычисление Value Shapley простым усреднением по всем порядкам; необходимо взвешивать по вероятности размера коалиции.
- Путаница Value Shapley с Nash Bargaining или другими концепциями решений; каждая имеет разные интерпретации и свойства.
- Забывание, что Value Shapley предполагает полную характеристическую функцию; если значения коалиций неопределенны, требуются расширения.
Часто задаваемые вопросы
Почему Value Shapley уникально?
Потому что это единственное распределение выигрыша, удовлетворяющее четырем интуитивно понятным аксиомам: (1) Эффективность (весь выигрыш распределен), (2) Симметрия (идентичные игроки получают равный выигрыш), (3) Нулевой игрок (игроки с нулевым вкладом ничего не получают) и (4) Аддитивность (выигрыши суммируются по играм). Эти аксиомы однозначно определяют значение.
Как Value Shapley обрабатывает игры, в которых не формируется большая коалиция?
Value Shapley предполагает, что формируется большая коалиция и распределяется ее выигрыш v(N). Если могут формироваться коалиции, отличные от большой коалиции, Value Shapley напрямую не решает проблему стабильности структуры коалиции; требуются другие концепции теории игр (ядро, торг).
Может ли Value Shapley быть отрицательным?
Да. Если средний предельный вклад игрока по коалициям отрицателен (они снижают общий выигрыш), его Value Shapley отрицателен. Это может произойти в играх с внешними эффектами или отрицательными синергиями.
Похожие методы
Источники
Shapley, L. S. (1953). A value for n-person games. In H. W. Kuhn & A. W. Tucker (Eds.), Contributions to the Theory of Games II (pp. 307-317). Princeton University Press.
Открыть ссылку DOIСкопировано.Roth, A. E. (1988). The Shapley value as a von Neumann-Morgenstern utility. Econometrica, 56(4), 745-794.
Открыть ссылку на публикациюСкопировано.