Mostrando entradas con la etiqueta equilibrio de Nash. Mostrar todas las entradas
Mostrando entradas con la etiqueta equilibrio de Nash. Mostrar todas las entradas

jueves, 25 de octubre de 2018

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

jueves, 1 de marzo de 2018

Duopolio: Sangriento Hotelling en Glasgow

Cuando en Glasgow ser vendedor de helados era una profesión de riesgo

Javier Sanz — Historias de la Historia



Si pidiéramos a la gente que elaborase un listado con las profesiones más peligrosas que se le ocurriesen, con casi toda seguridad estarían copadas por empleos del tipo artificiero, domador de leones o gestor de residuos nucleares. Todas estas y algunas más son labores que merecen respeto y reconocimiento por el riesgo que supone para aquellos que eligen desempeñarlas. Pero hubo un lapso de tiempo, hace ya algunos años, en los cuales la profesión más peligrosa que uno podía desarrollar en la ciudad escocesa de Glasgow era, por sorprendente que parezca, la de vendedor de helados.

A finales de la década de los 60 y los 70 se popularizaron los carritos de helados que perviven todavía hoy en día en el Reino Unido. Estos se diversificaron y con el tiempo dejaron de dedicarse en exclusiva a la venta de polos y granizados para distribuir otros productos como alimentos, papel higiénico e incluso medicamentos. Pero el afán de lucro unido a la falta de escrúpulos dieron lugar a un conflicto que se extendió por años y que ha pasado a la historia como “The Glasgow Ice Cream Wars” (La guerra de los carritos de helado de Glasgow), un hecho que parece el argumento de una película de serie B pero que marcó un antes y un después para el país británico en general y la ciudad escocesa en particular.



Ya en los 80, en esta urbe se había creado una especie de duopolio de los carritos que se repartían los Campbell y los hermanos Marchetti. Aunque se habían dividido el territorio, pronto comenzaron a surgir conflictos sobre los puntos de venta. Todo esto puede parecer excesivo si el objetivo es la venta de helados y accesoriamente otros productos, pero lo que no hemos dicho hasta ahora es que los mismos pasaron a ser negocios sumamente rentables a la par que peligrosos porque incluyeron la venta de drogas, especialmente heroína, así como armas y productos robados. La gran capacidad de carga de los camiones, el conocimiento de las calles de sus conductores y las nulas sospechas que en los primeros años pudieran levantar, los convirtieron en las herramientas perfectas para este lucrativo negocio. Entre ambas bandas, así como contra los vendedores independientes, comenzaron a actuar lo que se dio en llamar “frighteners”, mafiosos de baja categoría que utilizaban tácticas de intimidación que incluían lanzamiento de piedras, tiroteos y ataques con arma blanca. Y obviamente, con el tiempo esta violencia fue escalando hasta el punto de generar tensiones mucho mayores.

La muerte de “Fat Boy”

El punto álgido de este episodio se dio en 1984, cuando un distribuidor y propietario de un camión llamado Andrew Doyle, conocido por todos como “Fat Boy”, se negó desde un principio a participar en la venta de otra cosa que no fueran helados. Ni siquiera el tiroteo que sufrió mientras hacía su ruta de reparto logró amedrentarlo. Así que los gánsteres decidieron pasar a un plan mucho más agresivo: durante la madrugada del 16 de abril rociaron con gasolina la puerta de su casa y la incendiaron. El fuego acabó propagándose y matando al desafortunado e íntegro vendedor de helados y a toda su familia: 6 personas en total entre las que se encontraba un bebé de 18 meses. La desesperación echó a las gentes a las calles exigiendo que se tomasen medidas para acabar con la oleada de robos, tiroteos y ajustes de cuentas en las que se había visto inmerso Glasgow. Y comenzaron las presiones judiciales y sociales a la policía para encontrar a los culpables.


Entierro de la familia Doyle

