Valor de Shapley

Lloyd Shapley en 2012

En la teoría de juegos, el valor de Shapley, nombrado en honor de Lloyd Shapley, quien lo introdujo en 1953, es un método de distribución de riquezas en la teoría de juegos cooperativos.​​ Para cada juego cooperativo se asigna un único reparto (entre los jugadores) del beneficio total generado por la coalición de todos los jugadores. El valor de Shapley se caracteriza por una colección de propiedades deseables o axiomas que se describen a continuación. Hart (1989) ofrece un análisis del tema.​​

La configuración es como sigue: una coalición de jugadores coopera, y obtiene una cierta ganancia general de la cooperación. Dado que algunos jugadores pueden contribuir más a la coalición que otros, o pueden poseer diferente poder de negociación (por ejemplo, amenazando con destruir todo el excedente), ¿qué reparto final de los beneficios de la cooperación entre los jugadores debemos esperar que surjan en cualquier juego en particular? O expresado de otra manera: ¿qué importancia tiene cada jugador para la cooperación global, y qué recompensa puede él o ella razonablemente esperar? El valor de Shapley ofrece una posible respuesta a esta pregunta.

Definición formal

Para formalizar esta situación, utilizamos la noción de un juego de coalición: comenzamos con un grupo N (de n jugadores) y una función $v\;:\;2^{N}\to \mathbb {R}$ con $v(\emptyset )=0$, donde $\emptyset$ denota el conjunto vacío. La función $v$ que asigna subconjuntos de actores reales se llama función característica.

La función $v$ tiene el siguiente significado: si S es una coalición de jugadores, entonces v(S), llamado el valor de la coalición $S$, describe la suma total de los pagos a los miembros de S que se puede obtener por dicha cooperación.

El valor de Shapley es una manera de distribuir las ganancias totales a los jugadores, en el supuesto de que todos colaboran formando una gran coalición. 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. De acuerdo con el valor de Shapley, la cantidad que el jugador i obtiene durante un juego de coalición $(v,N)$ es:

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

Donde n es el número total de jugadores y la suma se extiende sobre todos los subconjuntos de N que no contiene el jugador i. La fórmula se puede interpretar de la siguiente manera: imaginar que la coalición está formando un actor a la vez, con cada actor exigiendo su contribución v (S ∪ {i}) - v (S) como una compensación justa, y luego para cada actor tomar el promedio de esta contribución sobre las diferentes posibles permutaciones en la que se puede formar la coalición.

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

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

donde la suma se extiende sobre todo $|N|!$ ordenando $R\,\!$ de los jugadores y $P_{i}^{R}\,\!$ es el conjunto de jugadores en $N\,\!$ que preceden $i\,\!$ en el orden $R\,\!$.

Ejemplo

Considere la posibilidad de una descripción simplificada de un negocio. Tenemos un propietario o, que no trabaja, sino que aporta el capital fundamental, lo que significa que sin él no se pueden obtener ganancias. Luego tenemos k trabajadores w₁, ..., w_k, cada uno de los cuales contribuye con una cantidad p de la utilidad total. Por lo tanto, la coalición es N = {O, w₁, ..., w_k} w y el valor v v(S) = 0 si o no es un miembro de S y V(S) = mp si S contiene el propietario y m trabajadores. Calcular el valor de Shapley para este juego de coalición lleva a un valor de kp / 2 para el propietario y p / 2 para cada trabajador.

Este juego es un juego de coalición, equivalente a que los jugadores tengan guantes izquierdos y derechos y deban formar parejas para darles valor. Si tenemos

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

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

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

$v(S)={\begin{cases}1,&{\text{Si }}S\in \left\{\{1,3\},\{2,3\},\{1,2,3\}\right\}\\0,&{\text{De cualquier otro modo}}\\\end{cases}}$

Cuando la fórmula para calcular el valor de Shapley es:

$\phi _{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 $P_{i}^{R}\,\!$ es el conjunto de actores en $N\,\!$ que preceden $i\,\!$ en el orden $R\,\!$

La siguiente tabla muestra las contribuciones marginales del jugador 1:

Order $R\,\!$	$MC_{1}$
${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\,\!$

$\phi _{1}(v)=(1)\!\left({\frac {1}{6}}\right)={\frac {1}{6}}\,\!$

Por un argumento de simetría se puede demostrar que

$\phi _{2}(v)=\phi _{1}(v)={\frac {1}{6}}\,\!$

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

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

El problema del aeropuerto

El problema del aeropuerto es un tipo de juego de división justa en el que se decide cómo distribuir el costo de un aeropuerto de la pista entre los diferentes actores que necesitan pistas de diferentes longitudes. El problema fue introducido por Stephen Littlechild y G. Owen en 1973. Los autores señalan que el conjunto resultante de las tasas de aterrizaje es el valor de Shapley para un juego definido adecuadamente.

Propiedades

El valor de Shapley tiene las siguientes propiedades deseables:

1. Eficiencia: La ganancia total se distribuye:

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

2. Simetría: si i y j son dos actores que son equivalentes en el sentido de que:

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

para cada subconjunto S de N que no contiene i ni j, entonces φ_i(v) = φ_j(v).

3. Linealidad: Si dos juegos cooperativos descritos por las funciones de ganancia v y w son combinados, entonces la ganancia distribuida debería corresponder a la ganancia derivada de v y w:

$\phi _{i}(v w)=\phi _{i}(v) \phi _{i}(w)$ por cada i en N.

También, por cada número real a:

$\phi _{i}(av)=a\phi _{i}(v)$ por cada i en N.

4. Zero Player (Jugador Nulo): El valor de Shapley $\phi _{i}(v)$ de un jugador nulo i en un juego v es cero. Un jugador "i" es nulo en v si $v$ if $v(S\cup \{i\})=v(S)$ para todas las coaliciones S.

De hecho, dado un conjunto de N jugadores, el valor de Shapley es el único mapa a partir del conjunto de todos los juegos de vectores de ganancias que satisface todas las cuatro propiedades aquí mencionadas.

Definiciones de adición

1. Anónimo: Si i y j son dos actores, y w es la función de ganancia que actúa igual que v, excepto que los roles de i y j se han intercambiado, entonces φ_i(v) = φ_j(w). En esencia, esto significa que el etiquetado de los actores no juega un papel en la asignación de sus ganancias. Dicha función se dice que es anónima.

2. Marginalismo: el valor de Shapley puede definirse como una función que utiliza sólo las contribuciones marginales del jugador i como argumentos.

Referencias

• Datos: Q240046