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

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

Значение Шепли — это концепция решения в теории кооперативных игр . Он был назван в честь Ллойда Шепли , который представил его в 1951 году и получил за него Нобелевскую премию по экономике в 2012 году. Каждой кооперативной игре присваивается уникальное распределение (среди игроков) общего излишка, созданного коалицией всех игроков. Ценность Шепли характеризуется набором желательных свойств. Харт (1989) дает обзор этой темы.

Формальное определение

Формально коалиционная игра определяется как:Существует набор N (из n игроков) и функция $v$ который сопоставляет подмножества игроков с реальными числами: $v\colon 2^{N}\to \mathbb {R}$, с $v(\emptyset )=0$, где $\emptyset$ обозначает пустое множество. Функция $v$ называется характеристической функцией.

Функция $v$ имеет следующий смысл: если S — коалиция игроков, то $v$( S ), называемая ценностью коалиции S , описывает общую ожидаемую сумму выигрышей членов коалиции. $S$ можно получить путем сотрудничества.

Значение Шепли — это один из способов распределения общего выигрыша между игроками при условии, что все они сотрудничают. Это «справедливый» дистрибутив в том смысле, что это единственный дистрибутив с определенными желательными свойствами, перечисленными ниже. Согласно значению Шепли, сумма, которую игрок i в коалиционной игре получает $(v,N)$ является

$\varphi _{i}(v)=\sum _{S\subseteq N\setminus \{i\}}{\frac {|S|!\;(n-|S|-1)!}{n!}}(v(S\cup \{i\})-v(S))$

$\quad \quad \quad ={\frac {1}{n}}\sum _{S\subseteq N\setminus \{i\}}{n-1 \choose n-|S|-1}^{-1}(v(S\cup \{i\})-v(S))$

где n — общее количество игроков, а сумма распространяется на все подмножества S из N, не содержащие игрока i , включая пустой набор. Также обратите внимание, что ${n \choose k}$ – биномиальный коэффициент . Формулу можно интерпретировать следующим образом: представьте себе, что коалиция формируется по одному актору за раз, причем каждый актор требует своего вклада. $v(S\cup \{i\})-v(S)$ в качестве справедливой компенсации, а затем для каждого участника взять среднее значение этого вклада по возможным различным перестановкам , в которых может быть сформирована коалиция.

Альтернативная эквивалентная формула для значения Шепли:

$\varphi _{i}(v)={\frac {1}{n!}}\sum _{R}\left[v(P_{i}^{R}\cup \left\{i\right\})-v(P_{i}^{R})\right]$

где сумма колеблется по всем $n!$ заказы $R$ игроков и $P_{i}^{R}$ это набор игроков в $N$ которые предшествуют $i$ в порядке $R$. Наконец, это также можно выразить как

$\varphi _{i}(v)={\frac {1}{n}}\sum _{S\subseteq N\setminus \{i\}}{\binom {n-1}{|S|}}^{-1}(v(S\cup \{i\})-v(S))$

который можно интерпретировать как

$\varphi _{i}(v)={\frac {1}{\text{number of players}}}\sum _{{\text{coalitions excluding }}i}{\frac {{\text{marginal contribution of }}i{\text{ to coalition}}}{{\text{number of coalitions excluding }}i{\text{ of this size}}}}$

С точки зрения синергии

Из характеристической функции $v$ можно подсчитать синергию , которую обеспечивает каждая группа игроков. Синергия – уникальная функция $w\colon 2^{N}\to \mathbb {R}$, такой, что

$v(S)=\sum _{R\subseteq S}w(R)$

для любого подмножества $S\subseteq N$ игроков. Другими словами, «общая ценность» коалиции $S$ происходит в результате суммирования синергии каждого возможного подмножества $S$.

Дана характеристическая функция $v$, функция синергии $w$ рассчитывается через

$w(S)=\sum _{R\subseteq S}(-1)^{|S|-|R|}v(R)$

используя принцип исключения включения . Другими словами, синергия коалиции $S$ это ценность $v(S)$ , что еще не учтено его подмножествами.

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

$\varphi _{i}(v)=\sum _{i\in S\subseteq N}{\frac {w(S)}{|S|}}$

где сумма ведется по всем подмножествам $S$ из $N$ включая игрока $i$.

Это можно интерпретировать как

$\varphi _{i}(v)=\sum _{\text{coalitions including i}}{\frac {\text{synergy of the coalition}}{\text{members in the coalition}}}$

Другими словами, синергия каждой коалиции делится поровну между всеми ее членами.

Примеры

Бизнес-пример

