Exploring the Braess Paradox: Static Versus Dynamic Assignment

Sylvain Lassarre; Andreas Schadschneider; Antoine Tordeux

doi:10.17815/CD.2025.190

Authors

Sylvain Lassarre IFSTTAR/COSYS/GRETTIA, University Gustave Eiffel, France
Andreas Schadschneider Institute for Theoretical Physics and Institute for Physics Didactics, University of Cologne, Cologne, Germany
Antoine Tordeux School of Mechanical Engineering and Safety Engineering, University of Wuppertal, Wuppertal, Germany

DOI:

https://doi.org/10.17815/CD.2025.190

Keywords:

Braess paradox, Closed system, Flow balancing, User & system optima, Interacting particle systems, Dynamic assignment, Monte Carlo simulation

Abstract

The Braess paradox is a well-known phenomenon initially observed in road traffic flow. It points out that increasing network capacity can lead to poorer performance in congested situations, when the drivers attempt to optimise their travel time individually. This paradox is not limited to road transport, but also extends to various information networks. In this article, we examine the Braess paradox in a closed network where demand remains constant. First, we determine the user and global optima of the deterministic system in stationary states with flow balancing. We present explicit formulae for the density intervals at which the Braess paradox occurs. We then compute Monte Carlo simulations of a stochastic mesoscopic traffic model using aggregate data obtained from a queueing model to explore the results. Static assignment models match the deterministic stationary results. In addition, the simulations assess the effectiveness of dynamic assignment, whereby drivers select routes in real time to minimise travel time. Interestingly, behaviour with dynamic assignment deviates from the generic static assignment results, particularly in highly congested situations. These results emphasise the significance of dynamic route selection in relation to Braess's paradox.

References

Pigou, A.: The economics of Welfare. Routledge (2002). URL https://www.taylorfrancis.com/books/mono/10.4324/9781351304368/economics-welfare-arthur-pigou

Braess, D.: Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung (Mathematical Methods of Operations Research) 12, 258 (1968). doi:10.1007/BF01918335

Wardrop, J.: Road paper. Some theoretical aspects of road traffic research. Proceedings of the Institution of Civil Engineers 1(3), 325-362 (1952). doi:10.1680/ipeds.1952.11259

Roughgarden, T.: On the severity of Braess's paradox: Designing networks for selfish users is hard. Journal of Computer and System Sciences 72, 922 (2006). doi:10.1016/j.jcss.2005.05.009

Acemoglu, D., Makhdoumi, A., Malekian, A.: Informational Braess' paradox: The effect of information on traffic congestion. Operational Research 66, 893 (2018). doi:10.1287/opre.2017.1712

Bittihn, S., Schadschneider, A.: Braess’ paradox in the age of traffic information. Journal of Statistical Mechanics: Theory and Experiment 2021(3), 033401 (2021). doi:10.1088/1742-5468/abdeae

Pöppe, C.: Der optimierte Verkehrsstau oder das Paradox von Braess. Spektrum.de Scilogs (2021). URL https://scilogs.spektrum.de/hlf/der-optimierte-verkehrsstau-oder-das-paradox-von-braess/

Wang, A., Tang, Y., Mohmand, Y., Xu, P.: Modifying link capacity to avoid Braess paradox considering elastic demand. Physica A: Statistical Mechanics and its Applications 605, 127951 (2022). doi:10.1016/j.physa.2022.127951

Dafermos, S., Nagurney, A.: On some traffic equilibrium theory paradoxes. Transportation Research Part B: Methodological 18, 101 (1984). doi:10.1016/0191-2615(84)90023-7

Steinberg, R., Zangwill, W.: The prevalence of Braess' paradox. Transportation Science 17, 301 (1983). doi:10.1287/trsc.17.3.301

Valiant, G., Roughgarden, T.: Braess's paradox in large random graphs. In: Proceedings of the 7th ACM Conference on Electronic Commerce, pp. 296-305 (2006). doi:10.1145/1134707.1134740

