La paradoja de Braess

La paradoja de Braess es la observación de que agregar una o más carreteras a una red de carreteras puede ralentizar el flujo general de tráfico a través de ella. La paradoja fue descubierta por primera vez por Arthur Pigou en 1920 y posteriormente recibió el nombre del matemático alemán Dietrich Braess en 1968.

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 que funciona mal podría lograrse eliminando ciertas partes de ella. La paradoja se ha utilizado para explicar casos de mejora del flujo de tráfico cuando se cierran las principales carreteras existentes.

Descubrimiento y definición

Dietrich Braess, matemático de la Universidad del Ruhr, Alemania, notó que el flujo en una red de carreteras podría verse impedido al agregar una nueva carretera, cuando trabajaba en un modelo de tráfico. Su idea era que si cada conductor toma la decisión óptima e interesada sobre qué ruta es más rápida, se podría elegir un atajo con demasiada frecuencia para que los conductores tengan los tiempos de viaje más cortos posibles. Más formalmente, la idea detrás del descubrimiento de Braess es que el equilibrio de Nash puede no equivaler al mejor flujo general a través de una red.

La paradoja se expresa de la siguiente manera:

"Para cada punto de una red de carreteras, déjese dar el número de coches que comienzan desde ella y el destino de los coches. En estas condiciones, se desea estimar la distribución del flujo de tráfico. Si una calle es preferible a 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 más les parece favorable, los tiempos de funcionamiento resultantes no necesitan ser mínimos. Además, es indicado por un ejemplo que una extensión de la red de carreteras puede causar una redistribución del tráfico que resulta en tiempos de funcionamiento más largos individuales."

Agregar capacidad adicional a una red cuando las entidades en movimiento eligen egoístamente su ruta puede, en algunos casos, reducir el rendimiento general. Esto se debe a que el equilibrio de Nash de dicho sistema no es necesariamente óptimo. El cambio de red induce una nueva estructura de juego que conduce al dilema del prisionero (multijugador). En un equilibrio de Nash, los conductores no tienen incentivos para cambiar sus rutas. Si bien 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 seguirán cambiando hasta alcanzar el equilibrio de Nash a pesar de la reducción del rendimiento general.

Si las funciones de latencia son lineales, agregar un borde nunca puede empeorar el tiempo total de viaje en equilibrio en un factor de más de 4/3.

Posibles ejemplos de la paradoja en acción

Prevalencia

En 1983, Steinberg y Zangwill proporcionaron, bajo suposiciones razonables, las condiciones necesarias y suficientes para que ocurriera la paradoja de Braess en una red de transporte general cuando se agrega una nueva ruta. (Tenga en cuenta que su resultado se aplica a la adición de cualquier ruta nueva, no sólo al caso de agregar un único enlace.) Como corolario, obtienen que la paradoja de Braess es tan probable como ocurrir como no ocurrir cuando se agrega una nueva ruta aleatoria.

Tráfico

La paradoja de Braess tiene su contraparte en el caso de una reducción de la red de carreteras (lo que puede provocar una reducción del tiempo de desplazamiento individual).

En Seúl, Corea del Sur, el tráfico alrededor de la ciudad se aceleró cuando se eliminó una autopista como parte del proyecto de restauración de Cheonggyecheon. En Stuttgart, Alemania, después de las inversiones en la red de carreteras en 1969, la situación del tráfico no mejoró hasta que se cerró nuevamente al tráfico un tramo de la carretera recién construida. En 1990, el cierre temporal de la calle 42 en Manhattan, Nueva York, para el Día de la Tierra redujo la congestión en el área. En 2008, Youn, Gastner y Jeong demostraron rutas específicas en Boston, Nueva York y Londres donde eso podría ocurrir realmente y señalaron carreteras que podrían cerrarse para reducir los tiempos de viaje previstos. En 2009, Nueva York experimentó con el cierre de Broadway en Times Square y Herald Square, lo que resultó en un mejor flujo de tráfico y plazas peatonales permanentes.