La confesión de un delincuente de poca monta llamado William Love, apresado por el robo en y de vehículos, puso sobred la pista a la policía y consiguieron detener a los autores del incendio y asesinato: dos vendedores de helados llamados Thomas Campbell y Joe Steele, Aunque durante el proceso mantuvieron su inocencia, e incluso llegaron a protagonizar huelgas de hambre como protesta, fueron condenados. Años después, el testigo que había sido clave para la detención de ambos heladeros reconoció haberse inventado la declaración, aunque el caso no fue reabierto hasta el 2001. Fueron liberados en 2004. Nunca se encontró a los pirómanos.

Después de este grave incidente, la policía puso en jaque a los clanes mafiosos a cargo de ese negocio y la guerra de los carritos de helado se fue diluyendo. Aunque sería la liberalización del sector comercial y la apertura de centros de venta lo que la remataría. De esta forma, los ciudadanos de Glasgow pudieron comprar los productos que necesitaban fuera de estos circuitos.

Colaboración Antonio Capilla Vega


Nota del administrador: Es famoso el modelo de competencia espacial de Hotelling al cual este caso se asemeja muchísimo. Aunque no en lo sangriendto del final.

miércoles, 10 de junio de 2015

Explicando el Equilibrio de Nash

Explicando una piedra angular de la teoría de juegos: Equilibrio de John Nash
Por Kenneth Chang - New York Times


John F. Nash Jr., en una ceremonia la semana pasada en Oslo, Noruega, donde fue galardonado con el Premio Abel. Crédito Berit Roald / NTB SCANPIX

John F. Nash Jr. fue más conocido por los avances en la teoría de juegos, que es esencialmente el estudio de la forma de llegar a una estrategia ganadora en el juego de la vida - especialmente cuando usted no sabe lo que están haciendo sus competidores y las opciones que hacer no siempre se ven prometedores.

Dr. Nash no inventó la teoría de juegos; el matemático John von Neumann hizo el trabajo pionero para establecer el campo en la primera mitad del siglo 20. Pero el Dr. Nash extendió el análisis más allá de suma cero, I-ganar-que-perder tipos de juegos en el que todos los jugadores pueden ganar situaciones más complejas, o la totalidad podía perder.

El concepto central es el equilibrio de Nash, más o menos definida como un estado estable en el que ningún jugador puede obtener una ventaja a través de un cambio unilateral de la estrategia de asumir las demás no cambian lo que están haciendo.

La película "Una mente maravillosa", basada en la vida del Dr. Nash, trata de explicar la teoría de juegos en una escena en la que Russell Crowe, jugando Dr. Nash, es en un bar con tres amigos, y todos ellos están embelesado por una bella rubia mujer que camina con cuatro amigos morena.

Una hermosa rubia entra en un bar. ¿Qué deben hacer cuatro tipos? Una Mente Maravillosa
Mientras sus amigos bromas acerca de cuál de ellos sería cortejar con éxito la rubia, el Dr. Nash concluye que deben hacer lo contrario: Ignorar ella. "Si todos vamos por la rubia," dice, "bloqueamos entre sí y ni uno solo de nosotros va a buscarla. Así que vamos a por sus amigos, pero a todos nos dan la espalda porque a nadie le gusta ser la segunda opción. Pero ¿y si nadie va a la rubia? Nosotros no ponemos en el camino del otro y no insultamos a las otras chicas. Esa es la única manera en que ganamos ".

Si bien esto nunca sucedió en la vida real-episodio ilustra algunas de las maquinaciones que los teóricos consideran juego, no es un ejemplo de un equilibrio de Nash.

Un ejemplo más sencillo es lo que se conoce como el dilema del prisionero. Dos conspiradores en un crimen son detenidos y ofreció un trato: "Si confiesas y testifica en contra de su cómplice, se lo haremos fuera y tirar el libro en el otro tipo - 10 años de prisión."

