Значение Шепли — это концепция решения в теории кооперативных игр . Оно было названо в честь Ллойда Шепли , который ввел его в 1951 году и получил за него Нобелевскую премию по экономике в 2012 году. [1] [2] Каждой кооперативной игре оно присваивает уникальное распределение (среди игроков) общего излишка, генерируемого коалицией всех игроков. Значение Шепли характеризуется набором желаемых свойств. Харт (1989) дает обзор предмета. [3] [4]
Формальное определение
Формально коалиционная игра определяется как: Есть множество N (из n игроков) и функция , которая отображает подмножества игроков в действительные числа: , с , где обозначает пустое множество. Функция называется характеристической функцией.
Функция имеет следующий смысл: если S — коалиция игроков, то ( S ), называемая стоимостью коалиции S , описывает общую ожидаемую сумму выигрышей, которые члены коалиции могут получить в результате сотрудничества.
Значение Шепли — один из способов распределения общего выигрыша между игроками, предполагая, что все они сотрудничают. Это «справедливое» распределение в том смысле, что это единственное распределение с определенными желательными свойствами, перечисленными ниже. Согласно значению Шепли, [5] сумма, которую игрок i получает в коалиционной игре, равна
где n — общее число игроков, а сумма распространяется на все подмножества S из N , не содержащие игрока i , включая пустое множество. Также обратите внимание, что — биномиальный коэффициент . Формулу можно интерпретировать следующим образом: представьте, что коалиция формируется по одному актеру за раз, причем каждый актер требует своего вклада в качестве справедливой компенсации, а затем для каждого актера возьмите среднее значение этого вклада по возможным различным перестановкам , в которых может быть сформирована коалиция.
Альтернативная эквивалентная формула для вектора Шепли:
где сумма распространяется на все порядки игроков и представляет собой набор игроков, в котором они предшествуют в порядке .
С точки зрения синергии
Из характеристической функции можно вычислить синергию , которую обеспечивает каждая группа игроков. Синергия — это уникальная функция , такая, что
для любого подмножества игроков. Другими словами, «общая стоимость» коалиции получается путем суммирования синергии каждого возможного подмножества .
При наличии характеристической функции функция синергии рассчитывается через
с использованием принципа включения-исключения . Другими словами, синергия коалиции — это значение , которое еще не учтено ее подмножествами.
Значения Шепли определяются через функцию синергии по формуле [6] [7]
где сумма берется по всем подмножествам , включающим игрока .
Это можно интерпретировать как
Другими словами, синергия каждой коалиции делится поровну между всеми ее членами.
Примеры
Пример бизнеса
Рассмотрим упрощенное описание бизнеса. Владелец, o , обеспечивает важнейший капитал в том смысле, что без него/нее не может быть получена прибыль. Есть m работников w 1 ,..., w m , каждый из которых вносит сумму p в общую прибыль. Пусть
Функция ценности для этой коалиционной игры:
Вычисление числа Шепли для этой коалиционной игры приводит к значению мп/2 для владельца и п/2 для каждого из m работников.
Это можно понять с точки зрения синергии. Функция синергии
Таким образом, единственные коалиции, которые создают синергию, — это коалиции один на один между владельцем и любым отдельным работником.
Используя приведенную выше формулу для вектора Шепли в терминах, мы вычисляем
и
Результат также можно понять с точки зрения усреднения по всем заказам. Данный работник присоединяется к коалиции после владельца (и, следовательно, вносит p ) в половине заказов и, таким образом, вносит средний вклад при присоединении. Когда владелец присоединяется, в среднем половина работников уже присоединилась, поэтому средний вклад владельца при присоединении составляет .
Игра в перчатки
Игра в перчатки — это коалиционная игра, в которой у игроков есть перчатки для левой и правой руки, а цель состоит в том, чтобы сформировать пары. Пусть
где у игроков 1 и 2 перчатки на правую руку, а у игрока 3 — на левую руку.
Функция ценности для этой коалиционной игры:
Формула для расчета вектора Шепли:
где R — это порядок игроков, а — множество игроков из N , которые предшествуют i в порядке R.
В следующей таблице показаны предельные вклады Игрока 1.
Наблюдать
Используя аргумент симметрии, можно показать, что
В силу аксиомы эффективности сумма всех чисел Шепли равна 1, что означает, что
Характеристики
Значение Шепли имеет много желаемых свойств. В частности, это единственное правило оплаты, удовлетворяющее четырем свойствам: Эффективность, Симметрия, Линейность и Нулевой игрок. [8]
См. [9] : 147–156 для дополнительных характеристик значения Шепли.
Эффективность
Сумма значений Шепли всех агентов равна значению большой коалиции, так что весь выигрыш распределяется между агентами:
Если и — два актера, которые эквивалентны в том смысле, что
для каждого подмножества , которое не содержит ни , ни , то .
Это свойство также называется равным отношением к равным .
Линейность
Если объединить две коалиционные игры, описываемые функциями выигрыша и , то распределенные выигрыши должны соответствовать выигрышам, полученным из и выигрышам, полученным из :
для каждого из . Также, для любого действительного числа ,
для каждого в .
Нулевой игрок
Значение Шепли нулевого игрока в игре равно нулю. Игрок является нулевым в , если для всех коалиций , которые не содержат .
Таким образом, если сотрудничество имеет положительные внешние эффекты, все агенты (слабо) выигрывают, а если оно имеет отрицательные внешние эффекты, все агенты (слабо) проигрывают. [9] : 147–156
Анонимность
Если и являются двумя агентами, а — функция выигрыша, идентичная за исключением того, что роли и поменялись местами, то . Это означает, что маркировка агентов не играет роли в назначении их выигрышей.
Маргинализм
Значение Шепли можно определить как функцию, которая в качестве аргументов использует только предельные вклады игрока.
Как показано выше, ценность игры n-человек связывает с каждым игроком ожидание его вклада в ценность коалиции игроков перед ним в случайном порядке всех игроков. Когда есть много игроков и каждый играет лишь незначительную роль, набор всех игроков, предшествующих данному, эвристически рассматривается как хорошая выборка всех игроков. Ценность данного бесконечно малого игрока ds тогда определяется как «его» вклад в ценность «идеальной» выборки всех игроков.
Символически, если v — функция ценности коалиции, которая связывает каждую коалицию c с ее ценностью, а каждая коалиция c — измеримое подмножество измеримого множества I всех игроков, которое мы предполагаем без потери общности, ценность бесконечно малого игрока ds в игре равна
Здесь tI — это идеальный образец набора всех игроков I, содержащий долю t всех игроков, и — это коалиция, полученная после того, как ds присоединяется к tI . Это эвристическая форма диагональной формулы. [10]
Предполагая некоторую регулярность функции ценности, например, предполагая, что v может быть представлена как дифференцируемая функция неатомарной меры на I , μ , с функцией плотности , с где — характеристическая функция c . При таких условиях
,
как можно показать, аппроксимируя плотность ступенчатой функцией и сохраняя пропорцию t для каждого уровня функции плотности, и
Диагональная формула тогда имеет вид, разработанный Ауманном и Шепли (1974)
Выше μ может быть векторно значимым (при условии, что функция определена и дифференцируема в диапазоне μ , приведенная выше формула имеет смысл).
В приведенном выше рассуждении, если мера содержит атомы, это уже не так — вот почему диагональная формула в основном применима к неатомарным играм.
Два подхода были использованы для расширения этой диагональной формулы, когда функция f больше не дифференцируема. Мертенс возвращается к исходной формуле и берет производную после интеграла, тем самым извлекая выгоду из эффекта сглаживания. Нейман использовал другой подход. Возвращаясь к элементарному применению подхода Мертенса из Mertens (1980): [11]
Это работает, например, для большинства игр, в то время как исходная диагональная формула не может быть использована напрямую. Как Мертенс расширяет это дальше, определяя симметрии, на которых значение Шепли должно быть инвариантным, и усредняя по таким симметриям, чтобы создать дополнительный эффект сглаживания, коммутирующий средние значения с производной операцией, как указано выше. [12] Обзор неатомарного значения можно найти в Neyman (2002) [13]
Обобщение коалиций
Значение Шепли присваивает значения только отдельным агентам. Оно было обобщено [14] для применения к группе агентов C как,
С точки зрения синергетической функции , приведенной выше, это выглядит следующим образом: [6] [7]
где сумма распространяется на все подмножества , содержащие .
Эта формула предполагает интерпретацию, согласно которой вектор Шепли коалиции следует рассматривать как стандартный вектор Шепли отдельного игрока, если коалиция рассматривается как отдельный игрок.
Ценность игрока для другого игрока
В [15] значение Шепли было разложено на матрицу значений
Каждое значение представляет собой значение игрока для игрока . Эта матрица удовлетворяет
т.е. ценность игрока для всей игры равна сумме его ценности для всех отдельных игроков.
С точки зрения синергии, определенной выше, это звучит так:
где сумма распространяется на все подмножества , которые содержат и .
Это можно интерпретировать как сумму по всем подмножествам, содержащим игроков и , где для каждого подмножества вы
возьмите синергию этого подмножества
Разделите его на количество игроков в подмножестве . Интерпретируйте это как прибавочную стоимость, которую игрок получает от этой коалиции.
далее разделите это на , чтобы получить часть ценности игрока, которая приписывается игроку
Другими словами, синергетическая ценность каждой коалиции равномерно распределяется между всеми парами игроков в этой коалиции, где генерируется излишек для .
Регрессия Шепли
Регрессия значений Шепли — это статистический метод, используемый для измерения вклада отдельных предикторов в регрессионную модель. В этом контексте «игроками» являются отдельные предикторы или переменные в модели, а «выигрыш» — это общая объясненная дисперсия или предсказательная сила модели. Этот метод обеспечивает справедливое распределение общего выигрыша среди предикторов, присваивая каждому предиктору значение, представляющее его вклад в производительность модели. Липовецкий (2006) обсудил использование значений Шепли в регрессионном анализе, предоставив всесторонний обзор его теоретических основ и практических приложений. [16]
Вклад в значение Шепли признается за его баланс стабильности и дискриминационной силы, что делает их подходящими для точного измерения важности атрибутов обслуживания в маркетинговых исследованиях. [17] В нескольких исследованиях регрессия значения Шепли применялась к анализу ключевых драйверов в маркетинговых исследованиях. Покрышевская и Антипов (2012) использовали этот метод для анализа намерений повторных покупок онлайн-клиентов, продемонстрировав его эффективность в понимании поведения потребителей. [18] Аналогичным образом, Антипов и Покрышевская (2014) применили регрессию значения Шепли для объяснения различий в показателях рекомендаций для отелей на Южном Кипре, подчеркнув ее полезность в индустрии гостеприимства. [19] Дальнейшее подтверждение преимуществ значения Шепли в анализе ключевых драйверов предоставлено Вриенсом, Видденом и Бошем (2021), которые подчеркнули его преимущества в прикладной маркетинговой аналитике. [20]
В машинном обучении
Значение Шепли обеспечивает принципиальный способ объяснения прогнозов нелинейных моделей, распространенных в области машинного обучения . Интерпретируя модель, обученную на наборе признаков, как функцию значения для коалиции игроков, значения Шепли обеспечивают естественный способ вычисления того, какие признаки способствуют прогнозу [21] или способствуют неопределенности прогноза. [22] Это объединяет несколько других методов, включая локально интерпретируемые модельно-независимые объяснения (LIME), [23] DeepLIFT, [24] и распространение релевантности по слоям. [25] [26]
^ Шепли, Ллойд С. (21 августа 1951 г.). «Заметки об игре n-персон — II: Значение игры n-персон» (PDF) . Санта-Моника, Калифорния: RAND Corporation.
^ Рот, Элвин Э., ред. (1988). Величина Шепли: Эссе в честь Ллойда С. Шепли . Кембридж: Издательство Кембриджского университета. doi : 10.1017/CBO9780511528446. ISBN0-521-36177-X.
^ Харт, Серджиу (1989). «Shapley Value». В Eatwell, J.; Milgate, M.; Newman, P. (ред.). The New Palgrave: Game Theory . Norton. стр. 210–216. doi :10.1007/978-1-349-20181-5_25. ISBN978-0-333-49537-7.
^ Харт, Серджиу (12 мая 2016 г.). «Библиография кооперативных игр: теория ценностей».
^ Для доказательства уникальности существования см. Ichiishi, Tatsuro (1983). Теория игр для экономического анализа. Нью-Йорк: Academic Press. С. 118–120. ISBN 0-12-370180-5.
^ ab Grabisch, Michel (октябрь 1997 г.). «Альтернативные представления дискретных нечетких мер для принятия решений». Международный журнал неопределенности, нечеткости и систем, основанных на знаниях . 5 (5): 587–607. doi :10.1142/S0218488597000440. ISSN 0218-4885.
^ ab Grabisch, Michel (1 декабря 1997 г.). "k-порядковые аддитивные дискретные нечеткие меры и их представление". Нечеткие множества и системы . 92 (2): 167–189. doi :10.1016/S0165-0114(97)00168-1. ISSN 0165-0114.
^ Шепли, Ллойд С. (1953). «Значение для игр с n лицами». В Kuhn, HW; Tucker, AW (ред.). Вклад в теорию игр . Annals of Mathematical Studies. Том 28. Princeton University Press. С. 307–317. doi :10.1515/9781400881970-018. ISBN9781400881970.
^ ab Herve Moulin (2004). Справедливое разделение и коллективное благосостояние . Кембридж, Массачусетс: MIT Press. ISBN9780262134231.
^ ab Aumann, Robert J.; Shapley, Lloyd S. (1974). Values of Non-Atomic Games . Princeton: Princeton Univ. Press. ISBN0-691-08103-4.
^ Мертенс, Жан-Франсуа (1980). «Значения и производные». Математика исследования операций . 5 (4): 523–552. doi :10.1287/moor.5.4.523. JSTOR 3689325.
^ Мертенс, Жан-Франсуа (1988). «Значение Шепли в недифференцируемом случае». Международный журнал теории игр . 17 (1): 1–65. doi :10.1007/BF01240834. S2CID 118017018.
^ Нейман, А., 2002. Значение игр с бесконечным числом игроков, «Справочник по теории игр с экономическими приложениями», Справочник по теории игр с экономическими приложениями, Elsevier, издание 1, том 3, номер 3, 00. RJ Aumann & S. Hart (ред.).[1]
^ Грабиш, Мишель; Рубенс, Марк (1999). «Аксиоматический подход к концепции взаимодействия между игроками в кооперативных играх». Международный журнал теории игр . 28 (4): 547–565. doi :10.1007/s001820050125. S2CID 18033890.
^ Хаускен, Кьелл; Мор, Маттиас (2001). «Ценность игрока в играх с n участниками». Социальный выбор и благосостояние . 18 (3): 465–83. doi :10.1007/s003550000070. JSTOR 41060209. S2CID 27089088.
^ Липовецкий С (2006). «Регрессия значений Шепли: метод объяснения вкладов отдельных предикторов в регрессионную модель». Линейная алгебра и ее приложения . 417 : 48–54. doi :10.1016/j.laa.2006.04.027 (неактивен 1 ноября 2024 г.).{{cite journal}}: CS1 maint: DOI inactive as of November 2024 (link)
^ Покрышевская Е., Антипов Е. (2014). «Сравнение методов, используемых для измерения важности атрибутов услуг». Международный журнал исследований рынка . 56 (3): 283–296. doi :10.2501/IJMR-2014-023.
^ Покрышевская Е.Б., Антипов Е.А. (2012). «Стратегический анализ намерений повторных покупок онлайн-клиентов». Журнал «Нацеливание, измерение и анализ для маркетинга» . 20 : 203–211. doi :10.1057/jt.2012.13.
^ Антипов Е.А., Покрышевская Е.Б. (2014). «Объяснение различий в рейтингах рекомендаций: случай отелей Южного Кипра». Economics Bulletin . 34 (4): 2368–2376.
^ Vriens M, Vidden C, Bosch N (2021). «Преимущества значения Шепли в анализе ключевых драйверов». Applied Marketing Analytics . 6 (3): 269–278.
^ Lundberg, Scott M.; Lee, Su-In (2017). «Унифицированный подход к интерпретации прогнозов моделей». Advances in Neural Information Processing Systems . 30 : 4765–4774. arXiv : 1705.07874 . Получено 30.01.2021 .
^ Уотсон, Дэвид; О'Хара, Джошуа; Такс, Ник; Мадд, Ричард; Гай, Идо (2023). «Объяснение прогностической неопределенности с помощью теории Шепли». Достижения в области нейронных систем обработки информации . 37. arXiv : 2306.05724 .
^ Рибейро, Марко Тулио; Сингх, Самир; Гестрин, Карлос (13 августа 2016 г.). "«Почему я должен тебе доверять?»". Труды 22-й Международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . Нью-Йорк, США: ACM. С. 1135–1144. doi :10.1145/2939672.2939778. ISBN 978-1-4503-4232-2.
^ Шрикумар, Аванти; Гринсайд, Пейтон; Кундадже, Аншул (17 июля 2017 г.). «Изучение важных признаков посредством распространения различий активации». PMLR : 3145–3153. ISSN 2640-3498 . Получено 30 января 2021 г.
^ Бах, Себастьян; Биндер, Александр; Монтавон, Грегуар; Клаушен, Фредерик; Мюллер, Клаус-Роберт ; Самек, Войцех (10 июля 2015 г.). Суарес, Оскар Дениз (ред.). «О пиксельных объяснениях решений нелинейных классификаторов с помощью распространения релевантности по слоям». PLOS ONE . 10 (7). Публичная научная библиотека (PLoS): e0130140. Bibcode : 2015PLoSO..1030140B. doi : 10.1371/journal.pone.0130140 . ISSN 1932-6203. PMC 4498753. PMID 26161953 .
^ Антипов, Е.А.; Покрышевская, Е.Б. (2020). «Интерпретируемое машинное обучение для моделирования спроса с многомерными данными с использованием машин градиентного усиления и значений Шепли». Журнал управления доходами и ценообразованием . 19 (5): 355–364. doi :10.1057/s41272-020-00236-4.
Дальнейшее чтение
Фридман, Джеймс У. (1986). Теория игр с приложениями к экономике . Нью-Йорк: Oxford University Press. С. 209–215. ISBN 0-19-503660-3.