Utilizamos cookies propias y de terceros para mejorar nuestros servicios y facilitarle el uso de la web mediante el análisis de sus preferencias de navegación. También compartimos la información sobre el tráfico por nuestra web a los medios sociales y de publicidad con los que colaboramos. Si continúa navegando, consideramos que acepta nuestra Política de cookies .

Actualidad científica

Síguenos
  • Google+
  • RSS
  • Noticias
  • 25/07/2017

teoría de juegos

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

La noción de equilibrio de John Nash es ubicua en la teoría económica, pero un estudio reciente demuestra que a menudo es imposible alcanzar un equilibrio así de modo eficiente.

arXiv

Menear

Todos los juegos tienen un equilibrio de Nash, pero ¿podrán los jugadores alcanzarlo? [Eric Nyquist para Quanta Magazine].

En 1949 John Nash, el matemático al que se referirían luego el libro y la película Una mente maravillosa, escribió un artículo de dos páginas que transformó la teoría de la economía. La idea esencial, sumamente simple, es que a todo juego competitivo le corresponde una noción de equilibrio: un conjunto de estrategias, una por cada jugador, tal que no hay ningún jugador que pueda ganar más adoptando unilateralmente 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 entender el comportamiento estratégico no solo en economía, sino también en psicología, biología evolutiva y una diversidad de otras disciplinas. 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», según Roger Myerson, de la Universidad de Chicago, que también tiene el premio Nobel de Economía.

Cuando los jugadores se encuentran en el equilibrio, ninguno tiene razón alguna para separarse de él. Pero ¿cómo llegan a ese equilibrio? Al revés que, digamos, una pelota que rueda cuesta abajo y acaba parándose en un llano, no hay una fuerza evidente que los guíe hacia un equilibrio de Nash.

 El trabajo de John Nash sobre la teoría de juegos transformó la teoría económica [Peter Badge].

«Ha sido siempre una espina que los microeconomistas tienen clavada», dice Tim Roughgarden, teórico de la computación de la Universidad Stanford. «Usan esas nociones de equilibrio y las analizan como si la gente estuviese en equilibrio, pero no siempre hay una explicación satisfactoria de por qué la gente está en un equilibrio de Nash en vez de ir a tientas en busca de uno».

Si un juego se juega solo una vez, a menudo no es razonable esperar que las jugadoras encuentren un equilibrio. Especialmente ocurre así cuando, como es habitual en el mundo real, cada una solo sabe cuánto valora ella misma los distintos resultados posibles del juego e ignora cuánto los valoran las demás. Pero si pueden jugar repetidas veces, quizás puedan aprender en las primeras rondas y conducirse rápidamente hacia un equilibrio. Sin embargo, los intentos de encontrar métodos eficientes de aprendizaje siempre han sido en vano.

«Los economistas han propuesto mecanismos por los cuales se podría converger [rápidamente] al equilibrio», dice Aviad Rubinstein, que está terminando un doctorado en teoría de la computación en la Universidad de California en Berkeley. Pero no hay ni uno de esos mecanismos, añade, para el que «no se puedan idear juegos simples en los que no funciona».

Ahora, Rubinstein y Yakov Babichenko, matemático del Tecnion (el Instituto de Tecnología de Israel, en Haifa), han explicado por qué. En un artículo publicado en Internet en septiembre de 2016 han demostrado que ningún método que adapte las estrategias a lo que ha ocurrido en las partidas anteriores, no importa cuán de sentido común, creativo o inteligente sea, convergerá eficientemente para cada juego posible siquiera sea a un equilibrio de Nash aproximado. Es un «resultado negativo que abarca mucho», afirma Roughgarden.

Las economistas se valen a menudo de análisis basados en el equilibrio de Nash para justificar reformas económicas, cuenta Myerson. Pero el nuevo resultado dice que las economistas no pueden presuponer que los jugadores obtendrán un equilibrio de Nash a no ser que puedan justificar qué tiene de especial el juego en cuestión. Según Noam Nisan, científico de la computación de la Universidad Hebrea, «si intentas determinar si tu juego encontrará fácilmente un equilibrio, dependerá de ti proporcionar el argumento que diga por qué va a ser así».

Juegos de muchos jugadores


