Valor de Shapley

El valor de Shapley es un concepto de solución en la teoría de juegos cooperativos . Recibió su nombre en honor a Lloyd Shapley , quien lo introdujo en 1951 y ganó el Premio Nobel de Economía por ello en 2012. ^{[1] [2]} A cada juego cooperativo le asigna una distribución única (entre los jugadores) de un excedente total generado por la coalición de todos los jugadores. El valor de Shapley se caracteriza por una colección de propiedades deseables. Hart (1989) proporciona un estudio del tema. ^{[3] [4]}

Formalmente, un juego de coalición se define como: Hay un conjunto N (de n jugadores) y una función que asigna subconjuntos de jugadores a los números reales: , con , donde denota el conjunto vacío. La función se llama función característica. ${\estilo de visualización v}$${\displaystyle v\colon 2^{N}\to \mathbb {R} }$${\displaystyle v(\emptyset )=0}$${\displaystyle \conjunto vacío}$${\estilo de visualización v}$

La función tiene el siguiente significado: si S es una coalición de jugadores, entonces ( S ), llamado el valor de la coalición S , describe la suma total esperada de pagos que los miembros de pueden obtener mediante la cooperación. ${\estilo de visualización v}$${\estilo de visualización v}$${\estilo de visualización S}$

El valor de Shapley es una forma de distribuir las ganancias totales entre los jugadores, suponiendo que todos ellos colaboren. Es una distribución "justa" en el sentido de que es la única distribución con ciertas propiedades deseables que se enumeran a continuación. Según el valor de Shapley, ^[5] la cantidad que se le da al jugador i en un juego de coalición es ${\estilo de visualización (v,N)}$

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

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

donde n es el número total de jugadores y la suma se extiende sobre todos los subconjuntos S de N que no contienen al jugador i , incluido el conjunto vacío. Observe también que es el coeficiente binomial . La fórmula se puede interpretar de la siguiente manera: imaginemos que la coalición se forma de a un actor a la vez, y que cada actor exige su contribución como compensación justa, y luego, para cada actor, tomemos el promedio de esta contribución sobre las posibles permutaciones diferentes en las que se puede formar la coalición. ${\displaystyle {n \elige k}}$${\displaystyle v(S\cup \{i\})-v(S)}$

Una fórmula equivalente alternativa para el valor de Shapley es:

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

donde la suma abarca todos los órdenes de los jugadores y es el conjunto de jugadores que preceden en el orden . ${\estilo de visualización n!}$${\estilo de visualización R}$$Estilo de visualización P_{i}^{R}}$${\estilo de visualización N}$${\estilo de visualización i}$${\estilo de visualización R}$

A partir de la función característica se puede calcular la sinergia que proporciona cada grupo de jugadores. La sinergia es la función única , tal que ${\estilo de visualización v}$${\displaystyle w\colon 2^{N}\to \mathbb {R} }$

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

para cualquier subconjunto de jugadores. En otras palabras, el "valor total" de la coalición surge de sumar las sinergias de cada subconjunto posible de . ${\displaystyle S\subseteq N}$${\estilo de visualización S}$${\estilo de visualización S}$

Dada una función característica , la función de sinergia se calcula mediante ${\estilo de visualización v}$${\estilo de visualización w}$

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

utilizando el principio de inclusión y exclusión . En otras palabras, la sinergia de la coalición es el valor que no se tiene en cuenta en sus subconjuntos. ${\estilo de visualización S}$${\displaystyle v(S)}$

Los valores de Shapley se dan en términos de la función de sinergia por ^{[6] [7]}

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

donde la suma es sobre todos los subconjuntos que incluyen al jugador . ${\displaystyle S}$${\displaystyle N}$${\displaystyle i}$

Esto puede interpretarse como

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

En otras palabras, la sinergia de cada coalición se divide equitativamente entre todos los miembros.

Consideremos una descripción simplificada de una empresa. Un propietario, o , proporciona un capital crucial en el sentido de que, sin él/ella, no se pueden obtener ganancias. Hay m trabajadores w ₁ ,..., w _m , cada uno de los cuales contribuye con una cantidad p a la ganancia total. Sea

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

La función de valor para este juego de coalición es

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

Calcular el valor de Shapley para este juego de coalición conduce a un valor de ⁠diputado/2⁠ para el propietario y ⁠pag/2⁠ para cada uno de los m trabajadores.

Esto se puede entender desde la perspectiva de la sinergia. La función de sinergia es ${\displaystyle w}$

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

