Puede tomar todo el tiempo del Universo encontrar un equilibrio de Nash

En la teoría de juegos, no hay un camino claro hacia el equilibrio

La noción de equilibrio de John Nash es omnipresente en la teoría económica, pero un nuevo estudio muestra que a menudo es imposible llegar de manera eficiente.


Laberinto de equilibrio de Nash

Todos los juegos tienen un equilibrio de Nash. ¿Pero los jugadores podrán alcanzarlo?

Erica Klarreich |Corresponsal contribuyente
Quanta Magazine



En 1950, John Nash, el matemático que luego apareció en el libro y la película "A Beautiful Mind", escribió un artículo de dos páginas que transformó la teoría de la economía. Su idea crucial, pero completamente simple, era que cualquier juego competitivo tiene una noción de equilibrio: una colección de estrategias, una para cada jugador, de modo que ningún jugador pueda ganar más al cambiar unilateralmente a una estrategia diferente.

El concepto de equilibrio de Nash, que le valió el Premio Nobel de economía en 1994, ofrece un marco unificado para comprender el comportamiento estratégico no solo en economía, sino también en psicología, biología evolutiva y muchos otros campos. Su influencia en la teoría económica "es comparable a la del descubrimiento de la doble hélice del ADN en las ciencias biológicas", escribió Roger Myerson, de la Universidad de Chicago, otro Nobel de economía.

Cuando los jugadores están en equilibrio, nadie tiene una razón para desviarse. Pero, ¿cómo llegan los jugadores al equilibrio en primer lugar? En contraste con, digamos, una bola que rueda cuesta abajo y se detiene en un valle, no hay una fuerza obvia que guíe a los jugadores del juego hacia un equilibrio de Nash.

El trabajo de John Nash en teoría de juegos transformó la economía.

"Siempre ha sido una espina para los microeconomistas", dijo Tim Roughgarden, un científico informático teórico en la Universidad de Stanford. "Usan estos conceptos de equilibrio, y los están analizando como si las personas estuvieran en equilibrio, pero no siempre hay una explicación satisfactoria de por qué las personas estarán en equilibrio de Nash en lugar de simplemente buscar a tientas por uno".

Si las personas juegan solo una vez, a menudo no es razonable esperar que encuentren un equilibrio. Este es especialmente el caso si, como es típico en el mundo real, cada jugador sabe solo cuánto ella misma valora los diferentes resultados del juego, y no cuánto lo hacen sus compañeros. Pero si las personas pueden jugar repetidamente, tal vez podrían aprender de las primeras rondas y dirigirse rápidamente hacia un equilibrio. Sin embargo, los intentos por encontrar métodos de aprendizaje tan eficientes siempre han resultado secos.

"Los economistas han propuesto mecanismos para que puedas converger [rápidamente] al equilibrio", dijo Aviad Rubinstein, quien está terminando un doctorado en informática teórica en la Universidad de California en Berkeley. Pero para cada uno de esos mecanismos, dijo, "hay juegos simples que puedes construir donde no funcionan".
59: 12/14: 43

Ahora, Rubinstein y Yakov Babichenko, matemático del Instituto de Tecnología Technion-Israel en Haifa, han explicado por qué. En un artículo publicado en línea en septiembre pasado, demostraron que ningún método de adaptación de estrategias en respuesta a juegos anteriores, no importa cuán cómodos, creativos o inteligentes, converjan de manera eficiente incluso en un equilibrio de Nash aproximado para cada juego posible. Es "un resultado negativo muy arrollador", dijo Roughgarden.

Los economistas a menudo usan los análisis de equilibrio de Nash para justificar las reformas económicas propuestas, dijo Myerson. Pero el nuevo resultado dice que los economistas no pueden suponer que los jugadores del juego llegarán a un equilibrio de Nash, a menos que puedan justificar lo que es especial sobre el juego en cuestión. "Si está tratando de averiguar si su juego encontrará fácilmente un equilibrio", dijo Noam Nisan, un científico informático de la Universidad Hebrea, "depende de usted proporcionar el argumento de por qué sería".
Juegos multijugador

