Paradoja de Braess

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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[editar]

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[editar]

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.[1]

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

Ejemplo[editar]

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[editar]

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[editar]

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[editar]

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 transito, el mismo fenómeno se presenta al eliminar algunas vías.

Para ello se va a considerar una red posible de transito 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 mas eficiente.

Modelamiento de una red de transporte a través de un grafo[editar]

Los grafos en si mismos constituyen una manera muy conveniente de modelar y representar redes (no solo de transito), 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 numero real no negativo y para un flujo fijo se define el flujo del transito 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 trafico que pasa por la arista  e en la ruta  s-t . La cantidad de trafico en toda la red se denomina la tasa de trafico 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 esta dado entonces por l_p(f)= \sum_{e\in e} l_e(f_e). Por ultimo se define la tripla (G,r,l) como una instancia.[2]

Flujo de Nash[editar]

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)[3] . 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. Ademas 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[4]


La paradoja en grafos aleatorios[editar]

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 numero 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 numero cuadrático de aristas internas, mientras que solo hay un numero 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 trafico, 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[editar]

  1. 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
  2. Greg Valiant and Tim roughgarden: Braess's Paradox in Large Random Graphs, Stanford University and Harvard University, 2006.
  3. T. Roughgarden and É. Tardos. How bad is selfish routing? journal of the ACM, 2002.
  4. M. Beckmann, C.B. Mcguire, and C.B. Winsten. Studies in the Economics of transportation. Yale University Press, 1956.