Рассмотрим упрощенное описание бизнеса. Владелец, o , обеспечивает важнейший капитал в том смысле, что без него невозможно получить никакую прибыль. Имеется m рабочих w ₁ ,..., w _m , каждый из которых вносит сумму p в общую прибыль. Позволять

$N=\{o,w_{1},\ldots ,w_{m}\}.$

Функция цены для этой коалиционной игры равна

$v(S)={\begin{cases}(|S|-1)p&{\text{if }}o\in S\;,\\0&{\text{otherwise}}\;.\\\end{cases}}$

Вычисление значения Шепли для этой коалиционной игры приводит к значению мп / 2 для владельца и п / 2 на каждого из m работников.

Это можно понять с точки зрения синергии. Функция синергии $w$ является

$w(S)={\begin{cases}p,&{\text{if }}S=\{o,w_{i}\}\\0,&{\text{otherwise}}\\\end{cases}}$

поэтому единственные коалиции, которые создают синергию, — это коалиции один на один между владельцем и любым отдельным работником.

Используя приведенную выше формулу для значения Шепли в терминах $w$ мы вычисляем

$\varphi _{w_{i}}={\frac {w(\{o,w_{i}\})}{2}}={\frac {p}{2}}$

и

$\varphi _{o}=\sum _{i=1}^{m}{\frac {w(\{o,w_{i}\})}{2}}={\frac {mp}{2}}$

Результат также можно понять с точки зрения усреднения по всем ордерам. Данный рабочий присоединяется к коалиции после того, как владелец (и, следовательно, вносит p ) в половину заказов и, таким образом, вносит средний вклад в размере ${\frac {p}{2}}$ при присоединении. Когда владелец присоединяется, в среднем половина работников уже присоединилась, поэтому средний вклад владельца при присоединении составляет ${\frac {mp}{2}}$.

Игра в перчатках

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

$N=\{1,2,3\},$

где у игроков 1 и 2 перчатки для правой руки, а у игрока 3 — перчатка для левой руки.

Функция цены для этой коалиционной игры равна

$v(S)={\begin{cases}1&{\text{if }}S\in \left\{\{1,3\},\{2,3\},\{1,2,3\}\right\};\\0&{\text{otherwise}}.\\\end{cases}}$

Формула для расчета значения Шепли:

$\varphi _{i}(v)={\frac {1}{|N|!}}\sum _{R}\left[v(P_{i}^{R}\cup \left\{i\right\})-v(P_{i}^{R})\right],$

где R — порядок игроков и $P_{i}^{R}$ — это набор игроков из N которые предшествуют i в порядке R. ,

В следующей таблице показаны предельные вклады Игрока 1.

${\begin{array}{|c|r|}{\text{Order }}R\,\!&MC_{1}\\\hline {1,2,3}&v(\{1\})-v(\varnothing )=0-0=0\\{1,3,2}&v(\{1\})-v(\varnothing )=0-0=0\\{2,1,3}&v(\{1,2\})-v(\{2\})=0-0=0\\{2,3,1}&v(\{1,2,3\})-v(\{2,3\})=1-1=0\\{3,1,2}&v(\{1,3\})-v(\{3\})=1-0=1\\{3,2,1}&v(\{1,3,2\})-v(\{3,2\})=1-1=0\end{array}}$

Наблюдать

$\varphi _{1}(v)=\!\left({\frac {1}{6}}\right)(1)={\frac {1}{6}}.$

С помощью аргумента симметрии можно показать, что

$\varphi _{2}(v)=\varphi _{1}(v)={\frac {1}{6}}.$

По аксиоме эффективности сумма всех значений Шепли равна 1, что означает, что

$\varphi _{3}(v)={\frac {4}{6}}={\frac {2}{3}}.$

Свойства

Значение Шепли имеет множество полезных свойств.Примечательно, что это единственное правило оплаты, удовлетворяющее четырем свойствам: эффективность, симметрия, линейность и нулевой игрок. Видеть для получения дополнительных характеристик значения Шепли.

Эффективность

Сумма значений Шепли всех агентов равна стоимости большой коалиции, так что весь выигрыш распределяется между агентами:

$\sum _{i\in N}\varphi _{i}(v)=v(N)$

Доказательство : $\sum _{i\in N}\varphi _{i}(v)={\frac {1}{|N|!}}\sum _{R}\sum _{i\in N}v(P_{i}^{R}\cup \left\{i\right\})-v(P_{i}^{R})={\frac {1}{|N|!}}\sum _{R}v(N)={\frac {1}{|N|!}}|N|!\cdot v(N)=v(N)$