En algunos juegos simples, es fácil detectar los equilibrios de Nash. Por ejemplo, si prefiero la comida china y usted prefiere la italiana, pero nuestra preferencia más fuerte es cenar juntos, hay dos equilibrios obvios para que ambos vayamos al restaurante chino o los dos vayamos al restaurante italiano. Incluso si comenzamos a conocer solo nuestras preferencias y no podemos comunicar nuestras estrategias antes del juego, no tomará demasiadas rondas de conexiones perdidas y cenas solitarias antes de que entendamos las preferencias de los demás y, con suerte, encontremos nuestro camino. a uno u otro equilibrio.

Pero imagínese si los planes de la cena incluyeran a 100 personas, cada una de las cuales ha decidido preferencias sobre con qué otras personas le gustaría cenar y ninguna de las cuales conoce las preferencias de otra persona. Nash demostró en 1950 que incluso los juegos grandes y complicados como este siempre tienen un equilibrio (al menos, si se amplía el concepto de una estrategia para permitir elecciones al azar, como elegir el restaurante chino con un 60% de probabilidad). Pero Nash, quien murió en un accidente automovilístico en 2015, no dio ninguna receta sobre cómo calcular ese equilibrio.

Aviad Rubinstein ayudó a demostrar que los jugadores del juego no necesariamente encontrarán un equilibrio de Nash.

Al sumergirse en el meollo de la prueba de Nash, Babichenko y Rubinstein pudieron demostrar que, en general, no hay un método garantizado para que los jugadores encuentren un equilibrio de Nash aproximado a menos que se digan prácticamente todo sobre sus preferencias respectivas. Y a medida que aumenta el número de jugadores en un juego, la cantidad de tiempo requerido para toda esta comunicación se vuelve rápidamente prohibitiva.

Por ejemplo, en el juego de restaurante para 100 jugadores, hay 2100 formas en que el juego podría jugarse, y por lo tanto, 2100 preferencias que cada jugador tiene que compartir. En comparación, la cantidad de segundos que han transcurrido desde el Big Bang es solo de unos 259.

Este cuello de botella en la comunicación significa que todos los métodos posibles para adaptar estrategias de una ronda a otra no servirán para guiar a los jugadores de manera eficiente hacia un equilibrio de Nash en al menos algunos juegos complejos (como un juego de restaurante para 100 jugadores con preferencias complicadas). Después de todo, en cada ronda, los jugadores aprenden solo un poco de información nueva sobre los demás: qué contentos están con el arreglo de cena individual que se jugó. Así que tomará el orden de las 2100 rondas antes de que sepan todo sobre los valores de los demás (para cuando, presumiblemente, los restaurantes chinos e italianos habrán cerrado).

"Si esto va a llevar más tiempo que la edad del universo", dijo Sergiu Hart, un teórico del juego en la Universidad Hebrea de Jerusalén, "es completamente inútil, por supuesto".

Puede parecer natural, casi obvio, que los jugadores a veces necesitarán saber todo sobre los valores de los demás para encontrar un equilibrio de Nash. El nuevo documento muestra, sin embargo, que esta misma limitación se mantiene incluso si los jugadores están dispuestos a conformarse con un equilibrio de Nash aproximado: un hallazgo importante cuando se trata de aplicaciones del mundo real, en las que se obtiene un resultado cercano al equilibrio de Nash. a menudo lo suficientemente bueno

Yakov Babichenko ayudó a demostrar que alcanzar un equilibrio de Nash podría llevar más tiempo que la edad del universo.

