Equilibrio correlacionado

Solución de teoría de juegos

En 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 elige 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 posible observación que un jugador puede hacer. 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.

Definición formal

Un juego estratégico de 2 jugadores se caracteriza por un conjunto de acciones y una función de utilidad para cada jugador . Cuando un jugador elige una estrategia y los demás jugadores eligen un perfil de estrategia descrito por la tupla , la utilidad del jugador es . ${\displaystyle N}$ ${\displaystyle \displaystyle (N,\{A_{i}\},\{u_{i}\})}$ ${\displaystyle A_{i}}$ ${\displaystyle u_{i}}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle a_{i}\in A_{i}}$ ${\displaystyle N-1}$ ${\displaystyle a_{-i}}$ ${\displaystyle i}$ ${\displaystyle \displaystyle u_{i}(a_{i},a_{-i})}$

Una modificación de estrategia para el jugador es una función , es decir, le indica al jugador que modifique su comportamiento ejecutando la acción cuando se le indica que lo haga . ${\displaystyle i}$ ${\displaystyle \phi _{i}\colon A_{i}\to A_{i}}$ ${\displaystyle \phi _{i}}$ ${\displaystyle i}$ ${\displaystyle \phi _{i}(a_{i})}$ ${\displaystyle a_{i}}$

Sea un espacio de probabilidad contable . Para cada jugador , sea su partición de información, sea el posterior de y sea , asignando el mismo valor a los estados en la misma celda de la partición de información de . Entonces es un equilibrio correlacionado del juego estratégico si para cada jugador y para cada modificación de estrategia : ${\displaystyle (\Omega ,\pi )}$ ${\displaystyle i}$ ${\displaystyle P_{i}}$ ${\displaystyle q_{i}}$ ${\displaystyle i}$ ${\displaystyle s_{i}\colon \Omega \rightarrow A_{i}}$ ${\displaystyle i}$ ${\displaystyle ((\Omega ,\pi ),P_{i},s_{i})}$ ${\displaystyle (N,A_{i},u_{i})}$ ${\displaystyle i}$ ${\displaystyle \phi _{i}}$

${\displaystyle \sum _{\omega \in \Omega }q_{i}(\omega )u_{i}(s_{i}(\omega ),s_{-i}(\omega ))\geq \sum _{\omega \in \Omega }q_{i}(\omega )u_{i}(\phi _{i}(s_{i}(\omega )),s_{-i}(\omega ))}$

En otras palabras, existe un equilibrio correlacionado si ningún jugador puede mejorar su utilidad esperada mediante una modificación de la estrategia. ${\displaystyle ((\Omega ,\pi ),P_{i})}$

Un ejemplo

Consideremos el juego de la gallina que se muestra en la imagen. En este juego, dos personas se desafían mutuamente a una competición en la que cada uno puede atreverse o acobardarse . Si uno se atreve, es mejor que el otro se acobarde. Pero si uno se acobarda, 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 2/3.

Ahora considere un tercero (o algún evento natural) que saca una de tres cartas etiquetadas: ( C , C ), ( D , C ), y ( C , D ), con la misma probabilidad, es decir, probabilidad 1/3 para cada carta. Después de sacar la carta, el tercero informa a los jugadores de la estrategia asignada a ellos en la carta (pero no la estrategia asignada a su oponente). Supongamos 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 a 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 Atreverse es 7(1/2) + 0(1/2) = 3,5 y la utilidad esperada de acobardarse es 2(1/2) + 6(1/2) = 4. Por lo tanto, el jugador preferiría acobardarse.

Dado que ninguno de los jugadores tiene incentivos para desviarse, se trata de un equilibrio correlacionado. El resultado esperado para este equilibrio es 7(1/3) + 2(1/3) + 6(1/3) = 5, que es mayor que el resultado esperado 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. Entonces, cuando a un jugador se le recomienda jugar C , sabe que el otro jugador jugará D con probabilidad (condicional) 1/3 y C con probabilidad 2/3, y obtiene una recompensa esperada 14/3, que es igual a (no menor que) la recompensa esperada cuando juega D . En este equilibrio correlacionado, ambos jugadores obtienen 5,25 en expectativa. Se puede demostrar que este es el equilibrio correlacionado con la suma máxima de recompensas esperadas para los dos jugadores.

Aprendizaje de equilibrios correlacionados

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 en un juego y terminen convergiendo hacia un equilibrio correlacionado. ^[4]

Referencias

1. 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.
2. 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. S2CID  18649722. 
3. Papadimitriou, Christos H.; Roughgarden, Tim (2008). "Cálculo 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. S2CID  53224027. 
4. 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-1Introducción matemática de 88 páginas; consulte la Sección 3.5. Disponible en línea de forma gratuita. Archivado el 15 de agosto de 2000 en Wayback Machine 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 completa desde una perspectiva computacional; consulte las secciones 3.4.5 y 4.6. Descargable en línea de forma gratuita.
• Éva Tardos (2004) Apuntes de clase de Teoría de juegos algorítmicos (nótese un error tipográfico importante) [1]
• Iskander Karibzhanov. Código MATLAB para representar gráficamente el conjunto de equilibrios correlacionados en un juego de dos jugadores en forma normal
• Noam Nisan (2005) Notas de clase del curso Temas en la frontera entre la economía y la computación (la u minúscula debe reemplazarse por u_i) [2]