Valor de Shapley

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En la teoría de juegos, el valor de Shapley, nombrado en honor de Lloyd Shapley, quien lo introdujo en 1953, es un concepto de la solución en la teoría de juegos cooperativos.[1] [2] 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 se describen a continuación. Hart (1989) ofrece un análisis del tema.[3] [4]

La configuración es como sigue: una coalición de jugadores coopera, y obtiene una cierta ganancia general de que 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[editar]

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 a una 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 que se espera de los pagos a los miembros del S se puede obtener por la cooperación.

El valor de Shapley es una manera de distribuir las ganancias totales a los jugadores, en el supuesto de que todos los que colaboran. Es una distribución "justo" en el sentido de que es el único de 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 dieron 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 S N no contiene el jugador i. La fórmula se puede interpretar de la siguiente manera: imaginar 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 la promedio de esta contribución sobre los 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[editar]

Juego de guantes[editar]

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 w1, ..., wk, cada uno de los cuales contribuye con una cantidad p de la utilidad total. Por lo tanto la coalición es N = {O, w1, ..., wk} 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\,\!</math> 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[editar]

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[editar]

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)
  1. 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).
  1. Zero Player (Null jugador): El valor de Shapley \phi_i(v) de un jugador nulo i en un juego v es cero. Un jugador yo es nulo en v si v if v(S\cup \{i\}) = v(S) para todas las coaliciones S .

De hecho, dado un conjunto N jugador, 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 de 1, 2, 3, y 4 desde arriba.

Referencias[editar]

  1. Lloyd S. Shapley. "A Value for n-person Games". In Contributions to the Theory of Games, volume II, by H.W. Kuhn and A.W. Tucker, editors. Annals of Mathematical Studies v. 28, pp. 307–317. Princeton University Press, 1953.
  2. Alvin E. Roth (editor). The Shapley value, essays in honor of Lloyd S. Shapley. Cambridge University Press, Cambridge, 1988.
  3. Sergiu Hart, Shapley Value, The New Palgrave: Game Theory, J. Eatwell, M. Milgate and P. Newman (Editors), Norton, pp. 210–216, 1989.
  4. A Bibliography of Cooperative Games: Value Theory by Sergiu Hart[1]