El resultado de Babichenko y Rubinstein no implica que todos los juegos, o incluso la mayoría, estén sujetos a esta limitación, solo que algunos juegos sí lo harán. Muchos de los juegos que usan los economistas para modelar el mundo real tienen una estructura adicional que reduce considerablemente la cantidad de información que cada jugador debe comunicar. Por ejemplo, si 100 de nosotros elegimos una de las dos rutas para nuestro viaje por la mañana, es probable que no te importe qué jugadores van en cada ruta, solo te importa cuántas personas van. Eso significa que su colección de preferencias tendrá un alto grado de simetría, y potencialmente puede transmitir su totalidad en un par de oraciones bien elegidas en lugar de 2100 de ellas.

Los economistas podrían usar tales argumentos para justificar por qué el equilibrio de Nash podría alcanzarse para juegos particulares. Pero el nuevo resultado implica que tales justificaciones deben hacerse caso por caso; no hay un argumento de muerte que cubra todos los juegos todo el tiempo.

Además, a pesar de que muchos juegos que han evolucionado junto con la civilización pueden ser susceptibles a tales simplificaciones, la era de Internet está dando lugar a todo tipo de juegos nuevos para múltiples jugadores, desde sitios de citas hasta transacciones de acciones en línea. "En este punto, no tenemos la lenta evolución de la humanidad que solo nos guía hacia juegos donde es fácil encontrar un equilibrio", dijo Nisan. "Diseñamos juegos nuevos, y si suponemos que vamos a lograr un equilibrio, muy a menudo nos vamos a equivocar".

En la vida real, las personas a menudo no juegan juegos de equilibrio, algo que los economistas conocen muy bien, dijo Andrew McLennan, economista de la Universidad de Queensland en Brisbane, Australia. Pero, dijo, "la economía no tiene ninguna estructura teórica para preguntar qué tan precisa puede ser la economía". Los resultados teóricos de la informática, como el nuevo de Babichenko y Rubinstein, "deberían ser una inspiración para abordar el problema de manera formal" él dijo.

Pero los dos campos tienen una mentalidad muy diferente, lo que puede obstaculizar la comunicación interdisciplinaria: los economistas tienden a buscar modelos simples que capten la esencia de una interacción compleja, mientras que los científicos de la computación teórica suelen estar más interesados ​​en comprender qué sucede a medida que los modelos se vuelven cada vez más complejos. "Desearía que mis colegas en economía estuvieran más conscientes, más interesados ​​en lo que está haciendo la informática", dijo McLennan.
Un asesor de confianza

El nuevo trabajo traza una brillante línea divisoria entre el equilibrio de Nash y otro concepto de equilibrio más general que se destacó 24 años después del artículo de Nash. "Equilibrio correlacionado", propuesto en 1974 por Robert Aumann, otro Nobel de economía, plantea un escenario en el que los jugadores reciben consejos de un mediador confiable (o "dispositivo de correlación") sobre qué estrategia jugar. El consejo del mediador forma un equilibrio correlacionado si ningún jugador individual tiene un incentivo para desviarse del consejo que ha recibido, si cree que los otros jugadores están siguiendo cada uno su propio consejo.

Esto puede sonar al principio como una construcción arcana, pero en realidad usamos equilibrios correlacionados todo el tiempo, cuando, por ejemplo, dejamos que un sorteo de monedas decida si saldremos para chino o italiano, o permitiremos que un semáforo dicte Cuál de nosotros pasará primero por una intersección.

Robert Aumann inventó el concepto de equilibrio correlacionado.

En estos dos ejemplos, cada jugador sabe exactamente qué consejo le da el "mediador" al otro jugador, y el consejo del mediador esencialmente ayuda a los jugadores a coordinar qué equilibrio de Nash jugarán. Pero cuando los jugadores no saben exactamente qué consejos están recibiendo los demás, solo cómo los diferentes tipos de consejos se correlacionan entre sí, Aumann demostró que el conjunto de equilibrios correlacionados puede contener más que solo combinaciones de equilibrios de Nash: puede incluir formas de juego que no son en absoluto los equilibrios de Nash, pero que a veces resultan en un resultado social más positivo que cualquiera de los equilibrios de Nash. Por ejemplo, en algunos juegos en los que cooperar rendiría un beneficio total más alto para los jugadores que actuar de manera egoísta, el mediador a veces puede engañar a los jugadores para que cooperen ocultando el consejo que les da a los otros jugadores. Este hallazgo, dijo Myerson, fue "un rayo del azul".