Baker, L.: Removing roads and traffic lights speeds urban travel. Scientific American pp. 20-21 (2009). URL https://www.scientificamerican.com/article/removing-roads-and-traffic-lights/

Easley, D., Kleinberg, J.: Networks, crowds, and markets: Reasoning about a highly connected world, vol. 1. Cambridge University Press (2010). URL https://www.cs.cornell.edu/home/kleinber/networks-book/

Knödel, W.: Graphentheoretische Methoden und ihre Anwendungen, vol. 13. Springer-Verlag (1969). doi:10.1007/978-3-642-95121-3

Kolata, G.: What if they closed 42nd street and nobody noticed. New York Times 25, 38 (1990). URL https://www.nytimes.com/1990/12/25/health/what-if-they-closed-42d-street-and-nobody-noticed.html

Cohen, J.: The counterintuitive in conflict and cooperation. Am. Scientist 76, 577 (1988). URL https://trid.trb.org/View/289989

Xia, Y., Hill, D.: Dynamic Braess's paradox in complex communication networks. IEEE Transactions on Circuits and Systems II: Express Briefs 60(3), 172-176 (2013). doi:10.1109/TCSII.2013.2240912

Huant, S., Baltazar, S., Liu, P., Sellier, H., Hackens, B., Martins, F., Bayot, V., Wallart, X., Desplanque, L., Pala, M.G.: Planning the electron traffic in semiconductor networks: A mesoscopic analog of the Braess paradox encountered in road networks. AIP Conference Proceedings 1566(1), 229-230 (2013). doi:10.1063/1.4848369

Manik, D., Witthaut, D., Timme, M.: Predicting Braess' paradox in supply and transport networks. arXiv:2205.14685 (2022). URL https://arxiv.org/abs/2205.14685

Nagurney, L., Nagurney, A.: Physical proof of the occurrence of the Braess paradox in electrical circuits. Europhysics Letters 115, 28004 (2016). doi:10.1209/0295-5075/115/28004

Coletta, T., Jacquod, P.: Linear stability and the Braess paradox in nonlinear electric transport. Physical Review E 93, 032222 (2016). doi:10.1103/PhysRevE.93.032222

Tchuisseu, E., Gomila, D., Colet, P., Witthaut, D., Timme, M., Schäfer, B.: Curing Braess’ paradox by secondary control in power grids. New Journal of Physics 20(8), 083005 (2018). doi:10.1088/1367-2630/aad490

Witthaut, D., Timme, M.: Braess's paradox in oscillator networks, desynchronization and power outage. New Journal of Physics 14(8), 083036 (2012). doi:10.1088/1367-2630/14/8/083036

Pala, M., Baltazar, S., Liu, P., Sellier, H., Hackens, B., Martins, F., Bayot, V., Wallart, X., Desplanque, L., Huant, S.: Transport inefficiency in branched-out mesoscopic networks: An analog of the Braess paradox. Physical Review Letters 108(7), 076802 (2012). doi:10.1103/PhysRevLett.108.076802

Donovan, G.: Biological version of Braess' paradox arising from perturbed homeostasis. Physical Review E 98, 062406 (2018). doi:10.1103/PhysRevE.98.062406

Fouladzadeh, A., Dorraki, M., Min, K., Cockshell, M., Thompson, E., Verjans, J., Allison, A., Bonder, C., Abbott, D.: The development of tumour vascular networks. Communications Biology 4(1), 1111 (2021). doi:10.1038/s42003-021-02632-x

Dong, A., Sohn, L., Lustig, M.: Metal-pad-enhanced resistive pulse sensor reveals complex-valued Braess paradox. Physical Review. E 108(1-1), 014408 (2023). doi:10.1103/PhysRevE.108.014408

Banerjee, K., Bhattacharyya, K.: Open chemical reaction networks, steady-state loads and Braess-like paradox. arXiv:1410.4299 (2014). URL http://arxiv.org/abs/1410.4299

