En la teoría de juegos , un equilibrio correlacionado es un concepto de solución que es más general que el conocido equilibrio de Nash . Fue discutido por primera vez por el matemático Robert Aumann en 1974. [1] [2] La idea es que cada jugador elija su acción de acuerdo con su observación privada del valor de la misma señal pública. Una estrategia asigna una acción a cada observación posible que puede hacer un jugador. Si ningún jugador quisiera desviarse de su estrategia (suponiendo que los demás tampoco se desvíen), la distribución de la que se extraen las señales se llama equilibrio correlacionado.
Equilibrio correlacionado | |
---|---|
Un concepto de solución en la teoría de juegos | |
Relación | |
Superconjunto de | equilibrio de Nash |
Significado | |
Propuesto por | Robert Aumann |
Ejemplo | Pollo |
Definicion formal
Un -Jugador juego de estrategia se caracteriza por un conjunto de acciones y función de utilidad para cada jugador . Cuando jugador elige estrategia y los jugadores restantes eligen un perfil de estrategia descrito por el -tupla , luego jugador la utilidad es .
Una modificación de estrategia para el jugador. es una función . Es decir, le dice al jugador modificar su comportamiento jugando a la acción cuando se le indique jugar .
Dejar ser un espacio de probabilidad contable . Para cada jugador, dejar sea su partición de información, ser es posterior y deja, asignando el mismo valor a los estados en la misma celda de partición de información. Luego es un equilibrio correlacionado del juego estratégico si para cada jugador y para cada modificación de estrategia :
En otras palabras, es un equilibrio correlacionado si ningún jugador puede mejorar su utilidad esperada mediante una modificación de estrategia.
Un ejemplo
D son | C hicken cabo | |
D son | 0, 0 | 7, 2 |
C hicken cabo | 2, 7 | 6, 6 |
Un juego de pollo |
Considere el juego del pollo en la foto. En este juego, dos personas se desafían mutuamente a un concurso en el que cada uno puede atreverse o acobardarse . Si uno se va a atrever, es mejor que el otro se acobarde. Pero si uno va a acobardarse, es mejor que el otro se atreva. Esto conduce a una situación interesante en la que cada uno quiere atreverse, pero solo si el otro puede acobardarse.
En este juego, hay tres equilibrios de Nash . Los dos equilibrios de Nash de estrategia pura son ( D , C ) y ( C , D ). También hay un equilibrio de estrategia mixta en el que ambos jugadores se acobardan con una probabilidad de 1/3.
Ahora considere un tercero (o algún evento natural) que roba una de las tres cartas etiquetadas: ( C , C ), ( D , C ) y ( C , D ), con la misma probabilidad, es decir, probabilidad 1/3 para cada tarjeta. Después de robar la carta, el tercero informa a los jugadores de la estrategia que se les asignó en la carta (pero no de la estrategia asignada a su oponente). Suponga que a un jugador se le asigna D , no querría desviarse suponiendo que el otro jugador jugó su estrategia asignada, ya que obtendrá 7 (la recompensa más alta posible). Supongamos que un jugador se le asigna C . Entonces el otro jugador jugará C con probabilidad 1/2 y D con probabilidad 1/2. La utilidad esperada de Daring es 7 (1/2) + 0 (1/2) = 3.5 y la utilidad esperada de acobardarse es 2 (1/2) + 6 (1/2) = 4. Entonces, el jugador prefiero acobardarse.
Dado que ninguno de los jugadores tiene un incentivo para desviarse, este es un equilibrio correlacionado. La recompensa esperada para este equilibrio es 7 (1/3) + 2 (1/3) + 6 (1/3) = 5 que es más alta que la recompensa esperada del equilibrio de Nash de estrategia mixta.
El siguiente equilibrio correlacionado tiene una recompensa aún mayor para ambos jugadores: Recomiende ( C , C ) con probabilidad 1/2, y ( D , C ) y ( C , D ) con probabilidad 1/4 cada uno. Luego, cuando se recomienda a un jugador que juegue C , ella sabe que el otro jugador jugará D con probabilidad (condicional) 1/3 y C con probabilidad 2/3, y obtiene el pago esperado 14/3, que es igual a (no menos a) el pago esperado cuando juega D . En este equilibrio correlacionado, ambos jugadores obtienen 5.25 de expectativa. Se puede demostrar que este es el equilibrio correlacionado con la suma máxima de los pagos esperados para los dos jugadores.
Una de las ventajas de los equilibrios correlacionados es que son computacionalmente menos costosos que los equilibrios de Nash . Esto se puede captar por el hecho de que calcular un equilibrio correlacionado solo requiere resolver un programa lineal, mientras que resolver un equilibrio de Nash requiere encontrar su punto fijo por completo. [3] Otra forma de ver esto es que es posible que dos jugadores respondan a las jugadas históricas de cada uno de un juego y terminen convergiendo hacia un equilibrio correlacionado. [4]
Referencias
- ^ Aumann, Robert (1974). "Subjetividad y correlación en estrategias aleatorias". Revista de Economía Matemática . 1 (1): 67–96. CiteSeerX 10.1.1.120.1740 . doi : 10.1016 / 0304-4068 (74) 90037-8 .
- ^ Aumann, Robert (1987). "Equilibrio correlacionado como expresión de la racionalidad bayesiana". Econometrica . 55 (1): 1–18. CiteSeerX 10.1.1.295.4243 . doi : 10.2307 / 1911154 . JSTOR 1911154 .
- ^ Papadimitriou, Christos H .; Roughgarden, Tim (2008). "Computación de equilibrios correlacionados en juegos multijugador". J. ACM . 55 (3): 14: 1–14: 29. CiteSeerX 10.1.1.335.2634 . doi : 10.1145 / 1379759.1379762 .
- ^ Foster, Dean P .; Vohra, Rakesh V. (1996). "Aprendizaje calibrado y equilibrio correlacionado". Juegos y comportamiento económico .
Fuentes
- Fudenberg, Drew y Jean Tirole (1991) Teoría de juegos , MIT Press , 1991, ISBN 0-262-06141-4
- Leyton-Brown, Kevin; Shoham, Yoav (2008), Fundamentos de la teoría de juegos: una introducción concisa y multidisciplinaria , San Rafael, CA: Morgan & Claypool Publishers, ISBN 978-1-59829-593-1. Una introducción matemática de 88 páginas; consulte la Sección 3.5. Gratis en línea en muchas universidades.
- Osborne, Martin J. y Ariel Rubinstein (1994). Un curso de teoría de juegos , MIT Press. ISBN 0-262-65040-1 (una introducción moderna a nivel de posgrado)
- Shoham, Yoav; Leyton-Brown, Kevin (2009), Sistemas multiagente: fundamentos algorítmicos, teóricos de juegos y lógicos , Nueva York: Cambridge University Press , ISBN 978-0-521-89943-7. Una referencia integral desde una perspectiva computacional; consulte las Secciones 3.4.5 y 4.6. Descarga gratuita en línea .
- Éva Tardos (2004) Notas de clase de la teoría algorítmica de juegos (tenga en cuenta un error tipográfico importante) [1]
- Iskander Karibzhanov. Código MATLAB para trazar el conjunto de equilibrios correlacionados en un juego de forma normal de dos jugadores
- Noam Nisan (2005) Notas de clase del curso Temas en la frontera de la economía y la computación (la u minúscula debe reemplazarse por u_i) [2]