Así que las únicas coaliciones que generan sinergia son las uno a uno entre el propietario y cualquier trabajador individual.

Usando la fórmula anterior para el valor de Shapley en términos de calculamos ${\displaystyle w}$

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

y

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

El resultado también puede entenderse desde la perspectiva del promedio de todos los pedidos. Un trabajador determinado se une a la coalición después del propietario (y, por lo tanto, contribuye p ) en la mitad de los pedidos y, por lo tanto, hace una contribución promedio de al unirse. Cuando el propietario se une, en promedio, la mitad de los trabajadores ya se han unido, por lo que la contribución promedio del propietario al unirse es . ${\displaystyle {\frac {p}{2}}}$${\displaystyle {\frac {mp}{2}}}$

El juego de guantes es un juego de coalición en el que los jugadores tienen guantes para la mano izquierda y la derecha y el objetivo es formar parejas.

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

donde los jugadores 1 y 2 tienen guantes en la mano derecha y el jugador 3 tiene un guante en la mano izquierda.

La función de valor para este juego de coalición es

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

La fórmula para calcular el valor de Shapley es

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

donde R es un ordenamiento de los jugadores y es el conjunto de jugadores en N que preceden a i en el orden R.${\displaystyle P_{i}^{R}}$

La siguiente tabla muestra las contribuciones marginales del Jugador 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,3,2\})-v(\{3,2\})=1-1=0\end{array}}}$

Observar

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

Mediante un argumento de simetría se puede demostrar que

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

Debido al axioma de eficiencia, la suma de todos los valores de Shapley es igual a 1, lo que significa que

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

El valor de Shapley tiene muchas propiedades deseables. Cabe destacar que es la única regla de pago que satisface las cuatro propiedades de Eficiencia, Simetría, Linealidad y Jugador nulo. ^[8] Véase ^{[9] : 147–156} para más caracterizaciones del valor de Shapley.

La suma de los valores de Shapley de todos los agentes es igual al valor de la gran coalición, de modo que toda la ganancia se distribuye entre los agentes:

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

Prueba :${\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)}$

ya que es una suma telescópica y hay diferentes ordenamientos . ${\displaystyle \sum _{i\in N}v(P_{i}^{R}\cup \left\{i\right\})-v(P_{i}^{R})}$${\displaystyle |N|!}$${\displaystyle R}$

Si y son dos actores que son equivalentes en el sentido de que ${\displaystyle i}$${\displaystyle j}$

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

para cada subconjunto del cual no contiene ni , entonces . ${\displaystyle S}$${\displaystyle N}$${\displaystyle i}$${\displaystyle j}$${\displaystyle \varphi _{i}(v)=\varphi _{j}(v)}$

Esta propiedad también se llama trato igualitario entre iguales .

Si se combinan dos juegos de coalición descritos por funciones de ganancia y , entonces las ganancias distribuidas deben corresponder a las ganancias derivadas de y las ganancias derivadas de : ${\displaystyle v}$${\displaystyle w}$${\displaystyle v}$${\displaystyle w}$

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

para cada en  . Además, para cualquier número real , ${\displaystyle i}$${\displaystyle N}$${\displaystyle a}$

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

para cada en  . ${\displaystyle i}$${\displaystyle N}$

El valor de Shapley de un jugador nulo en un juego es cero. Un jugador es nulo en si para todas las coaliciones que no contienen . ${\displaystyle \varphi _{i}(v)}$${\displaystyle i}$${\displaystyle v}$${\displaystyle i}$${\displaystyle v}$${\displaystyle v(S\cup \{i\})=v(S)}$${\displaystyle S}$${\displaystyle i}$

Si es una función de conjunto subaditivo , es decir, , entonces para cada agente : . ${\displaystyle v}$${\displaystyle v(S\sqcup T)\leq v(S)+v(T)}$${\displaystyle i}$${\displaystyle \varphi _{i}(v)\leq v(\{i\})}$

De manera similar, si es una función de conjunto superaditiva , es decir, , entonces para cada agente : . ${\displaystyle v}$${\displaystyle v(S\sqcup T)\geq v(S)+v(T)}$${\displaystyle i}$${\displaystyle \varphi _{i}(v)\geq v(\{i\})}$

Así, si la cooperación tiene externalidades positivas, todos los agentes ganan (débilmente), y si tiene externalidades negativas, todos los agentes pierden (débilmente). ^{[9] : 147–156}

