the potential energy n of the pattern when d takes path p if n < e: modify P so that d takes path p continue the topmost while At each step, if some particular driver could do better by taking an alternate path (a "best response"), doing so strictly decreases the energy of the graph. If no driver has a best response, the graph is at equilibrium. Since the energy of the graph strictly decreases with each step, the best response dynamics algorithm must eventually halt. How far from optimal is traffic at equilibrium? If the travel time functions are linear, that is for some , then at worst, traffic in the energy-minimizing equilibrium is twice as bad as socially optimal. Proof: Let be some traffic configuration, with associated energy and total travel time . For each edge, the energy is the sum of an arithmetic progression, and using the formula for the sum of an arithmetic progression, one can show that . If is the socially-optimal traffic flow and is the energy-minimizing traffic flow, the inequality implies that . Thus, the total travel time for the energy-minimizing equilibrium is at most twice as bad as for the optimal flow. Dynamics analysis of Braess's paradox In 2013, Dal Forno and Merlone interpret Braess's paradox as a dynamical ternary choice problem. The analysis shows how the new path changes the problem. Before the new path is available, the dynamics is the same as in binary choices with externalities, but the new path transforms it into a ternary choice problem. The addition of an extra resource enriches the complexity of the dynamics. In fact, there can even be coexistence of cycles, and the implication of the paradox on the dynamics can be seen from both a geometrical and an analytical perspective. See also References Further reading (translation by Nagurney & Wakolbinger) Katharina Belaga-Werbitzky: „Das Paradoxon von Braess in erweiterten Wheatstone-Netzen mit M/M/1-Bedienern“ Translation of the Braess 1968 article from German to English appears as the article "On a paradox of traffic planning," by D. Braess, A. Nagurney, and T. Wakolbinger in the journal Transportation Science, volume 39, 2005, pp. 446–450. More information T. Roughgarden. "The Price of Anarchy." MIT Press, Cambridge, MA, 2005. External links Software Testing Paradoxes (Dec. 2005) Direct Link Dietrich Braess's homepage The Road Network Paradox Short video illustrating the Braess Paradox with Lego minifigures The Spring Paradox, YouTube