Mizrak, O., Ozalp, N.: Fractional analog of a chemical system inspired by Braess’ paradox. Computational and Applied Mathematics 37, 2503-2518 (2018). doi:10.1007/s40314-017-0462-9

Cohen, J., Horowitz, P.: Paradoxical behaviour of mechanical and electrical networks. Nature 352, 699 (1991). doi:10.1038/352699a0

Penchina, C., Penchina, L.: The Braess paradox in mechanical, traffic, and other networks. American Journal of Physics 71(5), 479 (2003). doi:10.1119/1.1538553

Zhitlukhina, E., Belogolovskii, M., De Leo, N., Fretto, M., Sosso, A., Seidel, P.: Quantum coherent transport in a three-arm beam splitter and a Braess paradox. International Journal of Quantum Information 15(08), 1740011 (2017). doi:10.1142/S0219749917400111

Drinko, A., Andrade, F.M., Bazeia, D.: Narrow peaks of full transmission in simple quantum graphs. Physical Review A 100, 062117 (2019). doi:10.1103/PhysRevA.100.062117

Banerjee, A., Bej, P.: Braess paradox in a quantum network. Physical Review A 104, 052622 (2021). doi:10.1103/PhysRevA.104.052622

Braess, D.: A Paradox on Traffic Networks. https://homepage.ruhr-uni-bochum.de/dietrich.braess/#paradox (2019). [Online; accessed 25-Mai-2024]

Yao, J., Cheng, Z., Chen, A.: Bibliometric analysis and systematic literature review of the traffic paradoxes (1968-2022). Transportation Research Part B: Methodological 177, 102832 (2023). doi:10.1016/j.trb.2023.102832

Irvine, A.: How Braess' paradoxon solves Newcomb's problem. International Studies in the Philosophy of Science 7, 141 (1993). doi:10.1080/02698599308573460

Rapoport, A., Kugler, T., Dugar, S., Gisches, E.: Choice of routes in congested traffic networks: Experimental tests of the Braess paradox. Games and Economic Behavior 65, 538 (2009). doi:10.1016/j.geb.2008.02.007

Zhang, H.F., Yang, Z., Wu, Z.X., Wang, B.H., Zhou, T.: Braess's paradox in epidemic game: better condition results in less payoff. Scientific Reports 3, 3292 (2013). doi:10.1038/srep03292

Skinner, B.: The price of anarchy in basketball. Journal of Quantitative Analysis in Sports 6, 3 (2009). doi:10.2202/1559-0410.1217

Nagurney, A., Parkes, D., Daniele, P.: The internet, evolutionary variational inequalities, and the time-dependent Braess paradox. Computational Management Science 4, 355 (2007). doi:10.1007/s10287-006-0027-7

Turner, K., Wolpert, D.: Collective intelligence and Braess' paradox. In: Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p. 104 (2000). URL https://www.aaai.org/Papers/AAAI/2000/AAAI00-016.pdf

Zhu, W., Zhang, J., Ye, S., Xiang, W.: Braess paradox under the bi-objective user equilibrium. Expert Systems with Applications 213, 118871 (2023). doi:10.1016/j.eswa.2022.118871

Colombo, R., Holden, H.: On the Braess paradox with nonlinear dynamics and control theory. Journal of Optimization Theory and Applications 168, 216 (2016). doi:10.1007/s10957-015-0729-5

Sousa, A., Chaves, A., Farias, G., Peeters, F.: Braess paradox at the mesoscopic scale. Physical Review B 88, 245417 (2013). doi:10.1103/PhysRevB.88.245417

Pala, M., Sellier, H., Hackens, B., Martins, F., Bayot, V., Huant, S.: A new transport phenomenon in nanostructures: a mesoscopic analog of the Braess paradox encountered in road networks. Nanoscale Research Letters 7, 1-4 (2012). doi:10.1186/1556-276X-7-472

Cohen, J.E., Kelly, F.P.: A paradox of congestion in a queuing network. Journal of Applied Probability 27(3), 730-734 (1990). doi:10.2307/3214558