En algunos juegos simples resulta sencillo dar con equilibrios de Nash. Por ejemplo, si a mí me gusta más la comida china y a usted la italiana, pero la preferencia principal de ambos es cenar juntos, dos equilibrios obvios son que las dos vayamos al restaurante chino o que las dos vayamos al italiano. Incluso aunque al principio solo conozcamos nuestras propias preferencias y no podamos comunicar nuestras estrategias antes del juego, no harán falta muchas rondas de conexiones perdidas y cenas en solitario antes de que entendamos por completo las preferencias de la otra persona y quepa tener la esperanza de que encontraremos nuestro camino hacia uno u el otro equilibrio.

Pero imaginemos que los planes para cenar implican a cien personas, cada una de las cuales tiene sus preferencias acerca de con cuáles de las otras le gustaría cenar y ninguna de las cuales conoce las preferencias de las demás. Nash demostró en 1949 que incluso en juegos grandes y complicados como ese siempre hay un equilibrio (al menos, si el concepto de estrategia se amplia para permitir las decisiones aleatorias, como la de escoger el restaurante chino con unan probabilidad del 60 por ciento). Pero Nash, que murió en un accidente de coche en 2015, no dio las instrucciones de cómo se alcanza un equilibrio así.

 Aviad Rubinstein contribuyó a demostrar que quienes participan en un juego no necesariamente hallarán un equilibrio de Nash [Tselil Schramm].

Sumergiéndose en las entrañas de la prueba de Nash, Babichenko y Rubinstein han mostrado que en general no hay un método que garantice que los jugadores vayan a encontrar siquiera sea un equilibrio de Nash aproximado a no ser que se digan unos a otros prácticamente todo acerca de sus preferencias respectivas. Y a medida que el número de participantes en el juego crece, el tiempo necesario para todas estas comunicaciones se vuelve enseguida prohibitivo.

Por ejemplo, en el juego del restaurante con cien participantes hay 2100 formas en que podría jugarse el juego y por lo tanto 2100 preferencias que cada participante tendría que compartir. En comparación, el número de segundos que han pasado desde la Gran Explosión es de solo unos 259.

Este cuello de botella comunicativo significa que todos los métodos posibles de adopción de estrategias de ronda a ronda fallarán a la hora de guiar eficientemente a las jugadoras hacia un equilibrio de Nash, al menos en algunos juegos complejos (como el del restaurante con cien participantes y preferencias complicadas). Al fin y al cabo, en cada ronda las jugadoras aprenden solo una pizca de nueva información sobre las demás: su satisfacción con la disposición concreta de cenas que se ha producido en la ronda. Se necesitarán, pues, del orden de 2100 rondas antes de que sepan todo acerca de los valores de las demás (y para entonces cabe suponer que los restaurantes chinos e italianos habrán desaparecido hace mucho).

«Si se tarda más que la edad del universo», comenta Sergiu Hart, teórico de juegos de la Universidad Hebrea de Jerusalén, «no servirá de nada, claro está».

 Podría parecer natural, casi evidente, que los jugadores tengan a veces que saberlo todo acerca de los valores de los demás para acabar en un equilibrio de Nash. El nuevo artículo muestra, sin embargo, que esta misma limitación se mantiene en vigor incluso cuando los jugadores están dispuestos a conformarse con un equilibrio de Nash aproximado, hallazgo importante en las aplicaciones en el mundo real, donde suele bastar con un resultado cercano al equilibrio de Nash.

Yakov Babichenko contribuyó a demostrar que en alcanzar un equilibrio de Nash puede tardarse más tiempo que el que el universo lleva existiendo [por cortesía de Yakov Babichenko].

Del resultado de Babichenko y Rubinstein no se sigue que todos los juegos, ni siquiera la mayoría de los juegos, estén sujetos a esa limitación: solo que algunos lo estarán. Muchos de los juegos que utilizan los economistas como modelos del mundo real tienen una estructura adicional que reduce en gran medida la cantidad de información que cada participante debe comunicar. Por ejemplo, si cien personas elegimos una de dos rutas en nuestro viaje de la mañana hacia el trabajo, es probable que no importe quiénes somos en concreto las que escogemos así, sino solo cuántas somos. Quiere decir que el conjunto de preferencias ha de tener un alto grado de simetría, de forma que se pueda expresarlo entero con unas cuantas frases y no con 2100.

