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

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

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

Схема такова: коалиция игроков сотрудничает и получает от этого сотрудничества определенную общую выгоду. Поскольку одни игроки могут вносить больший вклад в коалицию, чем другие, или могут обладать разной переговорной силой (например, угрожая уничтожить весь излишек), какое окончательное распределение образованного излишка между игроками должно возникнуть в каждой конкретной игре? Или иначе говоря: насколько важен каждый игрок для общего сотрудничества и какой выигрыш он или она может ожидать? Значение Шепли дает один из возможных ответов на этот вопрос.

Для игр с разделением затрат с вогнутыми функциями затрат оптимальное правило разделения затрат, которое оптимизирует цену анархии , за которой следует цена стабильности , и есть правило разделения затрат Шепли. ^[5]

Формальное определение [ править ]

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

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

Значение Шепли - это один из способов распределить общую прибыль между игроками, предполагая, что все они сотрудничают. Это «справедливое» распределение в том смысле, что это единственное распределение с определенными желательными свойствами, перечисленными ниже. Согласно значению Шепли, ^[6] сумма, которую получает игрок i за коалиционную игру, равна${\ Displaystyle (v, N)}$

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

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

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

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

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

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

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

${\displaystyle \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}}}}}$

Примеры [ править ]

Деловой пример [ править ]

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

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

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

${\displaystyle v(S)={\begin{cases}mp,&{\text{if }}o\in S\\0,&{\text{otherwise}}\\\end{cases}}}$

где m - мощность . Вычисление значения Шепли для этой коалиционной игры приводит к значению${\displaystyle S\setminus \{o\}}$mp/2 для собственника и п/2для каждого из m рабочих.

Игра с перчатками [ править ]

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

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

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

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

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

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

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

где R представляет собой упорядочение игроков и есть множество игроков в N , которые предшествуют я в порядке R .${\displaystyle P_{i}^{R}}$

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

${\displaystyle {\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,2,3\})-v(\{2,3\})=1-1=0\end{array}}}$

Наблюдать

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

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

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

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

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

Свойства [ править ]

Ценность Шепли обладает многими желательными свойствами.

Эффективность [ править ]

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

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

Доказательство :${\displaystyle \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)}$

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

Симметрия [ править ]

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

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

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

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

Линейность [ править ]

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

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

за каждый ин  . Кроме того , для любого действительного числа ,${\displaystyle i}$${\displaystyle N}$${\displaystyle a}$

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

за каждый ин  .${\displaystyle i}$${\displaystyle N}$

Нулевой игрок [ править ]

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

Для данного набора игроков значение Шепли является единственной картой из набора всех игр для векторов выплат, которая удовлетворяет всем четырем свойствам: Эффективность, Симметрия, Линейность, Нулевой игрок.${\displaystyle N}$

Автономный тест [ править ]

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

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

Таким образом, если кооперация имеет положительные внешние эффекты, все агенты (слабо) выигрывают, а если она имеет отрицательные внешние эффекты, все агенты (слабо) проигрывают. ^{[7] : 147–156}

Анонимность [ править ]

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

Маржинализм [ править ]

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

Характеристика [ править ]

Значение Шепли не только имеет желаемые свойства, но и является единственным правилом оплаты, удовлетворяющим некоторому подмножеству этих свойств. Например, это единственное правило оплаты, удовлетворяющее четырем свойствам: Эффективность, Симметрия, Линейность и Нулевой игрок. ^[8] См. ^{[7] : 147–156} для получения дополнительных характеристик.

Значение Ауманна – Шепли [ править ]

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

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

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

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

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

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

${\displaystyle \mu (tI)=t\mu (I)}$,

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

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

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

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

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

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

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

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

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

Обобщение на коалиции [ править ]

Значение Шепли присваивает значения только отдельным агентам. Он был обобщен ^[13] для применения к группе агентов C следующим образом:

${\displaystyle \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)\;.}$

В машинном обучении [ править ]

Значение Шепли обеспечивает принципиальный способ объяснения предсказаний нелинейных моделей, распространенных в области машинного обучения . Интерпретируя модель, обученную набору характеристик, как функцию ценности для коалиции игроков, значения Шепли обеспечивают естественный способ вычисления того, какие особенности вносят вклад в прогноз. ^[14] Это объединяет несколько других методов, включая локально интерпретируемые независимые от модели объяснения (LIME), ^[15] DeepLIFT, ^[16] и послойное распространение релевантности. ^[17]

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

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