Si y son dos agentes, y es una función de ganancia idéntica a excepto que los roles de y se han intercambiado, entonces . Esto significa que el etiquetado de los agentes no juega un papel en la asignación de sus ganancias. ${\displaystyle i}$${\displaystyle j}$${\displaystyle w}$${\displaystyle v}$${\displaystyle i}$${\displaystyle j}$${\displaystyle \varphi _{i}(v)=\varphi _{j}(w)}$

El valor de Shapley se puede definir como una función que utiliza únicamente las contribuciones marginales del jugador como argumentos. ${\displaystyle i}$

En su libro de 1974, Lloyd Shapley y Robert Aumann extendieron el concepto del valor de Shapley a juegos infinitos (definidos con respecto a una medida no atómica ), creando la fórmula diagonal. ^[10] Esta fue posteriormente ampliada por Jean-François Mertens y Abraham Neyman .

Como se ha visto anteriormente, el valor de un juego de n personas asocia con cada jugador la expectativa de su contribución al valor de la coalición de jugadores que lo precede en un orden aleatorio de todos los jugadores. Cuando hay muchos jugadores y cada individuo desempeña sólo un papel menor, el conjunto de todos los jugadores que preceden a uno determinado se considera heurísticamente como una buena muestra de todos los jugadores. El valor de un jugador infinitesimal dado ds se define entonces como "su" contribución al valor de una muestra "perfecta" de todos los jugadores.

Simbólicamente, si v es la función de valor de coalición que asocia cada coalición c con su valor, y cada coalición c es un subconjunto medible del conjunto medible I de todos los jugadores, que asumimos que no tiene pérdida de generalidad, el valor de un jugador infinitesimal ds en el juego es ${\displaystyle I=[0,1]}$${\displaystyle (Sv)(ds)}$

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

Aquí tI es una muestra perfecta del conjunto de todos los jugadores I que contiene una proporción t de todos los jugadores, y es la coalición obtenida después de que ds se une a tI . Esta es la forma heurística de la fórmula diagonal. ^[10]${\displaystyle tI+ds}$

Suponiendo cierta regularidad de la función de valor, por ejemplo, suponiendo que v puede representarse como una función diferenciable de una medida no atómica en I , μ , con función de densidad , con donde es la función característica de c . En tales condiciones ${\displaystyle v(c)=f(\mu (c))}$${\displaystyle \varphi }$${\displaystyle \mu (c)=\int 1_{c}(u)\varphi (u)\,du,}$${\displaystyle 1_{c}(\bullet )}$

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

como se puede demostrar aproximando la densidad mediante una función escalonada y manteniendo la proporción t para cada nivel de la función de densidad, y

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

La fórmula diagonal tiene entonces la forma desarrollada por Aumann y Shapley (1974)

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

Por encima de μ se puede obtener un valor vectorial (siempre que la función esté definida y sea diferenciable en el rango de μ , la fórmula anterior tiene sentido).

En el argumento anterior, si la medida contiene átomos ya no es cierto; es por eso que la fórmula diagonal se aplica principalmente a juegos no atómicos. ${\displaystyle \mu (tI)=t\mu (I)}$

Se han utilizado dos métodos para ampliar esta fórmula diagonal cuando la función f ya no es diferenciable. Mertens vuelve a la fórmula original y toma la derivada después de la integral, beneficiándose así del efecto de suavizado. Neyman adoptó un enfoque diferente. Volviendo a una aplicación elemental del enfoque de Mertens de Mertens (1980): ^[11]

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

Esto funciona, por ejemplo, para juegos mayoritarios, mientras que la fórmula diagonal original no se puede utilizar directamente. Mertens amplía aún más esta idea identificando simetrías en las que el valor de Shapley debería ser invariante y haciendo un promedio sobre dichas simetrías para crear un efecto de suavizado adicional conmutando los promedios con la operación derivada como se indicó anteriormente. ^[12] En Neyman (2002) se encuentra un estudio sobre valores no atómicos ^[13].

El valor de Shapley sólo asigna valores a los agentes individuales. Se ha generalizado ^[14] para aplicarlo a un grupo de agentes C como,

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

En términos de la función de sinergia anterior, esto se lee ^{[6] [7]}${\displaystyle w}$

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

donde la suma cubre todos los subconjuntos de que contienen . ${\displaystyle T}$${\displaystyle N}$${\displaystyle C}$