Si ambos permanecen tranquilo, los fiscales no pueden probar los cargos más graves y ambos pasarían sólo un año tras las rejas por delitos menores. Si ambos confiesan, los fiscales no necesitarían su testimonio, y ambos recibirían penas de prisión de ocho años.

A primera vista, guardar silencio puede parecer la mejor estrategia. Si ambos lo hicieron, ambos se baje bastante ligera.

Pero el cálculo del equilibrio de Nash muestra que probablemente haría ambos confiesan.

Este tipo de problema se llama un juego no cooperativo, lo que significa que los dos presos no pueden transmitir intenciones entre sí. Sin saber lo que el otro prisionero está haciendo, cada uno se enfrenta a esta elección: si confiesa, él podría terminar con la libertad u ocho años de prisión. Si se queda tranquilo, él va a la cárcel por un año o 10 años.

En esa luz, confesión es la mejor opción. Y él sabe que el otro prisionero tiene el mismo incentivo para confesar, por lo que es menos probable que se quedaría tranquilo.

Además, el cambio de estrategia para la mamá de permanencia sería un mal movimiento - pena de prisión más larga - a menos que el otro preso de alguna manera también decidió hacer eso. Sin ningún tipo de comunicación, eso sería una suposición muy arriesgada, y por lo tanto, esta estrategia representa un equilibrio de Nash.

La escena de la barra, sin embargo, no lo hace. Con cuatro hombres persiguiendo cuatro morenas, ninguno de los hombres podría tener la tentación de perseguir a la rubia en su lugar, un resultado más deseable si sus amigos no también cambian estrategia.

lunes, 25 de mayo de 2015

Muere Nash y perdemos todos



Nash muere, todos perdemos: ¿Qué es la Teoría de juegos?

Una explicación sencilla de la idea que hizo famoso al Nobel de Economía


JOSÉ ÁNGEL MURCIA El País


Es una pena que a Nash se le esté recordando como el “protagonista” de una película y no como el genio detrás del desarrollo de la Teoría de juegos. A John Forbes Nash le gustaban los juegos, de hecho se le tiene como uno de los dos inventores independientes del juego de mesa que hoy se llama Hex, pero que en Princeton era conocido como “Nash”. Nash buscaba el juego perfecto para los matemáticos. Pero no, cuando los matemáticos hablamos de Teoría de juegos no nos referimos al Hex, ni al Candy Crush, ni a la brisca, estamos hablando fundamentalmente del estudio de las decisiones de los individuos, no de pasarnos vidas.

En Teoría de juegos se analizan situaciones complejas en las que hay más de un individuo que quiere tener éxito pero que tiene que tener en cuenta las decisiones del resto de los intervinientes. Esto es, no vale con preguntarte qué es lo que tienes que hacer tú, sino que tienes que preguntarte qué es lo que tienes que hacer tú teniendo en cuenta lo que piensas que van a hacer los demás. Veamos un ejemplo: te han detenido junto a un compinche, habéis hecho cosas terribles que no voy a contar aquí, pero la policía no tiene pruebas y solo os acusan de algo menor (sí, voy a contar el dilema del prisionero, los que lo conozcan pueden saltarse este párrafo). Pongamos que si no os delatáis el uno al otro vais a pasar tres años de chabolo. Si los dos cantáis (y os delatáis el uno al otro) os caerán 5 años a cada uno. Si canta uno solo, le caerán 12 años al otro y uno al cantor por “colaborar”... Os colocan en habitaciones separadas, claro, esto se pone interesante. Eres una persona inteligente, tu compañero es como tú -no te asocias con cualquiera- ¿qué crees que pasará?

