stringtranslate.com

Значение Шепли

Ллойд Шепли в 2012 году

Значение Шепли — это концепция решения в теории кооперативных игр . Оно было названо в честь Ллойда Шепли , который ввел его в 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 

Анонимность

Если и являются двумя агентами, а — функция выигрыша, идентичная за исключением того, что роли и поменялись местами, то . Это означает, что маркировка агентов не играет роли в назначении их выигрышей.

Маргинализм

Значение Шепли можно определить как функцию, которая в качестве аргументов использует только предельные вклады игрока.

Значение Ауманна-Шепли

В своей книге 1974 года Ллойд Шепли и Роберт Ауманн расширили концепцию вектора Шепли до бесконечных игр (определенных относительно неатомарной меры ) , создав диагональную формулу. [10] Позднее она была расширена Жаном-Франсуа Мертенсом и Авраамом Нейманом .

Как показано выше, ценность игры 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]

Смотрите также

Ссылки

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

Дальнейшее чтение

Внешние ссылки