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:

  • Elias Koutsoupias and Christos H. Papadimitriou, Worst-case Equilibira (2009).



  • Tim Roughgarden and Eva Tardos, How Bad Is Selfish Routing? (2002)



  • Noam Nisan and Amir Ronen, Algorithmic Mechanism Design (2001).



  • 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.)

    2 comentarios:

    Pedro Terán dijo...

    En principio los PDF sin permisos para imprimir se abren con el Ghostview y... ¡hop, milagro!

    JuanPablo dijo...

    shh, a ver si lo sacan ;)