No delatarDelatar
Tu compincheNo delatar3 años para cada uno12 para él, uno para ti
Delatar12 para ti y uno para él5 para cada uno
Llegados a este punto surgen las preguntas, ¿eres egoísta? ¿lo es tu compañero? Para poder proseguir tenemos que suponer algo al respecto, pongamos que los dos lo sois, sois completamente egoístas. Lo mejor sería que no os delataseis ¿no? Pues no, ¿no hemos dicho que sois los dos egoístas? Lo mejor para ti es que el otro no te delate y tú sí a él. Tu sabes que él piensa lo mismo, no querrás ser tú el que se pase 12 años a la sombra mientras él sale en un año ¿no?

La teoría existente antes de las aportaciones de Nash nos haría esperar el Óptimo de Pareto, esto es, ambos os calláis. Las teorías de Pareto nos llevarían a pensar que la mejor solución es que los dos cooperéis. Lo que aportó la “mente maravillosa” de Nash es que tú -conociendo al igual que tu tu socio las ideas de Nash- pienses “si creo que mi compinche no me va a delatar, lo mejor es delatarle, y si creo que me va a delatar, también es mejor para mi delatarle”. Lo que desde entonces se llama alcanzar un equilibrio de Nash: hay una estrategia dominante, debemos esperar que los dos cantéis, que los dos os delatéis, porque es lo único que podéis hacer que garantiza que estáis mejorando vuestras opciones.

Este dilema del prisionero es un ejemplo de juego en el que ambos jugadores pierden, esto es uno de los juegos de suma no nula. Otros matemáticos, como John Von Neumann (sí, el del proyecto Manhattan), ya habían estudiado el equilibrio en los juegos de suma cero (en el que los otros jugadores ganan lo que un jugador pierde). Pero Nash en su tesis doctoral de 1951 describió las situaciones en juegos en los que todos pueden perder. ¿Por qué es tan importante el equilibrio de Nash? Pues porque esta situación en la que hay mutua desconfianza es una situación muy corriente en economía, por eso se firman contratos que comprometen a las partes que suelen ser -como tú y tu compinche- bastante egoístas. Las implicaciones que tuvo el trabajo de Nash le valieron el premio Nobel de Economía en 1994. Sí, de Economía, porque de matemáticas no hay, seguramente porque al inventor de la dinamita no le gustaban las matemáticas.

La teoría de juegos proporciona modelos para entender este tipo de situaciones que se presentan -además de en famosos dilemas- en gestión, economía, psicología… o en partidas de póker, y que involucran por tanto las decisiones de todos los agentes y no solo las de uno. Para poder explicar estas situaciones se utilizan matrices o árboles de decisión.

Pero hoy no es un día de suma cero, hoy todos perdemos.

viernes, 27 de marzo de 2015

Nash gana el Nobel y el Abel

El inspirador de ‘Una mente maravillosa’ gana un ‘Nobel’ de matemáticas
John Nash y Louis Nirenberg reciben el Premio Abel de matemáticas por su su trabajo en ecuaciones diferenciales parciales, una herramienta empleada en muchas ciencias
El niño prodigio de las matemáticas cumple 65 años y no se jubila
DANIEL MEDIAVILLA -  El País



El matemático estadounidense John Nash / EFE

El matemático estadounidense John Nash, de 86 años, al que dio vida Russell Crowe en la película Una mente maravillosa, ha ganado el Premio Abel, junto a la Medalla Fields, el más prestigioso en el campo de las matemáticas. El investigador de la Universidad de Princeton compartirá los 800.000 dólares de premio que ofrece la Academia Noruega de las Ciencias y las Letras con su colega Louis Nirenberg, de 90 años, profesor emérito en la Universidad de Nueva York. Ambos han sido reconocidos por su trabajo en ecuaciones diferenciales parciales, una herramienta empleada para describir todo tipo de fenómenos científicos, desde los campos de la termodinámica a la física cuántica.

Según explica el comité del Premio Abel en un comunicado, los trabajos de Nash en este campo son considerados por los expertos más profundos y de mayor alcance que sus descubrimientos sobre teoría de juegos y las matemáticas detrás de la toma de decisiones por el que recibió el Nobel de Economía en 1994.

