Paradoja de Braess

La paradoja de Braess es la observación de que añadir una o más carreteras a una red de carreteras puede acabar dificultando el flujo de tráfico general a través de ella. La paradoja fue postulada en 1968 por el matemático alemán Dietrich Braess, quien se dio cuenta de que añadir una carretera en un ejemplo concreto de red de tráfico vial congestionada aumentaría el tiempo total de viaje.

La paradoja puede tener analogías en las redes eléctricas y los sistemas biológicos. Se ha sugerido que, en teoría, la mejora de una red podría lograrse eliminando ciertas partes de la misma.

La paradoja fue presentada en 1968 por el matemático alemán Dietrich Braess.

También puede relacionarse con la posición de Lewis-Mogridge.

Descubrimiento y definición

Dietrich Braess, un matemático de Universidad del Ruhr, Alemania, advirtió que el flujo en una red de carreteras empeoraba tras la adición de una nueva carretera, mientras estudiaba el modelado de tráfico. 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. Más formalmente, la idea detrás del descubrimiento de Braess es que el equilibrio de Nash puede no equipararse con el mejor flujo global a través de una red.^[1]​

La paradoja se enuncia como sigue:

Para cada punto de una red de carreteras, supongamos un número fijo de coches que parten de ella y el destino de los coches. En estas condiciones, se desea estimar la distribución del flujo de tráfico. La preferencia por una calle o por otra depende no sólo de la calidad de la carretera, sino también de la densidad del flujo. 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. Esto se debe a que el equilibrio de Nash de tal sistema no es necesariamente óptimo. El cambio de red induce una nueva estructura de juego que conduce a un dilema del prisionero de múltiples jugadores. En un equilibrio de Nash, los conductores no tienen ningún incentivo para cambiar de ruta. Cuando el sistema no está en equilibrio de Nash, los conductores individuales pueden mejorar sus respectivos tiempos de viaje cambiando las rutas que toman. En el caso de la paradoja de Braess, los conductores continuarán variando sus rutas hasta que alcancen el equilibrio de Nash, a pesar de la reducción del rendimiento general.

Si las funciones de latencia son lineales, la adición de una frontera nunca puede empeorar el tiempo total de desplazamiento en equilibrio en un factor superior a 4/3. ^[2]​.

Principios teóricos

Un principio básico que es necesario entender antes de entrar en el ejemplo de la paradoja es que cuantos más automóviles usan una vía, más se reduce la velocidad de todos los vehículos que la usan y se llega a un mayor tiempo de viaje. 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). Las dos rutas son idénticas. En este caso, bajo el principio de que los conductores escogen la ruta de forma egoísta (cada usuario buscará minimizar su tiempo de viaje), al final se repartirán de tal forma que por los dos lados haya igual congestión.

La paradoja

 

Figura 1. Red antes de la modificación.

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). Esto constituye una paradoja en la medida en que se espera que al realizar una inversión en vías, los tiempos de los usuarios disminuyan, no que aumenten. Aunque este es un caso teórico, se han podido encontrar algunos ejemplos de la vida real, no solo en redes de transporte, sino también en otro tipo de redes.^[3]​

 

Figura 2. Red con la construcción de un nuevo arco entre los puntos X e Y.

Ejemplo

 

Determine el número de vehículos por cada una de las posibles rutas y los tiempos de viaje, antes y después de la construcción de la vía entre A y B. El número total de vehículos que van del punto START al punto END es 4.000.

Red original

Suponga que se tiene una red como la de la figura 3. Los arcos de baja capacidad tiene la siguiente función de demora:

${\displaystyle t_{i}=t_{0}{\frac {V_{a}}{100}}}$ .

Para los arcos de alta capacidad (autopistas), el número de vehículos no les afecta los tiempos de viaje. Para este ejemplo, esos arcos tendrán un tiempo de viaje de 45 min. Antes de la construcción de la nueva vía (línea punteada) existen solamente dos posibles rutas entre los puntos START y END. Los tiempos para los viajeros que circulan por la ruta que pasa por la ciudad A se calculan con:

${\displaystyle t_{a}={\frac {V_{A}}{100}}+45}$ .

Los tiempos para los viajeros que circulan por la ruta que pasa por la ciudad B se calculan con:

${\displaystyle t_{a}={\frac {V_{B}}{100}}+45}$ .

La restricción para el problema de optimización es:

${\displaystyle V_{A}+V_{B}=4000}$ .

Sustituyendo la restricción en una de las dos ecuaciones e igualando con la sobrante, se obtiene que ${\displaystyle V_{A}=V_{B}=2.000}$ . Con esta solución, los usuarios por cualquiera de las dos vías se tardarán ${\displaystyle {\tfrac {2000}{100}}+45=65}$  minutos.

Red modificada

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 ${\displaystyle {\tfrac {V_{T}}{100}}+2={\tfrac {4000}{100}}+2=42<45}$ . Al final, todos los usuarios tomarán la misma ruta y el tiempo total de viaje será:

