El valor de Shapley es un concepto de solución en la teoría de juegos cooperativos . Fue nombrado en honor a Lloyd Shapley , quien lo introdujo en 1951 y ganó el Premio Nobel de Economía por él en 2012. [1] [2] A cada juego cooperativo se 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 una encuesta sobre el tema. [3] [4]
La configuración es la siguiente: una coalición de jugadores coopera y obtiene una cierta ganancia general de esa cooperación. Dado que algunos jugadores pueden contribuir más a la coalición que otros o pueden poseer un poder de negociación diferente (por ejemplo, amenazando con destruir todo el excedente), ¿qué distribución final del excedente generado entre los jugadores debería surgir en cualquier juego en particular? O dicho de otra manera: ¿qué importancia tiene cada jugador para la cooperación general y qué recompensa puede esperar razonablemente? El valor de Shapley proporciona una posible respuesta a esta pregunta.
Para los juegos de costos compartidos con funciones de costos cóncavas, la regla óptima de costos compartidos que optimiza el precio de la anarquía , seguida del precio de la estabilidad , es precisamente la regla de costo compartido del valor de Shapley. [5]
Definicion formal
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 , dónde denota el conjunto vacío. La función se llama función característica.
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 de los miembros de puede obtener mediante la cooperación.
El valor de Shapley es una forma de distribuir las ganancias totales a los jugadores, asumiendo que todos colaboran. 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, [6] la cantidad que el jugador i recibe en un juego de coalición es
donde n es el número total de jugadores y la suma se extiende a todos los subconjuntos S de N que no contienen al jugador i . La fórmula se puede interpretar de la siguiente manera: imagina que la coalición se forma un actor a la vez, con cada actor exigiendo su contribución( S ∪ { i }) -( S ) como una compensación justa, y luego, para cada actor, tome el promedio de esta contribución sobre las posibles permutaciones diferentes en las que se puede formar la coalición.
Una fórmula equivalente alternativa para el valor de Shapley es:
donde la suma se extiende sobre todo pedidos de los jugadores y es el conjunto de jugadores en que preceden en el orden . Finalmente, también se puede expresar como
que se puede interpretar como
Ejemplos de
Ejemplo empresarial
Considere una descripción simplificada de una empresa. Un propietario, o , proporciona un capital crucial en el sentido de que sin ella no se pueden obtener ganancias. Hay m trabajadores w 1 , ..., w m , cada uno de los cuales contribuye con una cantidad p a la ganancia total. Dejar
La función de valor para este juego de coalición es
donde m es la cardinalidad de. Calcular el valor de Shapley para este juego de coalición conduce a un valor demp/2 para el propietario y pag/2para cada uno de los m trabajadores.
Juego de guantes
El juego de guantes es un juego de coalición en el que los jugadores tienen guantes de mano izquierda y derecha y el objetivo es formar parejas. Dejar
donde los jugadores 1 y 2 tienen guantes para la mano derecha y el jugador 3 tiene un guante para la mano izquierda.
La función de valor para este juego de coalición es
La fórmula para calcular el valor de Shapley es
donde R es una ordenación de los jugadores yes el conjunto de jugadores en N que preceden i en el orden R .
La siguiente tabla muestra las contribuciones marginales del jugador 1.
Observar
Mediante un argumento de simetría se puede demostrar que
Debido al axioma de eficiencia, la suma de todos los valores de Shapley es igual a 1, lo que significa que
Propiedades
El valor de Shapley tiene muchas propiedades deseables.
Eficiencia
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:
Prueba :
desde es una suma telescópica y hay | N |! diferentes ordenamientos R .
Simetría
Si y son dos actores que son equivalentes en el sentido de que
para cada subconjunto de que no contiene ni ni , luego .
Esta propiedad también se denomina trato igual de iguales .
Linealidad
Si dos juegos de coalición descritos por funciones de ganancia y se combinan, entonces las ganancias distribuidas deben corresponder a las ganancias derivadas de y las ganancias derivadas de :
para cada en . Además, para cualquier número real,
para cada en .
Jugador nulo
El valor de Shapley de un jugador nulo en un juego es cero. Un jugadores nulo en Si para todas las coaliciones que no contienen .
Dado un conjunto de jugadores , el valor de Shapley es el único mapa del conjunto de todos los juegos a los vectores de pago que satisface las cuatro propiedades: eficiencia, simetría, linealidad, jugador nulo.
Prueba independiente
Si es una función de conjunto subaditivo , es decir,, luego para cada agente : .
Del mismo modo, si es una función de conjunto superaditiva , es decir,, luego para cada agente : .
Entonces, si la cooperación tiene externalidades positivas, todos los agentes (débilmente) ganan, y si tiene externalidades negativas, todos los agentes (débilmente) pierden. [7] : 147-156
Anonimato
Si y son dos agentes, y es una función de ganancia que es idéntica a excepto que los roles de y han sido intercambiados, entonces . Esto significa que el etiquetado de los agentes no juega un papel en la asignación de sus ganancias.
Marginalismo
El valor de Shapley se puede definir como una función que usa solo las contribuciones marginales del jugador como los argumentos.
Caracterización
El valor de Shapley no solo tiene propiedades deseables, también es la única regla de pago que satisface algún subconjunto de estas propiedades. Por ejemplo, es la única regla de pago que satisface las cuatro propiedades de Eficiencia, Simetría, Linealidad y Jugador nulo. [8] Ver [7] : 147-156 para más caracterizaciones.
Valor de Aumann-Shapley
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. [9] Esto fue ampliado más tarde por Jean-François Mertens y Abraham Neyman .
Como se vio anteriormente, el valor de un juego de n personas asocia a cada jugador la expectativa de su contribución al valor o la coalición o los jugadores antes que él 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 precede a una dada se cree de forma heurística como una muestra de buena de los jugadores por lo que el valor de un determinado jugador infinitesimales ds alrededor como "su" contribución a el valor de una muestra "perfecta" de la población de todos los jugadores.
Simbólicamente, si v es la función de valor de la coalición que se asocia a cada subconjunto medido de la coalición c de un conjunto medible I que se puede considerar sin pérdida de generalidad.
dónde denota el valor de Shapley del jugador infinitesimal ds en el juego, tI es una muestra perfecta del conjunto de todos los jugadores I que contiene una proporción t de todos los jugadores, yes la coalición obtenida después de que ds se une a tI . Esta es la forma heurística de la fórmula diagonal .
Suponiendo cierta regularidad de la función de valor, por ejemplo, suponiendo que v se puede representar como función diferenciable de una medida no atómica en I , μ , con función de densidad , con ( la función característica de c ). Bajo tales condiciones
- ,
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
La fórmula diagonal tiene entonces la forma desarrollada por Aumann y Shapley (1974)
Por encima de μ puede tener 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, por eso la fórmula diagonal se aplica principalmente a juegos no atómicos.
Se implementaron dos enfoques para extender 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 suavizante. Neyman adoptó un enfoque diferente. Volviendo a una aplicación elemental del enfoque de Mertens de Mertens (1980): [10]
Esto funciona, por ejemplo, para juegos mayoritarios, mientras que la fórmula diagonal original no se puede utilizar directamente. Cómo Mertens extiende esto aún más identificando simetrías sobre las que el valor de Shapley debería ser invariable, y promediando dichas simetrías para crear un efecto de suavizado adicional al conmutar los promedios con la operación derivada como se indicó anteriormente. [11] Una encuesta de valor no atómico se encuentra en Neyman (2002) [12]
Generalización a coaliciones
El valor de Shapley solo asigna valores a los agentes individuales. Se ha generalizado [13] para aplicarlo a un grupo de agentes C como,
En aprendizaje automático
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. [14] Esto unifica varios otros métodos, incluidas Explicaciones agnósticas del modelo interpretables localmente (LIME), [15] DeepLIFT, [16] y Propagación de relevancia por capas. [17]
Ver también
Referencias
- ^ Shapley, Lloyd S. (21 de agosto de 1951). "Notas sobre el juego de n-personas - II: El valor de un juego de n-personas" (PDF) . Santa Mónica, California: RAND Corporation.
- ^ Roth, Alvin E., ed. (1988). El valor de Shapley: ensayos en honor a Lloyd S. Shapley . Cambridge: Cambridge University Press. doi : 10.1017 / CBO9780511528446 . ISBN 0-521-36177-X.
- ^ Hart, Sergiu (1989). "Valor de Shapley". En Eatwell, J .; Milgate, M .; Newman, P. (eds.). The New Palgrave: Teoría de juegos . Norton. págs. 210–216. doi : 10.1007 / 978-1-349-20181-5_25 . ISBN 978-0-333-49537-7.
- ^ Hart, Sergiu (12 de mayo de 2016). "Bibliografía de juegos cooperativos: teoría del valor" .
- ^ Phillips, Matthew; Marden, Jason R. (julio de 2018). "Diseño de compensaciones en juegos de costos compartidos cóncavos". Transacciones IEEE sobre control automático . 63 (7): 2242–2247. doi : 10.1109 / tac.2017.2765299 . ISSN 0018-9286 .
- ^ Para una prueba de existencia única, vea Ichiishi, Tatsuro (1983). Teoría de juegos para el análisis económico . Nueva York: Academic Press. págs. 118-120. ISBN 0-12-370180-5.
- ^ a b Herve Moulin (2004). División Justa y Bienestar Colectivo . Cambridge, Massachusetts: MIT Press. ISBN 9780262134231.
- ^ Shapley, Lloyd S. (1953). "Un valor para los juegos de n-personas". En Kuhn, HW; Tucker, AW (eds.). Contribuciones a la teoría de los juegos . Anales de estudios matemáticos. 28 . Prensa de la Universidad de Princeton. págs. 307–317. doi : 10.1515 / 9781400881970-018 . ISBN 9781400881970.
- ^ Aumann, Robert J .; Shapley, Lloyd S. (1974). Valores de los juegos no atómicos . Princeton: Universidad de Princeton. Prensa. ISBN 0-691-08103-4.
- ^ Mertens, Jean-François (1980). "Valores y derivados". Matemáticas de la investigación operativa . 5 (4): 523–552. doi : 10.1287 / moor.5.4.523 . JSTOR 3689325 .
- ^ Mertens, Jean-François (1988). "El valor de Shapley en el caso no diferenciable". Revista Internacional de Teoría de Juegos . 17 (1): 1–65. doi : 10.1007 / BF01240834 .
- ^ Neyman, A., 2002. Valor de los juegos con infinitos jugadores, "Manual de teoría de juegos con aplicaciones económicas", Manual de teoría de juegos con aplicaciones económicas, Elsevier, edición 1, volumen 3, número 3, 00. RJ Aumann & S. Hart (ed.). [1]
- ^ Grabisch, Michel; Roubens, Marc (1999). "Una aproximación axiomática al concepto de interacción entre jugadores en juegos cooperativos". Revista Internacional de Teoría de Juegos . 28 : 547-565. doi : 10.1007 / s001820050125 .
- ^ Lundberg, Scott M .; Lee, Su-In. "Un enfoque unificado para interpretar las predicciones del modelo" . Avances en sistemas de procesamiento de información neuronal . 30 : 4765–4774 . Consultado el 30 de enero de 2021 .
- ^ Ribeiro, Marco Tulio; Singh, Sameer; Guestrin, Carlos (13 de agosto de 2016). "¿Por qué debería confiar en ti?" . Nueva York, NY, EE.UU .: ACM. doi : 10.1145 / 2939672.2939778 . ISBN 978-1-4503-4232-2.
- ^ Shrikumar, Avanti; Greenside, Peyton; Kundaje, Anshul (17 de julio de 2017). "Aprendizaje de características importantes mediante la propagación de diferencias de activación" . PMLR . págs. 3145–3153. ISSN 2640-3498 . Consultado el 30 de enero de 2021 .
- ^ Bach, Sebastián; Binder, Alexander; Montavon, Grégoire; Klauschen, Frederick; Müller, Klaus-Robert; Samek, Wojciech (10 de julio de 2015). Suárez, Oscar Deniz (ed.). "Sobre las explicaciones de píxeles para decisiones de clasificador no lineal por propagación de relevancia de capas" . PLOS ONE . Biblioteca Pública de Ciencias (PLoS). 10 (7): e0130140. doi : 10.1371 / journal.pone.0130140 . ISSN 1932-6203 .
Otras lecturas
- Friedman, James W. (1986). Teoría de juegos con aplicaciones a la economía . Nueva York: Oxford University Press. págs. 209 –215. ISBN 0-19-503660-3.
enlaces externos
- "Valor de Shapley" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
- Calculadora de valor de Shapley