El nombre de Nash, que solía trabajar en solitario, está vinculado a un gran número de trabajos influyentes en el campo de las matemáticas, desde el teorema de función inversa Nash-Moser, o el teorema Nash-De Giorgi, surgido de un problema que Nash trató de resolver por sugerencia de Niremberg.


El matemático de origen canadiense Louis Nirenberg / EFE

Nirenberg, nacido en Canadá, ha gozado de una larga carrera, produciendo resultados importantes hasta después de cumplir los 70. A diferencia de Nash, Nirenberg prefería el trabajo en equipo y solía hablar de las matemáticas como una gran familia. En una entrevista de 2002, aseguraba que cuando habla con personas sin ningún contacto con las matemáticas trataba de comunicarles “lo divertidas que son”.

sábado, 24 de agosto de 2013

La evolución premia a los solidarios

Be nice. Evolution will punish you if you’re not, says study
Selfish people have short-term advantage, but co-operation and communication win out in the long term
JAMES VINCENT

New research has challenged the notion that evolution favours self-interest above co-operation, suggesting instead that selfish individuals eventually ‘compete each other out of existence’.


The study, published in the journal Nature, used models of evolutionary game theory (EGT) to show how co-operative populations are more successful than selfish ones in the long run.

Researchers used computers to play through vast numbers of “games” simulating scenarios of co-operation and betrayal. By tweaking the strategies of the virtual players they were then able to compare which behaviours resulted in survival.

The study pitched players following so-called “zero determinant” strategies (those who acted selfishly) against others taking more benevolent approaches. While the selfish strategists enjoyed a brief advantage, opponents eventually came to recognise and overcome selfish individuals.

“Communication is critical for cooperation – we think communication is the reason co-operation occurs,” said Christoph Adami, a professor at Michigan State University and the lead author of the paper. “In an evolutionary setting, with populations of strategies, you need extra information to distinguish each other.

“We found evolution will punish you if you’re selfish and mean. For a short time and against a specific set of opponents, some selfish organisms may come out ahead. But selfishness isn’t evolutionarily sustainable.”

Much of what we understand about the working of selfish and selfless behaviour in society comes from game theory, a branch of mathematics concerned with decision making. It was developed throughout the middle of the 20th century but came to prominence first through the works of John Nash and then as a guiding political ideology during the cold war.

One of game theory’s most infamous studies is the “prisoner’s dilemma”, a hypothetical scenario where two prisoners are offered their freedom if they inform on the other. Under Nash’s explanation it seemed to show that individuals should pursue their own interests because they cannot predict how others will act.

The problem with such examples is that they are abstract and theoretical – they don’t take into account the many nuances of real-world scenarios where individuals have the opportunity to gauge how trustworthy others are, discuss their options, and also evaluate other people’s past behaviour.

Despite the apparent humane message of the findings of the new research, they do not contradict the concept of the “selfish gene” – the theory that living organisms exist only to propagate their genetic material.

Instead, the findings may complement it, as co-operative behaviour benefits whole species and thus the existence of a wider gene pool. Co-operation within a group does not preclude selfishness outside of it.

The Independent

lunes, 12 de agosto de 2013

Evitando la paradoja de Braess desinvirtiendo en rutas

Removing Roads and Traffic Lights Speeds Urban Travel
Urban travel is slow and inefficient, in part because drivers act in self-interested ways


By Linda Baker

