Paradoja de Braess

La paradoja de Braess dicta que al agregar mayor capacidad a una red, cuando las entidades por ella escogen la ruta de forma egoísta, puede en algunos casos reducir el desempeño de toda la red. La paradoja fue presentada en 1968 por el matemático alemán Dietrich Braess. El trabajo original de Braess mostraba una situación paradójica, en la que la construcción de una vía adicional (inversión de capital), llevaba a que, con la misma demanda de tráfico, los tiempos de viaje para todos los usuarios de la red aumentaran.

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 y 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.​

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

Ejemplo

Figura 3. Imagen de la red

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 por que van del punto START al punto END es 4.000.

Red original

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

$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:

$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:

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

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

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

Sustituyendo la restricción en una de las dos ecuaciones e igualando con la sobrante, se obtiene que $V_{A}=V_{B}=2.000$. Con esta solución, los usuarios por cualquiera de las dos vías se tardarán ${\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 ${\tfrac {V_{T}}{100}}+1={\tfrac {4000}{100}}+1=41$ <45. Al final, todos los usuarios tomarán la misma ruta y el tiempo total de viaje será:

${\tfrac {4000}{100}}+1+{\tfrac {4000}{100}}=81$ 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 hacia 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 si 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 mas generales y cercanos a la realidad donde se presente este comportamiento paradójico.

Comience definiendo la red como el grafo $G=(V,E)$ con un vértice de salida $s$ y otro de llegada $t$ y denote el conjunto de los caminos simples que van de $s$ a $t$ como $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 $p\in P$ como $f_{p}$, y se dice que $f_{e}=\sum _{p\in P:e\in p}f_{p}$ es la cantidad de tráfico que pasa por la arista $e$ en la ruta $s-t$. La cantidad de tráfico en toda la red se denomina la tasa de tráfico y se nota con una $r$ y el flujo se dice factible si $\sum _{p\in P}f_{p}=r$.

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

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 $f$ un flujo factible para $(G,r,l)$ se dice que este es un Nash-flujo o simplemente un equilibrio de Nash si para toda $p_{1},p_{2}\in P$ con $f_{p_{1}}>0$, se cumple $l_{p_{1}}(f)\leq l_{p_{2}}(f)$​. 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​

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 $s$ (y $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 $s$ y $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 $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.