с $\sum _{i\in N}v(P_{i}^{R}\cup \left\{i\right\})-v(P_{i}^{R})$ является телескопической суммой и существует |N|! разные порядки R .

Симметрия

Если $i$ и $j$ два действующих лица эквивалентны в том смысле, что

$v(S\cup \{i\})=v(S\cup \{j\})$

для каждого подмножества $S$ из $N$ который не содержит ни $i$ ни $j$, затем $\varphi _{i}(v)=\varphi _{j}(v)$.

Это свойство также называется равным обращением с равными .

Линейность

Если две коалиционные игры описываются функциями выигрыша $v$ и $w$ объединяются, то распределенные выигрыши должны соответствовать выигрышам, полученным из $v$ и выгоды, полученные от $w$:

$\varphi _{i}(v+w)=\varphi _{i}(v)+\varphi _{i}(w)$

для каждого $i$ в $N$. Также для любого действительного числа $a$,

$\varphi _{i}(av)=a\varphi _{i}(v)$

для каждого $i$ в $N$.

Нулевой игрок

Значение Шепли $\varphi _{i}(v)$ нулевого игрока $i$ в игре $v$ равен нулю. Игрок $i$ является нулевым в $v$ если $v(S\cup \{i\})=v(S)$ для всех коалиций $S$ которые не содержат $i$.

Автономный тест

Если $v$ является субаддитивной функцией множества , т. е. $v(S\sqcup T)\leq v(S)+v(T)$, то для каждого агента $i$: $\varphi _{i}(v)\leq v(\{i\})$.

Аналогично, если $v$ является супераддитивной функцией множества , т. е. $v(S\sqcup T)\geq v(S)+v(T)$, то для каждого агента $i$: $\varphi _{i}(v)\geq v(\{i\})$.

Таким образом, если сотрудничество имеет положительные внешние эффекты, все агенты (слабо) выигрывают, а если оно имеет отрицательные внешние эффекты, все агенты (слабо) проигрывают.

Анонимность

Если $i$ и $j$ два агента и $w$ представляет собой функцию усиления, идентичную $v$ разве что роли $i$ и $j$ были обменены, то $\varphi _{i}(v)=\varphi _{j}(w)$. Это означает, что маркировка агентов не играет роли в распределении их доходов.

Маржинализм

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

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

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

Как видно выше, ценность игры для n человек связывает с каждым игроком ожидание его вклада в ценность коалиции или игроков перед ним в случайном порядке всех игроков. Когда игроков много и каждый человек играет лишь второстепенную роль, набор всех игроков, предшествующих данному, эвристически рассматривается как хорошая выборка игроков, так что ценность данного бесконечно малого игрока колеблется вокруг «его» вклада в ценность «идеальной» выборки всех игроков.

Символически, если v — функция ценности коалиции, связывающая каждую коалицию c с измеренным подмножеством измеримого множества I, которое можно представить как $I=[0,1]$ без потери общности.

$(Sv)(ds)=\int _{0}^{1}(\,v(tI+ds)-v(tI)\,)\,dt.$

где $(Sv)(ds)$обозначает значение Шепли бесконечно малого игрока ds в игре, tI представляет собой идеальный образец набора всех игроков I, содержащего долю t всех игроков, и $tI+ds$ — коалиция, полученная после ds присоединения к tI . Это эвристическая форма диагональной формулы .

Предполагая некоторую регулярность функции ценности, например, предполагая, что v можно представить как дифференцируемую функцию неатомарной меры на I , µ , $v(c)=f(\mu (c))$ с функцией плотности $\varphi$, с $\mu (c)=\int 1_{c}(u)\varphi (u)\,du,$ ( $1_{c}()$ характеристическая функция c ). В таких условиях

$\mu (tI)=t\mu (I)$,

как можно показать, аппроксимировав плотность ступенчатой ​​функцией и сохранив пропорцию t для каждого уровня функции плотности, и

$v(tI+ds)=f(t\mu (I))+f'(t\mu (I))\mu (ds).$

Тогда диагональная формула имеет форму, разработанную Ауманном и Шепли (1974):

$(Sv)(ds)=\int _{0}^{1}f'_{t\mu (I)}(\mu (ds))\,dt$

Выше µ может иметь векторное значение (пока функция определена и дифференцируема в диапазоне µ , приведенная выше формула имеет смысл).

В приведенном выше рассуждении, если мера содержит атомы $\mu (tI)=t\mu (I)$ уже не соответствует действительности — вот почему диагональная формула в основном применима к неатомным играм.