Conventional traffic engineering assumes that given no increase in vehicles, more roads mean less congestion. So when planners in Seoul tore down a six-lane highway a few years ago and replaced it with a five-mile-long park, many transportation professionals were surprised to learn that the city’s traffic flow had actually improved, instead of worsening. “People were freaking out,” recalls Anna Nagurney, a researcher at the University of Massachusetts Amherst, who studies computer and transportation networks. “It was like an inverse of Braess’s paradox.”
The brainchild of mathematician Dietrich Braess of Ruhr University Bochum in Germany, the eponymous paradox unfolds as an abstraction: it states that in a network in which all the moving entities rationally seek the most efficient route, adding extra capacity can actually reduce the network’s overall efficiency. The Seoul project inverts this dynamic: closing a highway—that is, reducing network capacity—improves the system’s effectiveness.
Although Braess’s paradox was first identified in the 1960s and is rooted in 1920s economic theory, the concept never gained traction in the automobile-oriented U.S. But in the 21st century, economic and environmental problems are bringing new scrutiny to the idea that limiting spaces for cars may move more people more efficiently. A key to this counterintuitive approach to traffic design lies in manipulating the inherent self-interest of all drivers.
A case in point is “The Price of Anarchy in Transportation Networks,” published last September in Physical Review Letters by Michael Gastner, a computer scientist at the Santa Fe Institute, and his colleagues. Using hypothetical and real-world road networks, they explain that drivers seeking the shortest route to a given destination eventually reach what is known as the Nash equilibrium, in which no single driver can do any better by changing his or her strategy unilaterally. The problem is that the Nash equilibrium is less efficient than the equilibrium reached when drivers act unselfishly—that is, when they coordinate their movements to benefit the entire group.
The “price of anarchy” is a measure of the inefficiency caused by selfish drivers. Analyzing a commute from Harvard Square to Boston Common, the researchers found that the price can be high—selfish drivers typically waste 30 percent more time than they would under “socially optimal” conditions.
The solution hinges on Braess’s paradox, Gastner says. “Because selfish drivers optimize a wrong function, they can be led to a better solution if you remove some of the network links,” he explains. Why? In part because closing roads makes it more difficult for individual drivers to choose the best (and most selfish) route. In the Boston example, Gastner’s team found that six possible road closures, including parts of Charles and Main streets, would reduce the delay under the selfish-driving scenario. (The street closures would not slow drivers if they were behaving unselfishly.)
Another kind of anarchy could actually speed travel as well—namely, a counterintuitive traffic design strategy known as shared streets. The practice encourages driver anarchy by removing traffic lights, street markings, and boundaries between the street and sidewalk. Studies conducted in northern Europe, where shared streets are common, point to improved safety and traffic flow.
The idea is that the absence of traffic regulation forces drivers to take more responsibility for their actions. “The more uncomfortable the driver feels, the more he is forced to make eye contact on the street with pedestrians, other drivers and to intuitively go slower,” explains Chris Conway, a city engineer with Montgomery, Ala. Last April the city converted a signalized downtown intersection into a European-style cobblestone plaza shared by cars, bikes and pedestrians—one of a handful of such projects that are springing up around the country.
Although encouraging vehicular chaos seems at odds with the ideas presented in the price of anarchy study, both strategies downplay the role of the individual driver in favor of improved outcomes for everyone. They also suggest a larger transportationniche for bicycles and pedestrians. As the Obama administration prepares to invest in the biggest public works project since the construction of the interstate highway system, the notion that fewer, more inclusive roads yield better results is especially timely.
Faster Streets with Less Parking
New strategies in parking management could also improve urban traffic flow, remarks Patrick Siegman, a principal with Nelson/Nygaard Consulting Associates in San Francisco, a transportation-planning firm. In a misguided effort to reduce congestion, planners in the 1950s required developers to provide a minimum number of free parking spaces—a strategy that “completely ignored” basic economics, Siegman says, referring to how lower prices
increase demand.
Now limited urban space and concerns about global warming are inspiring city planners to eliminate these requirements. In San Francisco, for example, developers must restrict parking to a maximum of 7 percent of a building’s square footage, a negligible amount. Although downtown employment has increased, traffic congestion is actually declining, Seigard says. With fewer free spaces to park, drivers seem to be switching modes, relying more on mass transit, cycling and just plain walking.
Note: This article was originally printed with the title, "Detours by Design".