En 2012, Paul Lecroart, del Instituto de Planificación y Desarrollo de la Isla de Francia, escribió que "A pesar de los temores iniciales, la eliminación de las carreteras principales no provoca un deterioro de las condiciones del tráfico más allá de los ajustes iniciales.. La transferencia de tráfico es limitada y está por debajo de las expectativas". También señala que algunos viajes en vehículos privados (y actividades económicas relacionadas) no se transfieren al transporte público y simplemente desaparecen ("se evaporan").

El mismo fenómeno se observó también cuando el cierre de la vía no era parte de un proyecto urbano sino la consecuencia de un accidente. En 2012, en Rouen, un puente fue destruido por un incendio. Durante los dos años siguientes, se utilizaron más otros puentes, pero se redujo el número total de coches que cruzaban los puentes.

Electricidad

En 2012, los científicos del Instituto Max Planck de Dinámica y Autoorganización demostraron, mediante modelos computacionales, el potencial de que el fenómeno ocurra en redes de transmisión de energía donde la generación de energía está descentralizada.

En 2012, un equipo internacional de investigadores del Institut Néel (CNRS, Francia), INP (Francia), IEMN (CNRS, Francia) y UCL (Bélgica) publicó en Physical Review Letters un artículo mostrando que la paradoja de Braess puede ocurrir en sistemas electrónicos mesoscópicos. En particular, demostraron que agregar un camino para los electrones en una red nanoscópica reducía paradójicamente su conductancia. Esto se demostró tanto mediante simulaciones como mediante experimentos a baja temperatura utilizando microscopía de puerta de barrido.

Manantiales

Un modelo con resortes y cuerdas puede mostrar que un peso colgado puede aumentar de altura a pesar de que se corte una cuerda tensa en el sistema de suspensión, y se sigue de la misma estructura matemática que la paradoja de Braess original.

Para dos resortes idénticos unidos en serie por una cuerda corta, su constante elástica total es la mitad de cada resorte individual, lo que resulta en un estiramiento largo cuando se cuelga un cierto peso. Este sigue siendo el caso a medida que agregamos dos cuerdas más largas flojas para conectar el extremo inferior del resorte superior al peso colgado (extremo inferior del resorte inferior) y el extremo superior del resorte inferior al punto de suspensión (extremo superior del resorte). el resorte superior). Sin embargo, cuando se corta la cuerda corta, las cuerdas más largas se tensan y los dos resortes se vuelven paralelos (en el sentido mecánico) entre sí. La constante de resorte total es el doble que la de cada resorte individual, y cuando la longitud de las cuerdas largas no es demasiado larga, el peso colgado será mayor en comparación con antes de cortar la cuerda corta.

El hecho de que el peso colgado aumente a pesar de cortar una cuerda tensa (la cuerda corta) en el sistema de suspensión es contrario a la intuición, pero se sigue de la ley de Hooke y de la forma en que los resortes funcionan en serie y en paralelo..

Biología

Adilson E. Motter y sus colaboradores demostraron que los resultados de la paradoja de Braess pueden ocurrir a menudo en sistemas biológicos y ecológicos. Motter sugiere que eliminar parte de una red perturbada podría rescatarla. Para la gestión de recursos de las redes alimentarias de especies en peligro de extinción, en las que la extinción de muchas especies podría seguir secuencialmente, la eliminación selectiva de una especie condenada de la red podría, en principio, lograr el resultado positivo de prevenir una serie de extinciones adicionales.

Estrategia de deportes de equipo

Se ha sugerido que en el baloncesto, un equipo puede verse como una red de posibilidades para una ruta para anotar una canasta, con una eficiencia diferente para cada ruta, y un jugador estrella podría reducir la eficiencia general del equipo. análogo a un atajo que se utiliza en exceso, lo que aumenta los tiempos totales de un viaje a través de una red de carreteras. Una solución propuesta para lograr la máxima eficiencia en la puntuación es que un jugador estrella realice aproximadamente el mismo número de tiros que sus compañeros de equipo. Sin embargo, este enfoque no está respaldado por evidencia estadística contundente, como se señala en el artículo original.

Enfoque matemático

Ejemplo

