Paradoja de Braess
La paradoja puede tener analogías en las redes eléctricas y los sistemas biológicos.
Su idea era que si cada conductor tomaba la ruta óptima que le resultaba más rápida considerando sus intereses individuales, y sin conocer el comportamiento del resto de conductores, esto sobrecargaba las rutas percibidas como más rápidas.
En estas condiciones, se desea estimar la distribución del flujo de tráfico.
Si cada conductor toma el camino que le resulta aparentemente más favorable, los tiempos de marcha resultantes no necesariamente serán mínimos.
Además, se indica con un ejemplo que una extensión de la red de carreteras puede causar una redistribución del tráfico que resulte en tiempos de viaje individuales más largos.Añadir capacidad extra a una red cuando las entidades en movimiento eligen su ruta de forma egoísta puede en algunos casos reducir el rendimiento general.
Cuando el sistema no está en equilibrio de Nash, los conductores individuales pueden mejorar sus respectivos tiempos de viaje cambiando las rutas que toman.
Aquellas vías que tienen mayor capacidad (por ejemplo, más carriles para tráfico) podrán albergar más vehículos sin que la velocidad se vea afectada, mientras que vías con poca capacidad se congestionan más rápido.
El siguiente principio tiene que ver con que los usuarios de las vías tienden a escoger la ruta que más les conviene individualmente (por eso se les llama usuarios “egoístas”) y esto implica que cada usuario tratará de buscar la ruta que le represente menores tiempos de viaje (ver primer principio de Wardrop).
Braess demostró con un ejemplo simple, cómo al agregar más vías en una red de tráfico, se puede llegar a empeorar el desempeño de todos los usuarios.
La red clásica para mostrar esta paradoja se presenta en la figura 1.
Los árcos rojos representan autopistas de gran capacidad, mientras que los arcos amarillos representan vías de baja capacidad.
Al añadir una vía entre los puntos X e Y, los tiempos de todos los usuarios empeoran sustancialmente (figura 2).
Suponga que se tiene una red como la de la figura 3.
Antes de la construcción de la nueva vía (línea punteada) existen solamente dos posibles rutas entre los puntos START y END.
Sustituyendo la restricción en una de las dos ecuaciones e igualando con la sobrante, se obtiene que
Con esta solución, los usuarios por cualquiera de las dos vías se tardarán
Ahora suponga que se construye una vía que permite conectar A y B en un tiempo muy corto (un par de minutos).
Los viajeros que quieren llegar a B desde el punto de inicio, preferirán tomar la ruta pasando por A y usando el nuevo tramo AB ya que
Al final, todos los usuarios tomarán la misma ruta y el tiempo total de viaje será:
Sin embargo ramas de las matemáticas como la teoría de grafos y la probabilidad ofrecen una respuesta a la pregunta; pues se puede evidenciar que en una red aleatoria dotada de ciertas funciones que modelen su tránsito, el mismo fenómeno se presenta al eliminar algunas vías.
Para ello se va a considerar una red posible de tránsito modelada a través de un grafo aleatorio, hecho esto se puede evidenciar que en general las condiciones de la red permiten que al eliminar vías la movilidad sea más eficiente.
Los grafos en sí mismos constituyen una manera muy conveniente de modelar y representar redes (no solo de tránsito), de ahí que sea natural usarlos para ver si es posible encontrar ejemplos más generales y cercanos a la realidad donde se presente este comportamiento paradójico.
y el flujo se dice factible si
Modelamos la "congestión" de la red asignándole a cada arista
se dice que este es un Nash-flujo o simplemente un equilibrio de Nash si para toda
[5] O, en otras palabras todos los caminos tienden a tener la misma "demora", lo cual se puede evidenciar claramente en el ejemplo, pues pasado el tiempo los usuarios tenderán a escoger el camino que les permita llegar a todos lo más rápido posible, y por ende el tiempo que demoran todos en llegar desde el punto de salida al de llegada es el mismo.
[6] Al considerar el modelo anterior sobre un grafo aleatorio (en general un grafo grande), asumiendo que el flujo es un equilibrio de Nash y definiendo la distancia entre dos vértices como el menor número de aristas que los conectan, se puede probar que todos los "vértices internos" guardan relativamente la misma distancia con
), intuitivamente se puede ver esto entendiendo que hay un número cuadrático de aristas internas, mientras que solo hay un número linear de las aristas incidentes en los extremos
, entonces podemos ver la red esencialmente como dos conjuntos de vías que van desde el punto de salida "un punto intermedio artificial" (notado en la figura 4 como
Ordenando los caminos como en la figura 5 hemos dotado al grafo de una estructura similar a la del ejemplo inicial de la paradoja, y retirando las aristas de conexión el subgrafo resultante en general tiene un flujo más eficiente que el original.
