1.- El regreso de Mairena
-"Como decíamos ayer..." -dijo Mairena cuando retomó su cátedra, tras casi sesenta años de ausencia.
Pero uno de los alumnos levantó la mano, interrumpiéndolo:
-Profesor, ¿no se habrá equivocado de aula? Ayer no tuvimos clases con usted.
Mairena se frotó las manos con una sonrisa. Tenían mucho que aprender estos imbéciles.
-Voy a asumir que saben leer. Por lo menos la mayoría.
28.5.12
1638.- Diez añitos
Diez años con el blog, ni yo lo puedo creer...
26.5.12
1637.- Teoria algoritmica de juegos (3)
(viene de aquí)
Self-fish routing
En el segundo ejemplo cambia la situación. Acá uno o más jugadores tratan de rutear un cierto volumen de datos/líquidos por una red y el costo será proporcional al tiempo que se tarda en recorrerla. Incluso con un solo jugador que dirige el tráfico hay problemas...
* * *
Segundo Ejemplo
El ejemplo lo propuso Pigou, en 1920:
La ruta A tarda 1 independiente del tráfico, mientras que la ruta B se congestiona cuando el tráfico se incrementa. Acá, el tráfico se puede considerar formado por
unidades muy pequeñas, que pueden ir por una ruta u otra (paquetes de información, gotas de agua).
Supongamos que tenemos que mandar 1 GB, y en B el costo es 1 segundo, c(1 GB)=1'. Entonces el equilibrio de Nash es mandar 1 GB por B, y nada por A. ¿Por qué? Porque si dividimos el giga de datos en paquetes, y mandamos p paquetes por A, y el resto por B, cualquiera de los paquetes que va por A tarda 1, y si se cambia a B llega antes (porque el total de datos en B con ese paquete extra sigue siendo menor a 1 GB, y tardarán menos de 1). En definitiva, el único equilibrio de Nash es mandar todo por B.
Ajá... ya tenemos el juego, las reglas, los costos, el equilibrio de Nash... ¿qué nos podría interesar optimizar? Bueno, una posibilidad es mejorar el tiempo promedio que tardan los paquetes en cruzar.
Si metemos 1 GB por B, llegan todos 1 segundo más tarde. Si lo metemos por A, también... pero si metemos mitad y mitad, la mitad que va por A tarda 1 seg, y la otra
solo medio segundo.
El tiempo promedio que tarda un paquete es 1.(1/2) + (1/2).(1/2) = 3/4, mejor que el tiempo del Nash que era 1.
El precio de la anarquía es igual al precio de la estabilidad, y es 1/(3/4)=4/3.
* * *
El peor de los mundos
Un gran resultado de Roughgarden y Tardos es que en toda red, sin importar su longitud, ni su complejidad, el precio es 4/3 si los costos de cada link son lineales en el tráfico.
Es decir, si cuando hay un flujo x por un link el costo es ax+b, con a y b fijos, entonces el precio de la anarquía es menor 4/3, y esto es independiente de la
topología de la red.
El ejemplo de Pigou, de 1920, resultó ser el peor de los mundos posibles.
* * *
El mejor de los mundos
¿Y si los costos no fueran lineales? ¿Cuadráticos, cúbicos, polinomiales, racionales...?
Bueno, Roughgarden atacó ese problema aquí (free). Por ejemplo, para polinomios de grado p, la clave es modificar el ejemplo de Pigou, y poner un costo a la ruta B de xp. Una cuenta astuta, pero elemental, prueba que el precio es del orden de p/log(p). Tambien las cosas son independientes de la topología de la red, y del polinomio exacto involucrado.
Comparado, el ejemplo de Pigou es el mejor de los mundos posibles.
* * *
Qué falta?
Mucho, que reservo para la clase del jueves, e iré incluyendo según el ánimo/interés de aquí en más:
Una aplicación del ejemplo de Pigou de por qué podría interesarnos minimizar el tiempo promedio.
El ejemplo que da el peor precio de la estabilidad en problemas como el del primer ejemplo, donde cada jugador elige una ruta y comparten los costos quienes usan la misma. Es del orden del logaritmo de k, donde k es el número de jugadores.
La definición de juegos potenciales, o de congestión, que inluyen las dos grandes familias de juegos consideradas: jugadores eligiendo caminos en una red (atomic games), o envío de datos por una red (nonatomic games), donde se comparten los costos al usar un mismo camino, pero encareciéndolo por congestionarla.
Shapley... pobre Shapley!
Varios teoremas lindos: cotas para los precios de la estabilidad y de la anarquía en estos juegos, existencia de equilibrios de Nash puros,...
El precio de la Malicia: hay jugadores bizantinos cuyo único objetivo es cagarle la vida al resto... (ejmplos)
Otros ejemplos.
Más ejemplos.
La paradoja de Braess.
Problemas abiertos.
Diseño de mecanismos: ¿cómo reducir el precio de la anarquía/estabilidad?
* * *
Gran laburo el de esta gente, felicitaciones!
again, for the Carnival, now at Gaussianos
Self-fish routing
En el segundo ejemplo cambia la situación. Acá uno o más jugadores tratan de rutear un cierto volumen de datos/líquidos por una red y el costo será proporcional al tiempo que se tarda en recorrerla. Incluso con un solo jugador que dirige el tráfico hay problemas...
Segundo Ejemplo
El ejemplo lo propuso Pigou, en 1920:
La ruta A tarda 1 independiente del tráfico, mientras que la ruta B se congestiona cuando el tráfico se incrementa. Acá, el tráfico se puede considerar formado por
unidades muy pequeñas, que pueden ir por una ruta u otra (paquetes de información, gotas de agua).
Supongamos que tenemos que mandar 1 GB, y en B el costo es 1 segundo, c(1 GB)=1'. Entonces el equilibrio de Nash es mandar 1 GB por B, y nada por A. ¿Por qué? Porque si dividimos el giga de datos en paquetes, y mandamos p paquetes por A, y el resto por B, cualquiera de los paquetes que va por A tarda 1, y si se cambia a B llega antes (porque el total de datos en B con ese paquete extra sigue siendo menor a 1 GB, y tardarán menos de 1). En definitiva, el único equilibrio de Nash es mandar todo por B.
Ajá... ya tenemos el juego, las reglas, los costos, el equilibrio de Nash... ¿qué nos podría interesar optimizar? Bueno, una posibilidad es mejorar el tiempo promedio que tardan los paquetes en cruzar.
Si metemos 1 GB por B, llegan todos 1 segundo más tarde. Si lo metemos por A, también... pero si metemos mitad y mitad, la mitad que va por A tarda 1 seg, y la otra
solo medio segundo.
El tiempo promedio que tarda un paquete es 1.(1/2) + (1/2).(1/2) = 3/4, mejor que el tiempo del Nash que era 1.
El precio de la anarquía es igual al precio de la estabilidad, y es 1/(3/4)=4/3.
El peor de los mundos
Un gran resultado de Roughgarden y Tardos es que en toda red, sin importar su longitud, ni su complejidad, el precio es 4/3 si los costos de cada link son lineales en el tráfico.
Es decir, si cuando hay un flujo x por un link el costo es ax+b, con a y b fijos, entonces el precio de la anarquía es menor 4/3, y esto es independiente de la
topología de la red.
El ejemplo de Pigou, de 1920, resultó ser el peor de los mundos posibles.
El mejor de los mundos
¿Y si los costos no fueran lineales? ¿Cuadráticos, cúbicos, polinomiales, racionales...?
Bueno, Roughgarden atacó ese problema aquí (free). Por ejemplo, para polinomios de grado p, la clave es modificar el ejemplo de Pigou, y poner un costo a la ruta B de xp. Una cuenta astuta, pero elemental, prueba que el precio es del orden de p/log(p). Tambien las cosas son independientes de la topología de la red, y del polinomio exacto involucrado.
Comparado, el ejemplo de Pigou es el mejor de los mundos posibles.
Qué falta?
Mucho, que reservo para la clase del jueves, e iré incluyendo según el ánimo/interés de aquí en más:
Gran laburo el de esta gente, felicitaciones!
again, for the Carnival, now at Gaussianos
25.5.12
1636.- Teoría algorítmica de juegos (2)
(viene de Teoría algorítmica de juegos 1)
Ineficiencia
Consideren un juego, sus reglas, y los pagos y costos por participar. El problema principal que esta gente quiso resolver es el de analizar la ineficiencia asociada con la libertad que tienen los jugadores para elegir qué hacer. Claramente, si no hay restricciones, cada jugador actúa por su propio interés, pero el resultado al que se llega puede ser malo desde el punto de vista social o colectivo.
En Una mente brillante se dice que Nash refutó a Adam Smith, mostrando cómo todos podían beneficiarse, etcétera. Ni ahí. Hay equilibrios de Nash donde la mano invisible que elige las estrategias producen resultados desastrosos (de los cuales nadie quiere salir, porque empeora su situación), y hay ejemplos que lo muestran claramente.
* * *
Primer Ejemplo
El primer ejemplo NO es el dilema del prisionero. Ahí no hay opción: el juego tiene un solo equilibrio, así que no tienen chances de hacer nada. En cualquier situación, confesar es mejor que quedarse callado, y si bien se llega a un resultado no deseado, es clarísimo que no hay alternativas.
El primer ejemplo es una red con dos caminos A y B para ir de s a t. Pero A cuesta K y B cuesta 1+E, con E muy pequeño. Tenemos también K jugadores, que deben elegir ruta, y compartirán el costo de una ruta aquellos jugadores que la elijan.
Observemos que si todos van por el camino B, cada uno paga (1+E)/K, muy poco, y a nadie le conviene desviarse porque pagaría K, muchísimo.
Pero resulta que hay otro equilibrio de Nash, muy ineficiente, y es que todos elijan la ruta A: cada uno paga 1, y si un jugador se desvía, pagaría 1+E. Resultado: se quedan todos en la ruta A, pagando en total K.
Bienvenidos a la ineficiencia de la mano invisible de Nash.
* * *
Antes de otro ejemplo, veamos que buscaron resolver los seis ganadores del Godel de este año. Para analizar la ineficiencia de un juego hay que contestar las siguientes preguntas:
1.- ¿Cuáles son los pagos?
El problema se simplifica si hay un valor monetario (se paga o cobra cierta cantidad según qué hacen todos), pero también se puede considerar el tiempo que lleva una tarea (si bien time = money, hay situaciones donde el presupuesto no importa con tal de minimizar el tiempo).
2.- ¿Cómo comparar los distintos resultados del juego?
Si bien 1.- sugiere minimizar costos ó tiempos, o maximizar ganancias, hay que distinguir entre dos enfoques:
-Utilitario: buscamos minimizar el costo (o tiempo) general, tal vez a costa de matar a algún jugador, que corre con todo el costo.
-Igualitario: se quiere reducir el costo máximo de los jugadores.
Según el contexto, habrá que ver cuál conviene, definir la función correspondiente, y se busca el valor óptimo.
3.- ¿Qué quiere decir 'casi óptimo'?
La solución que eligieron es dividir el valor óptimo y el valor de la función en un equlibrio. Si esa razón está cerca de uno, podemos pensar que el equilibrio es casi óptimo. Y es fácil comparar, diciendo que es un tanto por ciento peor, o que cuesta el triple, etc. Además, como dicen en el libro: casi todos usan ese parámetro...
En la elección de cómo comparar, se llegó a un equilibrio ¿será cercano a un óptimo? :-)
4.- ¿Qué equilibrios se considerarán?
Acá no hay mucha vuelta: son los equlibrios de Nash, preferentemente los equilibrios en estrategias puras, y se mira cuánto valen para la función del punto 2.-
5.- ¿Qué pasa si hay más de un equilibrio?
Ahí vienen las dos definiciones importantes:
Precio de la Anarquía: es la razón (definida en 3.-) entre el peor valor de la función evaluada en los equilibrios (4.-) y el valor óptimo (2.-).
Precio de la Estabilidad: es la razón (definida en 3.-) entre el mejor valor de la función evaluada en los equilibrios (4.-) y el valor óptimo (2.-).
En el ejemplo de la red de dos caminos, el óptimo (utilitario e igualitario) es que todos vayan por B, que era un equilibrio de Nash. Como ese equilibrio coincide con el óptimo, el precio de la estabilidad es 1. Pero hay un equilibrio cuyo costo es K, con lo cual el precio de la anarquía es
(valor del equilibrio)/óptimo = K / (1+E) ~ K.
* * *
Precio de la estabilidad
Recordemos que en un equilibrio de Nash nadie tiene motivos para desviarse, lo cual estabiliza una situación: si todos estamos haciendo algo, y nadie gana más por desviarse unilateralmente, entonces seguiremos haciendo todos lo mismo.
En cualquier elección de estrategias que no sea un Nash, habrá un jugador que tiene incentivos por desviarse, con lo cual es difícil lograr que todos se coordinen en una situación (por ejemplo, la que da el valor óptimo) si esta no es un Nash. El precio de la estabilidad es lo mínimo que tenemos que sacrificar para tener un Nash.
* * *
Precio de la anarquía
El precio de la anarquía, en cambio, es el peor caso que puede darse. Nos alejamos del óptimo, y nadie tiene incentivos para cambiarse. Cuando hay un único equilibrio, mala suerte, coincide con el precio de la estabilidad y no hay mucho más para decir.
El problema más grave es cuando hay varios equilibrios y justo ese es fácil de descubrir, o es el que se implementa fácil o rápido por razones dinámicas. Veamos el ejemplo inicial con otra óptica.
Vivir en el centro de Buenos Aires es una locura, y si bien muchísima gente trabaja en el centro, prefiere vivir en Pilar, o Tigre, zonas alejadas desde las que sólo se llega en auto. Si K personas viven en Pilar, salen a las 8hs y vuelven a las 18hs, cada una pagando el costo de un auto, unas 8-10 podrían pagar mucho menos y mantener una combi que los lleve/traigo más o menos en el mismo tiempo. El tema es que cuando un country comienza a formarse, como los habitantes son pocos, la única solución es que cada uno resuelva su problema de transporte con su propio auto.
La formación de una villa sigue una dinámica similar: cada familia ocupa parcelas de un terreno, hasta cubrir por completo el área disponible. Abrir luego caminos internos (para circular con más comodidad o seguridad, llevar luz o agua, etc) termina siendo imposible, porque es necesario desplazar algunas familias, y en ocasiones ya no hay donde ubicarlas a menos que sea en otra parte.
El problema se ve también en las partes más viejas de las ciudades, donde la estructura antigua tiene calles intransitables para la modernidá, e invitan a carnicerías históricas, tales como en el centro de Buenos Aires, cuando se demolió parte del Cabildo para facilitar el tránsito. Bueno, también a Vieytes se le ocurre instalar su jabonería justo donde hoy (25 de Mayo, pero 202 años después) tenía que pasar la Avenida 9 de Julio...
* * *
Continuará.
(y esta vez, el Carnaval está en Gaussianos.)
Ineficiencia
Consideren un juego, sus reglas, y los pagos y costos por participar. El problema principal que esta gente quiso resolver es el de analizar la ineficiencia asociada con la libertad que tienen los jugadores para elegir qué hacer. Claramente, si no hay restricciones, cada jugador actúa por su propio interés, pero el resultado al que se llega puede ser malo desde el punto de vista social o colectivo.
En Una mente brillante se dice que Nash refutó a Adam Smith, mostrando cómo todos podían beneficiarse, etcétera. Ni ahí. Hay equilibrios de Nash donde la mano invisible que elige las estrategias producen resultados desastrosos (de los cuales nadie quiere salir, porque empeora su situación), y hay ejemplos que lo muestran claramente.
Primer Ejemplo
El primer ejemplo NO es el dilema del prisionero. Ahí no hay opción: el juego tiene un solo equilibrio, así que no tienen chances de hacer nada. En cualquier situación, confesar es mejor que quedarse callado, y si bien se llega a un resultado no deseado, es clarísimo que no hay alternativas.
El primer ejemplo es una red con dos caminos A y B para ir de s a t. Pero A cuesta K y B cuesta 1+E, con E muy pequeño. Tenemos también K jugadores, que deben elegir ruta, y compartirán el costo de una ruta aquellos jugadores que la elijan.
Observemos que si todos van por el camino B, cada uno paga (1+E)/K, muy poco, y a nadie le conviene desviarse porque pagaría K, muchísimo.
Pero resulta que hay otro equilibrio de Nash, muy ineficiente, y es que todos elijan la ruta A: cada uno paga 1, y si un jugador se desvía, pagaría 1+E. Resultado: se quedan todos en la ruta A, pagando en total K.
Bienvenidos a la ineficiencia de la mano invisible de Nash.
Antes de otro ejemplo, veamos que buscaron resolver los seis ganadores del Godel de este año. Para analizar la ineficiencia de un juego hay que contestar las siguientes preguntas:
El problema se simplifica si hay un valor monetario (se paga o cobra cierta cantidad según qué hacen todos), pero también se puede considerar el tiempo que lleva una tarea (si bien time = money, hay situaciones donde el presupuesto no importa con tal de minimizar el tiempo).
Si bien 1.- sugiere minimizar costos ó tiempos, o maximizar ganancias, hay que distinguir entre dos enfoques:
-Utilitario: buscamos minimizar el costo (o tiempo) general, tal vez a costa de matar a algún jugador, que corre con todo el costo.
-Igualitario: se quiere reducir el costo máximo de los jugadores.
Según el contexto, habrá que ver cuál conviene, definir la función correspondiente, y se busca el valor óptimo.
La solución que eligieron es dividir el valor óptimo y el valor de la función en un equlibrio. Si esa razón está cerca de uno, podemos pensar que el equilibrio es casi óptimo. Y es fácil comparar, diciendo que es un tanto por ciento peor, o que cuesta el triple, etc. Además, como dicen en el libro: casi todos usan ese parámetro...
En la elección de cómo comparar, se llegó a un equilibrio ¿será cercano a un óptimo? :-)
Acá no hay mucha vuelta: son los equlibrios de Nash, preferentemente los equilibrios en estrategias puras, y se mira cuánto valen para la función del punto 2.-
Ahí vienen las dos definiciones importantes:
Precio de la Anarquía: es la razón (definida en 3.-) entre el peor valor de la función evaluada en los equilibrios (4.-) y el valor óptimo (2.-).
Precio de la Estabilidad: es la razón (definida en 3.-) entre el mejor valor de la función evaluada en los equilibrios (4.-) y el valor óptimo (2.-).
En el ejemplo de la red de dos caminos, el óptimo (utilitario e igualitario) es que todos vayan por B, que era un equilibrio de Nash. Como ese equilibrio coincide con el óptimo, el precio de la estabilidad es 1. Pero hay un equilibrio cuyo costo es K, con lo cual el precio de la anarquía es
Precio de la estabilidad
Recordemos que en un equilibrio de Nash nadie tiene motivos para desviarse, lo cual estabiliza una situación: si todos estamos haciendo algo, y nadie gana más por desviarse unilateralmente, entonces seguiremos haciendo todos lo mismo.
En cualquier elección de estrategias que no sea un Nash, habrá un jugador que tiene incentivos por desviarse, con lo cual es difícil lograr que todos se coordinen en una situación (por ejemplo, la que da el valor óptimo) si esta no es un Nash. El precio de la estabilidad es lo mínimo que tenemos que sacrificar para tener un Nash.
Precio de la anarquía
El precio de la anarquía, en cambio, es el peor caso que puede darse. Nos alejamos del óptimo, y nadie tiene incentivos para cambiarse. Cuando hay un único equilibrio, mala suerte, coincide con el precio de la estabilidad y no hay mucho más para decir.
El problema más grave es cuando hay varios equilibrios y justo ese es fácil de descubrir, o es el que se implementa fácil o rápido por razones dinámicas. Veamos el ejemplo inicial con otra óptica.
Vivir en el centro de Buenos Aires es una locura, y si bien muchísima gente trabaja en el centro, prefiere vivir en Pilar, o Tigre, zonas alejadas desde las que sólo se llega en auto. Si K personas viven en Pilar, salen a las 8hs y vuelven a las 18hs, cada una pagando el costo de un auto, unas 8-10 podrían pagar mucho menos y mantener una combi que los lleve/traigo más o menos en el mismo tiempo. El tema es que cuando un country comienza a formarse, como los habitantes son pocos, la única solución es que cada uno resuelva su problema de transporte con su propio auto.
La formación de una villa sigue una dinámica similar: cada familia ocupa parcelas de un terreno, hasta cubrir por completo el área disponible. Abrir luego caminos internos (para circular con más comodidad o seguridad, llevar luz o agua, etc) termina siendo imposible, porque es necesario desplazar algunas familias, y en ocasiones ya no hay donde ubicarlas a menos que sea en otra parte.
El problema se ve también en las partes más viejas de las ciudades, donde la estructura antigua tiene calles intransitables para la modernidá, e invitan a carnicerías históricas, tales como en el centro de Buenos Aires, cuando se demolió parte del Cabildo para facilitar el tránsito. Bueno, también a Vieytes se le ocurre instalar su jabonería justo donde hoy (25 de Mayo, pero 202 años después) tenía que pasar la Avenida 9 de Julio...
Continuará.
(y esta vez, el Carnaval está en Gaussianos.)
23.5.12
1635.-. Teoria algoritmica de juegos
Al paso que voy, casi no posteo en este Carnaval. Pero quiero preparar una clase para el 31/5, y su contenido me viene bien para acá. O el Carnaval me viene bien para prepararla... no se. Allá vamos.
Introducción
La semana pasada, la ACM entregó el premio Godel, destinado a avances en lógica o fundamentos de la computación, y los ganadores fueron seis personas por tres papers que escribieron en parejas:
De paso, los tres primeros escriben en el blog Turing's invisible hand (agtb.worpress.com, por algorithmic game theory blog).
Más info sobre la teoría de juegos algorítmica se puede encontrar en el libro de Vazirani, Nisan, Roughgarden, y Tardos, Algorithmic Game Theory, Cambridge University Press, 2007. Se baja
gratis un pdf (non-printable, je!) de la editorial o las páginas de los autores.
El trabajo que hicieron se aplica a problemas interesantísimos de redes (incluyendo tráfico, no solo internet o redes de comunicaciones), y pienso desarrollar lo básico en los próximos posts.
Problema relacionado: hallar una localidad y las rutas adecuadas para que se junten a festejar, si deben viajar desde Stanford, Cornell, Berkeley, Atenas, Jerusalem y Haifa con los (apenas) 5000 U$S de premio...
(y esta vez, el Carnaval está en Gaussianos.)
Suscribirse a:
Entradas (Atom)