Y aunque un mediador puede dar muchos tipos diferentes de consejos, el conjunto de equilibrios correlacionados de un juego, que está representado por una colección de ecuaciones lineales y desigualdades, es matemáticamente más manejable que el conjunto de equilibrios de Nash. "Esta otra forma de pensar sobre esto, las matemáticas es mucho más hermosa", dijo Myerson.

Si bien Myerson ha calificado la visión de la teoría de juegos de Nash como "uno de los avances intelectuales más destacados del siglo XX", considera que el equilibrio correlacionado es quizás un concepto aún más natural que el equilibrio de Nash. Ha opinado en numerosas ocasiones que "si hubiera vida inteligente en otros planetas, en la mayoría de ellos habrían descubierto el equilibrio correlacionado antes del equilibrio de Nash".

Cuando se trata de repetidas rondas de juego, muchas de las formas más naturales que los jugadores pueden elegir para adaptar sus estrategias convergen, en un sentido particular, a los equilibrios correlacionados. Tomemos, por ejemplo, los enfoques de "minimización de arrepentimiento", en los cuales, antes de cada ronda, los jugadores aumentan la probabilidad de usar una estrategia determinada si se arrepienten de no haber jugado más en el pasado. La minimización por arrepentimiento es un método "que tiene cierta semejanza con la vida real: prestar atención a lo que funcionó bien en el pasado, combinado con experimentar un poco ocasionalmente", dijo Roughgarden.

Para muchos enfoques que minimizan el arrepentimiento, los investigadores han demostrado que el juego convergerá rápidamente a un equilibrio correlacionado en el siguiente sentido sorprendente: después de que tal vez se hayan jugado 100 rondas, el historial del juego se verá esencialmente igual que si un mediador hubiera estado aconsejando a los jugadores todo el tiempo. Es como si "el dispositivo [correlativo] se encontrara implícitamente de alguna manera, a través de la interacción", dijo Constantinos Daskalakis, un científico informático teórico del Instituto de Tecnología de Massachusetts.

A medida que el juego continúa, los jugadores no se mantendrán necesariamente en el mismo equilibrio correlacionado; después de 1,000 rondas, por ejemplo, pueden haberse desplazado a un nuevo equilibrio, de modo que ahora su historial de 1,000 juegos parece haber sido guiado por un Mediador diferente al anterior. El proceso recuerda a lo que sucede en la vida real, dijo Roughgarden, a medida que las normas sociales sobre las cuales se debe jugar el equilibrio evolucionan gradualmente.

En el tipo de juegos complejos para los cuales el equilibrio de Nash es difícil de alcanzar, el equilibrio correlacionado es "el principal candidato natural" para un concepto de solución de reemplazo, dijo Nisan.

El hecho de que a la humanidad se le haya ocurrido la idea del equilibrio de Nash antes del equilibrio correlacionado puede ser solo un accidente de la historia, dijo Myerson. "La gente piensa que las ideas que evolucionaron antes son las más fundamentales", dijo, pero en este caso, "¿quién puede decir qué es una idea más fundamental?"

Sin embargo, los resultados sobre la rápida convergencia no implican que ninguna ronda individual del juego se juegue en un equilibrio correlacionado, solo que la historia a largo plazo del juego sí lo es. Esto significa, señaló Rubinstein, que los enfoques de minimización de arrepentimiento no son siempre una opción ideal para los jugadores racionales en una ronda cualquiera. Eso deja la pregunta "¿Qué harán los jugadores racionales?" Sin una respuesta definitiva.

Esta pregunta "ha sido explorada desde antes de que yo naciera", dijo Rubinstein, de 30 años. "Pero aún es el principio".