Los economistas pueden valerse de argumentos así para justificar que el equilibrio de Nash será accesible en juegos particulares. Pero del nuevo resultado se sigue que esas justificaciones tienen que hacerse caso a caso; no hay un argumento que de una vez por todas cubra todos los juegos todas las veces.

Más aún: aunque muchos juegos que han ido evolucionando con la civilización pueden ser susceptibles de esas simplificaciones, la era de Internet está creando todo tipo de nuevos juegos con una multitud de participantes, de los sitios de citas a la negociación de acciones en la Red. «Llegados a 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», asevera Nisan. «Diseñamos nuevos juegos, y si suponemos que vamos a conseguir un nuevo equilibrio, a menudo nos vamos a equivocar».

En la vida real la gente no juega juegos en un equilibrio, y, según Andrew McLennan, economista de la Universidad de Queensland, en Brisbane, Australia, los economistas tiene plena conciencia de ello. Pero, añade, «la economía no tiene ninguna estructura teórica para preguntarse cómo sería una economía precisa». Los resultados de la ciencia teórica de la computación, como este nuevo de Babichenko y Rubinstein, «deberían ser una inspiración para abordar la cuestión de un modo formal», concluye.

Pero las dos disciplinas tienen unos esquemas mentales muy diferentes, lo que puede dificultan la comunicación entre ambas. Los economistas tienden a buscar modelos simples que capten la esencia de una interacción compleja, mientras que los teóricos de la computación a menudo están más interesados en saber qué pasa cuando los modelos son cada vez más complejos. «Deseo que mis colegas economistas sean más conscientes de lo que está haciendo la ciencia de la computación y le presten más atención», dice McLennan.

Un asesor de fiar


El trabajo de Yakov Babichenko y Aviad Rubinstein dibuja una brillante línea que separa el equilibrio de Nash de otra noción de equilibrio, más general, que irrumpió 24 años después del artículo de Nash. El «equilibrio correlacionado», propuesto en 1974 por Robert Aumann, otro premiado con el Nobel de Economía, plantea una situación en la que cada jugador recibe consejo de un asesor en el que se confía (o de un «dispositivo correlacionador») sobre la estrategia que se va a seguir. El consejo del asesor da lugar a un equilibrio correlacionado, en el que no hay ningún jugador que tenga el incentivo de desviarse del consejo que ha recibido, si cada jugador cree que los demás jugadores siguen los consejos respectivos.

Esto podría parecer a primera vista artificioso, pero lo cierto es que usamos equilibrios correlacionados todo el tiempo; por ejemplo, cuando arrojamos una moneda al aire para decidir si iremos al chino o al italiano, o cuando dejamos que un semáforo nos diga quién debe pasar primero por el cruce.

Robert Aumann creó el concepto de equilibrio correlacionado. [Cortesía de Robert Aumann]

En estos dos ejemplos, cada jugadora sabe exactamente qué consejo está dándole el «mediador» a la otra, y el consejo del mediador, en esencia, ayuda a las jugadoras a coordinar qué equilibrio de Nash jugarán. Pero cuando no se sabe exactamente qué consejos reciben las demás, cuando solo se sabe que los diferentes tipos de consejo están correlacionados entre sí, Aumann mostró que el conjunto de equilibrios corrrelacionados puede contener algo más que meras combinaciones de equilibrios de Nash: puede incluir formas de jugar que no son equilibrios de Nash en absoluto, pero que a veces producen un resultado social más positivo que cualquier equilibrio de Nash. Así, en juegos en los que cooperar arroja un pago total superior a los jugadores que jugar de modo egoísta, la mediadora puede a veces seducir a los jugadores para que cooperen, y lo hace solo con ocultar el consejo que les da a los demás jugadores. Este hallazgo, según Myerson, fue completamente sorprendente.

E incluso aunque una mediadora pudiese dar muchos tipos diferentes de consejo, el conjunto de equilibrios correlacionados de un juego, representado por un conjunto de ecuaciones lineales y de desigualdades, es más tratable matemáticamente que el conjunto de equilibrios de Nash. «Con esta otra forma de pensar, las matemáticas son mucho más bellas», dice Myerson.

