Rutas egoístas y el precio de la anarquía

Título original:

Selfish Routing and the Price of Anarchy

Contenido del libro:

Un análisis de la pérdida de rendimiento causada por un comportamiento egoísta y descoordinado en las redes.

La mayoría de nosotros preferimos desplazarnos por la ruta más corta disponible, sin tener en cuenta la congestión de tráfico que causamos a los demás. Muchas redes, incluidas las informáticas, sufren algún tipo de este "encaminamiento egoísta". En Selfish Routing and the Price of Anarchy, Tim Roughgarden estudia la pérdida de bienestar social causada por el comportamiento egoísta y descoordinado en las redes. Cuantifica el precio de la anarquía -la peor pérdida posible de bienestar social por enrutamiento egoísta- y también analiza varios métodos para mejorar el precio de la anarquía con control centralizado.

Roughgarden comienza con una introducción relativamente poco técnica al enrutamiento egoísta, describiendo dos ejemplos importantes que motivan los problemas que siguen. El primero, el ejemplo de Pigou, demuestra que el comportamiento egoísta no tiene por qué generar un resultado socialmente óptimo. El segundo, la paradoja contraintuitiva de Braess, muestra que las mejoras de la red pueden degradar su rendimiento. A continuación, desarrolla técnicas para cuantificar el precio de la anarquía (en las que el ejemplo de Pigou desempeña un papel central). A continuación, analiza la paradoja de Braess y la complejidad computacional de detectarla algorítmicamente, y describe el enrutamiento de Stackelberg, que mejora el precio de la anarquía utilizando un grado modesto de control central. Por último, define varios problemas abiertos que pueden inspirar nuevas investigaciones. El trabajo de Roughgarden será de interés no sólo para investigadores y estudiantes de postgrado en informática teórica y optimización, sino también para otros informáticos, así como para economistas, ingenieros eléctricos y matemáticos.