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 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 pueda 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 denomina equilibrio correlacionado.

Definicion formal

Un juego estratégico de jugadores se caracteriza por un conjunto de acciones y una función de utilidad para cada jugador . Cuando el jugador elige la estrategia y los jugadores restantes eligen un perfil de estrategia descrito por la tupla , entonces 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 dice al jugador que modifique su comportamiento realizando una acción cuando se le indique que juegue . ${\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 la posterior y let , asignando el mismo valor a los estados en la misma celda de la partición de información. Entonces existe 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}\left(\phi _{i}\left(s_{i}(\omega )\right),s_{-i}(\omega )\right)}$

En otras palabras, es 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

Considere el juego de la gallina que se muestra en la imagen. En este juego, dos personas se desafían mutuamente en una competencia en la que cada uno puede atreverse o acobardarse . Si uno se va a atrever, más vale que el otro se acobarde. Pero si uno se va a acobardar, más vale que el otro se atreva. Esto lleva a una situación interesante en la que cada uno quiere atreverse, pero sólo si el otro se acobarda.

En este juego hay tres equilibrios de Nash . Los dos equilibrios de Nash de estrategia pura son ( D , C ) y ( C , D ). También existe 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 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 una. tarjeta. Después de robar la carta, el tercero informa a los jugadores de la estrategia que se les ha asignado en la carta (pero no de la estrategia asignada a su oponente). Supongamos que a un jugador se le asigna D , no querrá desviarse suponiendo que el otro jugador haya jugado su estrategia asignada, ya que obtendrá 7 (el pago más alto posible). Supongamos que a un jugador se le asigna C. Luego 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 acobardarme.

Dado que ninguno de los jugadores tiene incentivos para desviarse, éste es un equilibrio correlacionado. El pago esperado para este equilibrio es 7(1/3) + 2(1/3) + 6(1/3) = 5, que es mayor que el pago esperado del equilibrio de Nash con estrategias mixtas.

El siguiente equilibrio correlacionado tiene un beneficio aún mayor para ambos jugadores: recomendar ( 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 obtendrá el pago esperado 14/3, que es igual a (no menos que) el pago esperado cuando juegan D . En este equilibrio correlacionado, ambos jugadores obtienen 5,25 de expectativa. Se puede demostrar que éste es el equilibrio correlacionado con la suma máxima de pagos esperados 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 puede reflejarse en 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 del otro 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". Econométrica . 55 (1): 1–18. CiteSeerX 10.1.1.295.4243 . doi :10.2307/1911154. JSTOR  1911154. S2CID  18649722. 
3. Papadimitriou, Christos H.; Jardín áspero, Tim (2008). "Calcular 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-1. Una introducción matemática de 88 páginas; consulte la Sección 3.5. Gratis en línea Archivado el 15 de agosto de 2000 en Wayback Machine en muchas universidades.
• Osborne, Martín 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 lógicos, algorítmicos y de teoría de juegos, 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. Descargable gratis en línea.
• Éva Tardos (2004) Apuntes de clase sobre 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) Apuntes del curso Temas en la frontera entre Economía y Computación (la u minúscula debe reemplazarse por u_i) [2]