Braess's Paradox - Finding An Equilibrium

Finding An Equilibrium

The above proof outlines a procedure known as Best Response Dynamics, which finds an equilibrium for a linear traffic graph and terminates in a finite number of steps. The algorithm is termed "best response" because at each step of the algorithm, if the graph is not at equilibrium then some driver has a best response to the strategies of all other drivers, and switches to that response.

Pseudocode for Best Response Dynamics:

Let P be some traffic pattern. while P is not at equilibrium: compute the potential energy e of P for each driver d in P: for each alternate path p available to d: compute 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.