Si bien Myerson sostiene que la teoría de juegos entendida conforme a Nash fue «uno de los avances intelectuales más notables del siglo XX», la de equilibrio correlacionado le parece quizás una idea aún más natural que la de equilibrio de Nash. Ha opinado en numerosas ocasiones que «si hay vida inteligente en otros planetas, en la mayor parte de ellos se descubriría el equilibrio correlacionado antes que el equilibrio de Nash».

Cuando hay varias rondas de un juego, muchas de las formas más naturales de adaptar sus estrategias que los jugadores podrían escoger convergen, en un sentido muy determinado, en equilibrios correlacionados. Consideremos, por ejemplo, los métodos de «minimización de arrepentimientos», en los que antes de cada ronda las jugadoras incrementan la probabilidad de usar una estrategia si se arrepienten de no haberla jugado más en el pasado. Como dice Roughgarden, la minimización de arrepentimientos «guarda cierta semejanza con la vida real: prestar atención a lo que funcionó bien en el pasado, combinado con experimentar un poco de vez en cuando».

Se ha demostrado que en muchos métodos de minimización de los arrepentimientos el juego convergerá rápidamente en un equilibrio correlacionado, en el siguiente, y sorprendente, sentido: tras quizá cien rondas, la historia del juego parecerá esencialmente la misma que si una mediadora hubiese estado aconsejando a las jugadoras en todo momento. Es como si «por medio de la interacción se hubiese encontrado implícitamente el dispositivo [correlacionador]», comenta Constantinos Daskalakis, teórico de la computación del Instituto de Tecnología de Massachusetts.

A medida que continúa el juego, los jugadores no permanecerán necesariamente en el mismo equilibrio correlacionado: pasadas mil rondas, digamos, sería posible que hubiesen derivado hacia un nuevo equilibrio, así que entonces su historia de mil rondas parecerá como si hubiese sido guiada por un mediador distinto al anterior. El proceso recuerda a lo que pasa en la vida real, dice Roughgarden, cuando las normas sociales relativas a qué equilibrio se debería jugar evolucionan gradualmente.

En los tipos de juegos complejos en los que el equilibrio de Nash resulta difícil de alcanzar, el equilibrio correlacionado es, según Nisan, «el principal competidor natural» como tipo de solución sustitutivo.

Que la humanidad haya dado con la idea de equilibrio de Nash antes que con la de equilibrio correlacionado podría ser, cree Myerson, solo un accidente de la historia. «Suele pensarse que las ideas que aparecen antes son las más fundamentales», afirma, pero en este caso, «¿quién dirá qué es más fundamental?».

Sin embargo, de los resultados de la convergencia rápida no se sigue que cualquier ronda del juego se juegue conforme a un equilibrio correlacionado, sino solo que la historia a largo plazo del juego se juega así. Significa, señala Rubinstein, que la minimización de los arrepentimientos no es siempre una elección ideal para unos jugadores racionales en una ronda dada. Esto deja a la pregunta de qué harán unos jugadores racionales sin respuesta definitiva.

Esa pregunta «ha estado siendo explorada desde que nací», dice Rubinstein, que tiene treinta años, «pero todavía estamos solo en el principio».

Erica Klarreich/Quanta Magazine

Artículo traducido por Investigación y Ciencia con permiso de QuantaMagazine.org, una publicación independiente promovida por la Fundación Simons para potenciar la comprensión de la ciencia.

Referencia: «Communication complexity of approximate Nash equilibria», Yakov Babichenko y Aviad Rubinstein en arXiv: 1608.06580, 23 de agosto de 2016 (segunda versión: 13 de septiembre de 2016).

Artículos relacionados

BOLETÍN ACTUALIDAD¿Quieres estar al día de la actualidad científica? Recibe el nuevo boletín de actualidad con nuestros mejores contenidos semanales gratuitos (noticias y posts). Si lo deseas también puedes personalizar tu suscripción. BOLETÍN ACTUALIDAD¿Quieres estar al día de la actualidad científica? ¡Recibe el nuevo boletín de contenidos gratuitos! Ver más boletines.