${\displaystyle {\tfrac {4000}{100}}+2+{\tfrac {4000}{100}}=82}$  minutos.

Este tiempo es mayor que el tiempo antes de hacer la mejora.

Generalización a redes más complejas

Vale la pena preguntarse si existe evidencia en el mundo real de redes de transporte que aumenten su eficacia al ser privadas de alguna vía que antes formaba parte de ellas. La cuestión en sí es difícil de responder, pues las redes de transporte humanas son claramente muy complejas y en general hay muchos factores responsables de la eficacia de la red.

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.

Modelamiento de una red de transporte a través de un grafo

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.

Comience definiendo la red como el grafo ${\displaystyle G=(V,E)}$  con un vértice de salida ${\displaystyle s}$  y otro de llegada ${\displaystyle t}$  y denote el conjunto de los caminos simples que van de ${\displaystyle s}$  a ${\displaystyle t}$  como ${\displaystyle P\neq \emptyset }$ , el flujo de la red es un número real no negativo y para un flujo fijo se define el flujo del tránsito en un camino ${\displaystyle p\in P}$  como ${\displaystyle f_{p}}$ , y se dice que ${\displaystyle f_{e}=\sum _{p\in P:e\in p}f_{p}}$  es la cantidad de tráfico que pasa por la arista ${\displaystyle e}$  en la ruta ${\displaystyle s-t}$ . La cantidad de tráfico en toda la red se denomina la tasa de tráfico y se nota con una ${\displaystyle r}$  y el flujo se dice factible si ${\displaystyle \sum _{p\in P}f_{p}=r}$ .

Modelamos la "congestión" de la red asignándole a cada arista ${\displaystyle e}$  una función no negativa, continua y no decreciente llamada función de demora ${\displaystyle l_{e}}$  que describe la congestión en la arista ${\displaystyle e}$  como función de el flujo ${\displaystyle f_{e}}$  la demora total de un ${\displaystyle s-t}$  camino ${\displaystyle p}$  con respecto al flujo ${\displaystyle f}$  está dado entonces por ${\displaystyle l_{p}(f)=\sum _{e\in e}l_{e}(f_{e})}$ . Por último se define la tripla ${\displaystyle (G,r,l)}$  como una instancia.^[4]​

Flujo de Nash

En teoría de juegos es bien conocido el concepto del Equilibrio de Nash, en este ámbito; y dado que la decisión de cada usuario al elegir una ruta es una decisión egoísta, podemos interpretar el equilibrio de Nash como una propiedad del flujo a través de la red.

Dado ${\displaystyle f}$  un flujo factible para ${\displaystyle (G,r,l)}$  se dice que este es un Nash-flujo o simplemente un equilibrio de Nash si para toda ${\displaystyle p_{1},p_{2}\in P}$  con ${\displaystyle f_{p_{1}}>0}$ , se cumple ${\displaystyle l_{p_{1}}(f)\leq l_{p_{2}}(f)}$ .^[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. Además también se sabe que en una red en donde los usuarios pueden escoger su ruta de forma egoísta tiene un único equilibrio de Nash.^[6]​

La paradoja en grafos aleatorios

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 ${\displaystyle s}$  (y ${\displaystyle t}$ ), 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 ${\displaystyle s}$  y ${\displaystyle t}$ , 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 ${\displaystyle f}$ ) en el que se concentra todo el flujo del sistema, y de ahí hasta el de llegada.

 

Figura4. Conjuntos de aristas.

Cada uno de estos dos conjuntos de vías vistos como conjuntos de aristas del grafo se deben clasificar en tres tipos: Primero están las aristas cuya función de demora es constante (como las grandes avenidas de las cuales se espera teóricamente nunca se congestionen), segundo están las aristas cuya función de demora tiende a aumentar a medida que aumenta el tráfico, y tercero el resto de las aristas.

 

Figura 5. Diagrama de clasificación de vías.

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.

Referencias

1. New Scientist,42nd St Paradox: Cull the best to make things better, 16 de enero de 2014 por Justin Mullins
2. . Roughgarden, Tim; Tardos, Éva. «How Bad is Selfish Routing?». Journal of the ACM. desde el original el 9 de abril de 2016. Consultado el 18 de julio de 2016. 
3. C. Fisk and S. Pallotion: Empirical Evidence for Equilibrium Paradoxes With Implications for Optimal Planning Strategies. TRANSPORT. RES. Vol. 15A, no. 3, pp. 245-248. 1981
4. Greg Valiant and Tim roughgarden: Braess's Paradox in Large Random Graphs, Stanford University and Harvard University, 2006.
5. T. Roughgarden and É. Tardos. How bad is selfish routing? journal of the ACM, 2002.
6. M. Beckmann, C.B. Mcguire, and C.B. Winsten. Studies in the Economics of transportation. Yale University Press, 1956.

•   Datos: Q897194
•   Multimedia: Braess's paradox