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 x^p. 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