Problemas en la fundamentación de la teoría de juegos

11

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.

«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í».

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í.

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.

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.

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, y que aquí se publica en dos partes.

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