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 de tráfico general a través de ella. La paradoja fue postulada en 1968 por el matemático alemán Dietrich Braess .
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 carreteras principales existentes.
Descubrimiento y definición
Dietrich Braess, matemático de la Universidad de Ruhr , Alemania , notó que el flujo en una red de carreteras podría verse obstaculizado al agregar una nueva carretera, cuando estaba trabajando en el modelado de tráfico . Su idea era que si cada conductor tomaba la decisión óptima en función de sus intereses en cuanto a 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 equipararse con el mejor flujo general a través de una red. [1]
La paradoja se expresa de la siguiente manera:
"Para cada punto de una red de carreteras, indique el número de automóviles que parten de él y el destino de los automóviles. En estas condiciones, se desea estimar la distribución del flujo de tráfico. Si una calle es preferible a otra no depende de sólo en la calidad de la carretera, sino también en la densidad del flujo . Si cada conductor toma el camino que le parece más favorable, los tiempos de ejecución resultantes no tienen por qué ser mínimos. Además, se indica mediante un ejemplo que una extensión de la red de carreteras puede provocar una redistribución del tráfico que se traduce en tiempos de funcionamiento individuales más prolongados ".
Agregar capacidad adicional a una red cuando las entidades en movimiento eligen egoístamente su ruta puede, en algunos casos, reducir el rendimiento general. Eso 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 ningún incentivo para cambiar sus rutas. Si bien el sistema no se encuentra en un 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 cambiando hasta que alcancen el equilibrio de Nash a pesar de la reducción en el 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. [2]
Posibles instancias de la paradoja en acción
Predominio
En 1983, Steinberg y Zangwill proporcionaron, bajo supuestos 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 solo al caso de agregar un solo enlace). Como corolario, obtienen que la paradoja de Braess es casi tan probable que ocurra como no ocurra; su resultado se aplica a redes y adiciones aleatorias en lugar de planificadas. [3]
Tráfico
La paradoja de Braess tiene su contraparte en caso de una reducción de la red de carreteras (que puede provocar una reducción del tiempo de desplazamiento individual). [4]
En Seúl , Corea del Sur , se observó una aceleración del tráfico alrededor de la ciudad cuando se eliminó una autopista como parte del proyecto de restauración de Cheonggyecheon . [5] 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 una sección de la carretera recién construida se cerró de nuevo al tráfico. [6] En 1990, el cierre temporal de 42nd Street en la ciudad de Nueva York para el Día de la Tierra redujo la cantidad de congestión en el área. [7] En 2008, Youn, Gastner y Jeong demostraron rutas específicas en Boston, Nueva York y Londres donde eso podría ocurrir y señalaron carreteras que podrían cerrarse para reducir los tiempos de viaje previstos. [8] En 2009, Nueva York experimentó con cierres de Broadway en Times Square y Herald Square , lo que resultó en un mejor flujo de tráfico y plazas peatonales permanentes. [9]
En 2012, Paul Lecroart, del instituto de planificación y desarrollo de Île-de-France , 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 por debajo de las expectativas ". [4] También señala que algunos viajes en vehículos privados no se transfieren al transporte público y simplemente desaparecen ("evaporan"). [4]
El mismo fenómeno también se observó cuando el cierre de carreteras no era parte de un proyecto urbano sino la consecuencia de un accidente. En 2012 en Rouen , un puente fue quemado por un accidente; durante los dos años siguientes, se utilizaron más otros puentes, pero se redujo el número total de automóviles que cruzaban puentes. [4] Del mismo modo, en 2015 en Varsovia , se cerró un puente; Las autoridades observaron un mayor uso de otras carreteras y transporte público, pero la mitad de los vehículos que cruzaban habitualmente el puente "desaparecieron" (52.000 de 105.000 diarios). [4]
Electricidad
En 2012, científicos del Instituto Max Planck de Dinámica y Autoorganización demostraron, a través de 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. [10]
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 [11] un artículo que mostraba que la paradoja de Braess puede ocurrir en sistemas de electrones mesoscópicos . En particular, demostraron que agregar una ruta para los electrones en una red nanoscópica reducía paradójicamente su conductancia. Eso se demostró tanto mediante simulaciones como mediante experimentos a baja temperatura utilizando microscopía de puerta de barrido .
Biología
Adilson E. Motter y colaboradores demostraron que los resultados de la paradoja de Braess pueden ocurrir a menudo en sistemas biológicos y ecológicos. [12] Motter sugiere que eliminar parte de una red perturbada podría rescatarla. Para la gestión de recursos de las redes tróficas de especies en peligro , 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, producir el resultado positivo de prevenir una serie de extinciones adicionales. [13]
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 vía, y un jugador estrella podría reducir la eficiencia general del equipo, de forma análoga a una atajo que se sobreutiliza aumentando los tiempos totales para 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 dispare aproximadamente la misma cantidad de tiros que sus compañeros de equipo. Sin embargo, este enfoque no está respaldado por pruebas estadísticas sólidas, como se indica en el documento original. [14]
En fútbol, Helenio Herrera es muy conocido por su célebre frase "con 10 [jugadores] nuestro equipo juega mejor que con 11".
Enfoque matemático
Ejemplo
Considere una red de carreteras como se muestra en el diagrama adyacente en la que 4000 conductores desean viajar desde el punto de inicio hasta el final. El tiempo de viaje en minutos en la ruta Start-A es el número de viajeros (T) dividido por 100, y en Start-B es una constante de 45 minutos (del mismo modo con las carreteras frente a ellos). Si la carretera discontinua 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 los conductores serían . El tiempo necesario para conducir la ruta Start-B-End con los conductores serían . Como hay 4000 controladores, el hecho de que se puede utilizar para derivar el hecho de que cuando el sistema está en equilibrio. Por tanto, cada ruta llevaminutos. Si cualquiera de las rutas tomara menos tiempo, no sería un equilibrio de Nash: un conductor racional cambiaría de la ruta más larga a la más corta.
Ahora suponga que la línea discontinua A – B es una carretera con un tiempo de viaje extremadamente corto de aproximadamente 0 minutos. Suponga que la carretera está abierta y un conductor intenta Start-A-B-End. Para su sorpresa, descubre que su tiempo esminutos, un ahorro de casi 25 minutos. Pronto, más de los 4000 conductores están probando esta nueva ruta. El tiempo transcurrido pasa 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áminutos, lo que no mejora la ruta original. Mientras tanto, esos 1500 conductores se han ralentizado paraminutos, un aumento de 20 minutos. También están obligados a cambiar a la nueva ruta a través de A, por lo que ahoraminutos. Nadie tiene ningún incentivo para viajar A-End o Start-B porque cualquier conductor que los pruebe tardará 85 minutos. Por lo tanto, la apertura de la ruta transversal provoca un cambio irreversible por parte de todos, costando a todos 80 minutos en lugar de los 65 originales. Si todos los conductores aceptaran no usar la ruta A – B, o si esa ruta estuviera cerrada, cada El conductor se beneficiaría de una reducción de 15 minutos en el tiempo de viaje.
Existencia de un equilibrio
Si se supone que el tiempo de viaje para cada persona que conduce en un borde es igual, siempre existirá un equilibrio.
Dejar ser la fórmula para el tiempo de viaje de cada persona que viaja a lo largo del borde Cuándo la gente toma esa ventaja. Suponga que hay un gráfico de tráfico con gente conduciendo por el borde . Deja que la energía de, , ser
(Si dejar ). Sea la energía total del gráfico de tráfico la suma de las energías de cada borde del gráfico.
Elija rutas que minimicen la energía total. Esa elección debe existir porque hay un número finito de opciones de rutas. Eso será un equilibrio.
Supongamos, por contradicción, que este no es el caso. Entonces, hay al menos un conductor que puede cambiar la ruta y mejorar el tiempo de viaje. Suponga que la ruta original es mientras la nueva ruta es . Dejar sea la energía total del gráfico de tráfico y considere lo que sucede cuando la ruta es removido. La energía de cada borde será reducido por y entonces el será reducido por . Ese es simplemente el tiempo total de viaje necesario para tomar la ruta original. Si luego se agrega la nueva ruta,, la energía total aumentará con 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, debe disminuir en relación con la configuración original, lo que contradice 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 controlador tiene una mejor respuesta a las estrategias de todos los demás controladores y cambia a esa respuesta.
Pseudocódigo para una mejor dinámica de respuesta:
Sea P un patrón de tráfico.mientras que P no está en equilibrio: Calcule la energía potencial e de P para cada controlador d en P : para cada camino alternativo p disponible para d : Calcule la energía potencial n del patrón cuando d toma la ruta p si n < e : modificar P para que d tome el camino p continúe en la parte superior mientras
En cada paso, si algún conductor en particular podría hacerlo mejor tomando una ruta alternativa (una "mejor respuesta"), hacerlo disminuye estrictamente la energía del gráfico. Si ningún controlador tiene una 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 debe detenerse eventualmente.
¿Qué tan lejos del óptimo está el tráfico en equilibrio?
Si las funciones de tiempo de viaje son lineales, eso es para algunos Entonces, en el peor de los casos, el tráfico en el equilibrio de minimización de energía es dos veces más malo que socialmente óptimo. [15]
Prueba: dejar ser alguna configuración de tráfico, con energía asociada y tiempo total de viaje . Para cada arista, la energía es la suma de una progresión aritmética , y usando la fórmula para la suma de una progresión aritmética, se puede demostrar que. Si es el flujo de tráfico socialmente óptimo y es el flujo de tráfico que minimiza la energía, la desigualdad implica que .
Por lo tanto, el tiempo total de viaje para el equilibrio que minimiza la energía es como máximo dos veces más malo que para el flujo óptimo.
Análisis dinámico de la paradoja de Braess
En 2013, Dal Forno y Merlone [16] interpretan la paradoja de Braess como un problema de elección ternaria dinámica. El análisis muestra cómo la nueva ruta cambia el problema. Antes de que la nueva ruta esté disponible, la dinámica es la misma que en las elecciones binarias con externalidades, pero la nueva ruta la transforma en un problema de elección ternaria. La adición de un recurso adicional enriquece la complejidad de la dinámica. De hecho, incluso puede haber coexistencia de ciclos, y la implicación de la paradoja en la dinámica se puede ver tanto desde una perspectiva geométrica como analítica.
Ver también
- La anomalía de Bélády
- Elección de ruta
- Paradoja de Downs-Thomson
- Paradoja de Jevons
- La constante de Marchetti
- Demanda inducida
- Posición de Lewis-Mogridge
- Ley de Hotelling
- Paradoja del enriquecimiento
- Ola de tráfico
- Paradoja de la distribución
- John Glen Wardrop
- Efecto hidra
- Rata corriendo
- Dieta de carretera
- Bufferbloat
- Rendimientos decrecientes
Referencias
- ^ New Scientist, 42nd St Paradox: Elija lo mejor para mejorar las cosas , 16 de enero de 2014 por Justin Mullins
- ↑ Roughgarden, Tim; Tardos, Éva. "¿Qué tan grave es el enrutamiento egoísta?" (PDF) . Revista de la ACM. Archivado (PDF) desde el original el 9 de abril de 2016 . Consultado el 18 de julio de 2016 .
- ^ Steinberg, R .; Zangwill, WI (1983). "La prevalencia de la paradoja de Braess". Ciencia del transporte . 17 (3): 301. doi : 10.1287 / trsc.17.3.301 .
- ↑ a b c d e (en francés) Olivier Razemon, "Le paradoxde de l '« évaporation »du trafic Automobile", Le monde , jueves 25 de agosto de 2016, página 5. Publicado en línea como "Et si le trafic s' évaporait? " el 24 de agosto de 2016 y actualizado el 25 de agosto de 2016 (página visitada el 19 de septiembre de 2016).
- ^ Easley, D .; Kleinberg, J. (2008). Redes . Prensa de la tienda de Cornell. pag. 71.
- ^ Knödel, W. (31 de enero de 1969). Graphentheoretische Methoden Und Ihre Anwendungen . Springer-Verlag . págs. 57–59. ISBN 978-3-540-04668-4.
- ^ Kolata, Gina (25 de diciembre de 1990). "¿Qué pasa si cierran la calle 42 y nadie se da cuenta?" . New York Times . Consultado el 16 de noviembre de 2008 .
- ^ Youn, Hyejin; Gastner, Michael; Jeong, Hawoong (2008). "Precio de la anarquía en las redes de transporte: control de la eficiencia y la optimización". Cartas de revisión física . 101 (12): 128701. arXiv : 0712.1598 . Código Bibliográfico : 2008PhRvL.101l8701Y . doi : 10.1103 / PhysRevLett.101.128701 . ISSN 0031-9007 . PMID 18851419 . S2CID 20779255 .
- ^ Boyd, Andrew. "Paradoja de Braess" . Motores de nuestro ingenio . Episodio 2814.
- ^ Personal (Instituto Max Planck) (14 de septiembre de 2012), "Study: Solar and wind energy may stabilize the power grid" , R&D Magazine , rdmag.com , consultado el 14 de septiembre de 2012
- ^ Pala, MG; Baltazar, S .; Liu, P .; Sellier, H .; Hackens, B .; Martins, F .; Bayot, V .; Wallart, X .; Desplanque, L .; Huant, S. (2012) [6 de diciembre de 2011 (v1)]. "Ineficiencia del transporte en redes mesoscópicas ramificadas: un análogo de la paradoja de Braess". Cartas de revisión física . 108 (7): 076802. arXiv : 1112.1170 . Código Bibliográfico : 2012PhRvL.108g6802P . doi : 10.1103 / PhysRevLett.108.076802 . ISSN 0031-9007 . PMID 22401236 . S2CID 23243934 .
- ^ Motter, Adilson E. (2010). "Mejora del rendimiento de la red a través del antagonismo: de rescates sintéticos a combinaciones de múltiples fármacos" . BioEssays . 32 (3): 236–245. arXiv : 1003.3391 . doi : 10.1002 / bies.200900128 . PMC 2841822 . PMID 20127700 .
- ^ Sahasrabudhe S., Motter AE, Rescatando ecosistemas de cascadas de extinción mediante perturbaciones compensatorias , Nature Communications 2, 170 (2011)
- ^ Skinner, Brian; Gastner, Michael T; Jeong, Hawoong (2009). "El precio de la anarquía en el baloncesto". Revista de análisis cuantitativo en el deporte . 6 (1). arXiv : 0908.1801 . Código Bibliográfico : 2009arXiv0908.1801S . CiteSeerX 10.1.1.215.1658 . doi : 10.2202 / 1559-0410.1217 . S2CID 119275142 .
- ^ Easley, David; Kleinberg, Jon. "Redes, multitudes y mercados: razonamiento sobre un mundo altamente conectado (8.3 Material avanzado: el costo social del tráfico en equilibrio)" (PDF) . Página de inicio de Jon Kleinberg . Jon Kleinberg. Archivado (PDF) desde el original el 16 de marzo de 2015 . Consultado el 30 de de mayo de el año 2015 . - Esta es la preimpresión de ISBN 9780521195331
- ^ Dal Forno, Arianna; Merlone, Ugo (2013). "Bifurcaciones de colisión fronteriza en un modelo de paradoja de Braess". Matemáticas y Computación en Simulación . 87 : 1–18. doi : 10.1016 / j.matcom.2012.12.001 . ISSN 0378-4754 .
Otras lecturas
- Braess, D. (1969). "Über ein Paradoxon aus der Verkehrsplanung" [Sobre una paradoja de la planificación del tráfico] (PDF) . Unternehmensforschung (en alemán). 12 : 258-268. (traducción de Nagurney & Wakolbinger)
- Katharina Belaga-Werbitzky: "Das Paradoxon von Braess in erweiterten Wheatstone-Netzen mit M / M / 1-Bedienern" ISBN 3-89959-123-2
- La traducción del artículo de Braess 1968 del alemán al inglés aparece como el artículo "Sobre una paradoja de la planificación del tráfico", de D. Braess, A. Nagurney y T. Wakolbinger en la revista Transportation Science, volumen 39, 2005, págs. 446 –450. Más información
- Irvine, AD (1993). "Cómo la paradoja de Braess resuelve el problema de Newcomb". Estudios Internacionales en Filosofía de la Ciencia . 7 (2): 141–160. doi : 10.1080 / 02698599308573460 .
- Steinberg, R .; Zangwill, WI (1983). "La prevalencia de la paradoja de Braess". Ciencia del transporte . 17 (3): 301. doi : 10.1287 / trsc.17.3.301 .
- Rapoport, A .; Kugler, T .; Dugar, S .; Gisches, EJ (2009). "Elección de rutas en redes de tráfico congestionadas: pruebas experimentales de la paradoja de Braess" (PDF) . Juegos y comportamiento económico . 65 (2): 538–571. doi : 10.1016 / j.geb.2008.02.007 .
- T. Roughgarden. "El precio de la anarquía". Prensa del MIT, Cambridge, MA, 2005.
enlaces externos
- Paradojas de las pruebas de software (diciembre de 2005) Enlace directo
- Página de inicio de Dietrich Braess
- La paradoja de la red de carreteras
- Video corto que ilustra la paradoja de Braess con minifiguras de Lego