Considere una red de carreteras como se muestra en el diagrama adyacente en el que 4000 conductores desean viajar desde el punto Inicio a Final. El tiempo de viaje en minutos en la carretera Start–A es el número de viajeros (T) dividido por 100, y en Start–B es una constante de 45 minutos (sólo con las carreteras a través de ellos). Si la carretera no existe (por lo que la red de tráfico tiene 4 carreteras en total), el tiempo necesario para conducir la ruta Start–A–End con ${displaystyle a}$ los conductores serían ${displaystyle {tfrac {}}+45}$. El tiempo necesario para conducir la ruta Start–B–End con ${displaystyle b}$ los conductores serían ${fnMicroc} {b}{100}+45}$. Como hay 4000 conductores, el hecho de que ${displaystyle a+b=4000}$ se puede utilizar para derivar el hecho de que ${displaystyle a=b=2000}$ cuando el sistema está en equilibrio. Por lo tanto, cada ruta toma ${displaystyle {tfrac {2000}{100}+45=65}$ minutos. Si una ruta toma menos tiempo, no sería un equilibrio de Nash: un controlador racional cambiaría de la ruta más larga a la ruta más corta.

Ahora supongamos que la línea acorazada A-B es una carretera con un tiempo de viaje extremadamente corto de aproximadamente 0 minutos. Supongamos que el camino está abierto y un conductor intenta Inicio – A–B–End. Por su sorpresa encuentra que su tiempo es ${displaystyle {tfrac {2000}{100}+{tfrac {2001}{100}=40.01}$ minutos, un ahorro de casi 25 minutos. Pronto, más de los 4000 pilotos están probando esta nueva ruta. El tiempo tomado surge de 40.01 y sigue subiendo. Cuando el número de conductores que intentan la nueva ruta llega a 2500, con 1500 todavía en la ruta Start–B–End, su tiempo será ${displaystyle {tfrac {2500}{100}+{tfrac {4000}{100}=65}$ minutos, que no mejora sobre la ruta original. Mientras tanto, esos 1500 conductores se han retrasado ${displaystyle 45+{tfrac {4000}}=85}$ minutos, un aumento de 20 minutos. Están obligados a cambiar a la nueva ruta vía A también, por lo que ahora se necesita ${displaystyle {tfrac {4000}{100}+{tfrac {4000}{100}=80}$ minutos. Nadie tiene ningún incentivo para viajar A-End o Start-B porque cualquier conductor que los intente tomará 85 minutos. Así, la apertura de la ruta cruzada desencadena un cambio irreversible para todos, costando a todos 80 minutos en lugar de los 65 originales. Si cada conductor estuviera de acuerdo en no utilizar la ruta A-B, o si esa ruta estuviera cerrada, cada conductor se beneficiaría con una reducción de 15 minutos en el tiempo de viaje.

Existencia de un equilibrio

Si se supone que el tiempo de viaje de cada persona que conduce sobre un borde es igual, siempre existirá un equilibrio.

Vamos. ${displaystyle L_{e}(x)}$ ser la fórmula para el tiempo de viaje de cada persona que viaja a lo largo del borde ${displaystyle e}$ cuando ${displaystyle x}$ La gente toma ese borde. Supongamos que hay un gráfico de tráfico con ${displaystyle x_{e}}$ gente que conduce por el borde ${displaystyle e}$. Dejar la energía de ${displaystyle e}$, ${displaystyle E(e)}$, estar

${displaystyle sum _{i=1}{x_{e}L_{e}(i)=L_{e}(1)+L_{e}(2)+cdots +L_{e}(x_{e}}}$

(Si) ${displaystyle x_{e}=0}$ Deja ${displaystyle E(e)=0}$). Que la energía total del gráfico de tráfico sea la suma de las energías de cada borde en el gráfico.

Elija una ruta que minimice la energía total. Esta elección debe existir porque hay un número finito de opciones de rutas. Eso será un equilibrio.

Supongamos que, para la contradicción, este no es el caso. Entonces, hay al menos un conductor que puede cambiar la ruta y mejorar el tiempo de viaje. Supongamos que la ruta original es ${displaystyle E_{0},e_{1},ldotse_{n}$ mientras que la nueva ruta es ${fnMicrosoft Sans Serif}$. Vamos. ${displaystyle E}$ ser energía total del gráfico de tráfico, y considerar lo que sucede cuando la ruta ${displaystyle E_{0},e_{1},...e_{n}$ es eliminado. La energía de cada borde ${displaystyle E_{i}$ se reducirá ${displaystyle ¿Qué?$ y así ${displaystyle E}$ se reducirá ${textstyle sum ¿Por qué? }$. Es simplemente el tiempo total de viaje necesario para tomar la ruta original. Si se añade la nueva ruta, ${fnMicrosoft Sans Serif}$, la energía total ${displaystyle E}$ se incrementará por el tiempo total de viaje necesario para tomar la nueva ruta. Debido a que la nueva ruta es más corta que la ruta original, ${displaystyle E}$ debe disminuir en relación con la configuración original, contradiciendo la suposición de que el conjunto original de rutas minimizaba la energía total.

Por lo tanto, la elección de rutas que minimicen la energía total es un equilibrio.

Encontrar un equilibrio

La prueba anterior describe un procedimiento conocido como dinámica de mejor respuesta, que encuentra un equilibrio para un gráfico de tráfico lineal y termina en un número finito de pasos. El algoritmo se denomina "mejor respuesta" porque en cada paso del algoritmo, si el gráfico no está en equilibrio, entonces algún factor tiene la mejor respuesta a las estrategias de todos los demás factores y cambia a esa respuesta.

Pseudocódigo para la mejor dinámica de respuesta:

Vamos. P Sé un patrón de tráfico.
mientras P no está en equilibrio:
computar la energía potencial e de P para cada uno Conductor d dentro P:
 para cada uno sendero alternativo p disponibles d:
computar la energía potencial n del patrón cuando d el camino p si n c) e:
modificación P así d el camino pcontinuar el más alto mientras

En cada paso, si algún conductor en particular podría hacerlo mejor tomando un camino alternativo (una "mejor respuesta"), hacerlo disminuye estrictamente la energía del gráfico. Si ningún conductor tiene la mejor respuesta, la gráfica está en equilibrio. Dado que la energía del gráfico disminuye estrictamente con cada paso, el algoritmo de dinámica de mejor respuesta eventualmente debe detenerse.

¿A qué distancia del óptimo está el tráfico en equilibrio?

Si las funciones del tiempo de viaje son lineales, es decir ${displaystyle L_{e}(x)=a_{e}x+b_{e}$ para algunos ${displaystyle a_{e},b_{e}geq 0}$, entonces en el peor de los casos, el tráfico en el equilibrio que minimiza la energía es el doble de malo que socialmente óptimo.

Prueba: ${displaystyle Z}$ ser alguna configuración de tráfico, con energía asociada ${displaystyle E(Z)}$ y tiempo total de viaje ${displaystyle T(Z)}$. Para cada borde, la energía es la suma de una progresión aritmética, y utilizando la fórmula para la suma de una progresión aritmética, se puede demostrar que ${displaystyle E(Z)leq T(Z)leq 2E(Z)}$. Si ${displaystyle Z_{o}$ es el flujo de tráfico social-optimal y ${displaystyle Z_{e}$ es el flujo de tráfico que minimiza la energía, la desigualdad implica que ${displaystyle T(Z_{e})leq 2E(Z_{e})leq 2E(Z_{o})leq 2T(Z_{o})}$.

Por lo tanto, el tiempo total de viaje para el equilibrio de minimización de energía es como máximo el doble que para el flujo óptimo.

Análisis dinámico de la paradoja de Braess

En 2013, Dal Forno y Merlone interpretan la paradoja de Braess como un problema dinámico de elección ternaria. El análisis muestra cómo el nuevo camino cambia el problema. Antes de que el nuevo camino esté disponible, la dinámica es la misma que en las elecciones binarias con externalidades, pero el nuevo camino lo transforma en un problema de elección ternaria. La adición de un recurso extra enriquece la complejidad de la dinámica. De hecho, incluso puede haber coexistencia de ciclos, y las implicaciones de la paradoja en la dinámica pueden verse desde una perspectiva tanto geométrica como analítica.

Efecto de la topología de la red

Mlichtaich demostró que la paradoja de Braess puede ocurrir si y sólo si la red no es un gráfico de series paralelas.