Kelly, F.P.: Network routing. Philosophical Transactions of the Royal Society of London. Series A: Physical and Engineering Sciences 337(1647), 343-367 (1991). doi:10.1098/rsta.1991.0129

Calvert, B., Solomon, W., Ziedins, I.: Braess's paradox in a queueing network with state-dependent routing. Journal of Applied Probability 34(1), 134-154 (1997). doi:10.2307/3215182

Lin, W.H., Lo, H.: Investigating Braess' paradox with time-dependent queues. Transportation Science 43, 117 (2009). doi:10.1287/trsc.1090.0258

Bazzan, A., Klügl, F.: Case studies on the Braess paradox: Simulating route recommendation and learning in abstract and microscopic models. Transportation Research Part C: Emerging Technologies 13, 299 (2005). doi:10.1016/j.trc.2005.07.003

Bittihn, S., Schadschneider, A.: Braess paradox in a network of totally asymmetric exclusion processes. Physical Review E 94, 062312 (2016). doi:10.1103/PhysRevE.94.062312

Bittihn, S., Schadschneider, A.: Braess paradox in networks of stochastic microscopic traffic models. Proceedings of the Traffic and Granular Flow 2017 Conference p. 45 (2019). doi:10.1007/978-3-030-11440-4_6

Case, D., Liu, Y., Kiss, I., Angilella, J.R., Motter, A.: Braess's paradox and programmable behaviour in microfluidic networks. Nature 574, 647 (2019). doi:10.1038/s41586-019-1701-6

Schadschneider, A., Bittihn, S.: Braess' paradox in networks with microscopic stochastic dynamics and traffic information. Proceedings of the Traffic and Granular Flow 2019 Conference p. 563 (2020). doi:10.1007/978-3-030-55973-1_69

Cheng, Z., Yao, J., Chen, A., An, S.: Analysis of a multiplicative hybrid route choice model in stochastic assignment paradox. Transportmetrica A: Transport Science 18(3), 1544-1568 (2022). doi:10.1080/23249935.2021.1953189

R Core Team: R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria (2025). URL https://www.R-project.org/

Tordeux, A., Lämmel, G., Hänseler, F.S., Steffen, B.: A mesoscopic model for large-scale simulation of pedestrian dynamics. Transportation Research Part C: Emerging Technologies 93, 128-147 (2018). doi:10.1016/j.trc.2018.05.021

Klamroth, K., Lang, B., Seyfried, A., Stiglmayr, M.: Network simulation for pedestrian flows with hydefs. Collective dynamics 5, 1-16 (2020)

Andjel, E.D.: Invariant measures for the zero range process. The Annals of Probability 10(3), 525-547 (1982). doi:10.1214/aop/1176993765

Evans, M.R., Hanney, T.: Nonequilibrium statistical mechanics of the zero-range process and related models. Journal of Physics A: Mathematical and General 38(19), R195 (2005). doi:10.1088/0305-4470/38/19/R01

Challet, D., Zhang, Y.C.: On the minority game: Analytical and numerical studies. Physica A: Statistical Mechanics and its Applications 256(3-4), 514-532 (1998). doi:10.1016/S0378-4371(98)00260-X

Moro, E.: The minority game: An introductory guide. Advances in Condensed Matter and Statistical Physics (2004). URL https://arxiv.org/abs/cond-mat/0402651

Cavagna, A.: Irrelevance of memory in the minority game. Physical Review E 59(4), R3783 (1999). doi:10.1103/PhysRevE.59.R3783

Braess, D., Nagurney, A., Wakolbinger, T.: On a paradox of traffic planning. Transportation Science 39, 446 (2005). doi:10.1287/trsc.1050.0127

Nagurney, A.: The negation of the Braess paradox as demand increases: The wisdom of crowds in transportation networks. Europhysics Letters 91, 48002 (2010). doi:10.1209/0295-5075/91/48002