Для расширения этой диагональной формулы были использованы два подхода, когда функция f больше не является дифференцируемой. Мертенс возвращается к исходной формуле и берет производную после интеграла, тем самым получая выгоду от эффекта сглаживания. Нейман придерживался другого подхода. Возвращаясь к элементарному применению подхода Мертенса от Мертенса (1980):

$(Sv)(ds)=\lim _{\varepsilon \to 0,\varepsilon >0}{\frac {1}{\varepsilon }}\int _{0}^{1-\varepsilon }(f(t+\varepsilon \mu (ds))-f(t))\,dt$

Это работает, например, для большинства игр, хотя исходную диагональную формулу нельзя использовать напрямую. Как Мертенс расширяет это далее, определяя симметрии, для которых значение Шепли должно быть инвариантным, и усредняя по таким симметриям, чтобы создать дополнительный эффект сглаживания, коммутируя средние значения с операцией производной, как указано выше. Обзор неатомарных ценностей можно найти в Neyman (2002).

на

Значение Шепли присваивает значения только отдельным агентам. Это было обобщено применить к группе агентов C as,

$\varphi _{C}(v)=\sum _{T\subseteq N\setminus C}{\frac {(n-|T|-|C|)!\;|T|!}{(n-|C|+1)!}}\sum _{S\subseteq C}(-1)^{|C|-|S|}v(S\cup T)\;.$

С точки зрения синергетической функции $w$ выше это читается

$\varphi _{C}(v)=\sum _{C\subseteq T\subseteq N}{\frac {w(T)}{|T|-|C|+1}}$

где сумма учитывает все подмножества $T$ из $N$ которые содержат $C$.

Эта формула предполагает интерпретацию, согласно которой ценность Шепли коалиции следует рассматривать как стандартную ценность Шепли отдельного игрока, если коалиция $C$ рассматривается как одиночный игрок.

Ценность игрока для другого игрока

Значение Шепли $\varphi _{i}(v)$ был разложен в в матрицу значений

$\varphi _{ij}(v)=\sum _{S\subseteq N}{\frac {(|S|-1)!\;(n-|S|)!}{n!}}(v(S)-v(S\setminus \{i\})-v(S\setminus \{j\})+v(S\setminus \{i,j\}))\sum _{t=|S|}^{n}{\frac {1}{t}}$

Каждое значение $\varphi _{ij}(v)$ представляет ценность игрока $i$ игроку $j$. Эта матрица удовлетворяет

$\varphi _{i}(v)=\sum _{j\in N}\varphi _{ij}(v)$

то есть ценность игрока $i$ для всей игры — это сумма их ценности для всех отдельных игроков.

С точки зрения синергии $w$ определено выше, это гласит

$\varphi _{ij}(v)=\sum _{\{i,j\}\subseteq S\subseteq N}{\frac {w(S)}{|S|^{2}}}$

где сумма учитывает все подмножества $S$ из $N$ которые содержат $i$ и $j$.

Это можно интерпретировать как сумму по всем подмножествам, содержащим игроков. $i$ и $j$, где для каждого подмножества $S$ ты

• воспользоваться синергией $w(S)$ из этого подмножества
• разделите его на количество игроков в подмножестве $|S|$. Интерпретируйте это как игрока прибавочной стоимости. $i$ выгоды от этой коалиции
• далее разделите это на $|S|$ чтобы получить роль игрока $i$значение, присвоенное игроку $j$

Другими словами, ценность синергии каждой коалиции поровну делится между всеми $|S|^{2}$ пары $(i,j)$ игроков в этой коалиции, где $i$ генерирует излишек для $j$.

В машинном обучении

Значение Шепли обеспечивает принципиальный способ объяснить предсказания нелинейных моделей, распространенных в области машинного обучения . Интерпретируя модель, обученную на наборе признаков, как функцию ценности коалиции игроков, значения Шепли обеспечивают естественный способ вычислить, какие характеристики способствуют прогнозу. или способствовать неопределенности прогноза. Это объединяет несколько других методов, включая локально интерпретируемые модельно-независимые объяснения (LIME), ДипЛИФТ, и послойное распространение релевантности.

См. также

• Проблема с аэропортом
• Индекс мощности Банцхафа
• Индекс мощности Шепли – Шубика

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

• Фридман, Джеймс В. (1986). Теория игр с приложениями к экономике . Нью-Йорк: Издательство Оксфордского университета. стр. 209–215 . ISBN  0-19-503660-3 .

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

• «Значение Шепли» , Математическая энциклопедия , EMS Press , 2001 [1994]
• Калькулятор стоимости Шепли
• Расчет стоимости проезда на такси с использованием значения Шепли