Esta fórmula sugiere la interpretación de que el valor Shapley de una coalición debe considerarse como el valor Shapley estándar de un solo jugador, si la coalición se trata como un solo jugador. ${\displaystyle C}$

El valor de Shapley se descompuso en ^[15] en una matriz de valores ${\displaystyle \varphi _{i}(v)}$

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

Cada valor representa el valor de jugador a jugador . Esta matriz satisface ${\displaystyle \varphi _{ij}(v)}$${\displaystyle i}$${\displaystyle j}$

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

es decir, el valor del jugador para el juego en su conjunto es la suma de su valor para todos los jugadores individuales. ${\displaystyle i}$

En términos de la sinergia definida anteriormente, esto se lee ${\displaystyle w}$

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

donde la suma cubre todos los subconjuntos de que contienen y . ${\displaystyle S}$${\displaystyle N}$${\displaystyle i}$${\displaystyle j}$

Esto se puede interpretar como la suma de todos los subconjuntos que contienen jugadores y , donde para cada subconjunto se ${\displaystyle i}$${\displaystyle j}$${\displaystyle S}$

• Aprovecha la sinergia de ese subconjunto${\displaystyle w(S)}$
• dividirlo por el número de jugadores en el subconjunto . Interpretar que el jugador con plusvalía gana con esta coalición${\displaystyle |S|}$${\displaystyle i}$
• Divida esto aún más para obtener la parte del valor del jugador que se le atribuye.${\displaystyle |S|}$${\displaystyle i}$${\displaystyle j}$

En otras palabras, el valor de sinergia de cada coalición se divide equitativamente entre todos los pares de jugadores en esa coalición, donde genera excedente para . ${\displaystyle |S|^{2}}$ ${\displaystyle (i,j)}$${\displaystyle i}$${\displaystyle j}$

La regresión del valor de Shapley es un método estadístico que se utiliza para medir la contribución de los predictores individuales en un modelo de regresión. En este contexto, los "jugadores" son los predictores o variables individuales en el modelo, y la "ganancia" es la varianza explicada total o el poder predictivo del modelo. Este método garantiza una distribución justa de la ganancia total entre los predictores, atribuyendo a cada predictor un valor que representa su contribución al desempeño del modelo. Lipovetsky (2006) analizó el uso del valor de Shapley en el análisis de regresión, brindando una descripción general completa de sus fundamentos teóricos y aplicaciones prácticas. ^[16]

Las contribuciones del valor de Shapley son reconocidas por su equilibrio de estabilidad y poder discriminatorio, lo que las hace adecuadas para medir con precisión la importancia de los atributos de servicio en la investigación de mercado. ^[17] Varios estudios han aplicado la regresión del valor de Shapley al análisis de impulsores clave en la investigación de mercado. Pokryshevskaya y Antipov (2012) utilizaron este método para analizar las intenciones de compra repetida de los clientes en línea, demostrando su eficacia para comprender el comportamiento del consumidor. ^[18] De manera similar, Antipov y Pokryshevskaya (2014) aplicaron la regresión del valor de Shapley para explicar las diferencias en las tasas de recomendación de hoteles en el sur de Chipre, destacando su utilidad en la industria hotelera. ^[19] Vriens, Vidden y Bosch (2021) brindan una validación adicional de los beneficios del valor de Shapley en el análisis de impulsores clave y destacaron sus ventajas en el análisis de marketing aplicado. ^[20]

El valor de Shapley proporciona una forma basada en principios para explicar las predicciones de modelos no lineales comunes en el campo del aprendizaje automático . Al interpretar un modelo entrenado en un conjunto de características como una función de valor en una coalición de jugadores, los valores de Shapley proporcionan una forma natural de calcular qué características contribuyen a una predicción ^[21] o contribuyen a la incertidumbre de una predicción. ^[22] Esto unifica varios otros métodos, incluidas las explicaciones locales interpretables independientes del modelo (LIME), ^[23] DeepLIFT, ^[24] y la propagación de relevancia por capas. ^{[25] [26]}

• Problema del aeropuerto
• Índice de potencia de Banzhaf
• Índice de potencia Shapley-Shubik

• Friedman, James W. (1986). Teoría de juegos con aplicaciones a la economía . Nueva York: Oxford University Press. pp. 209–215. ISBN. 0-19-503660-3.

• "Valor de Shapley", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Calculadora del valor de Shapley
• Cálculo de la tarifa de un taxi utilizando el valor Shapley