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 whileAt 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.
Read more about this topic: Braess's Paradox
Famous quotes containing the words finding and/or equilibrium:
“There comes a point in many people’s lives when they can no longer play the role they have chosen for themselves. When that happens, we are like actors finding that someone has changed the play.”
—Brian Moore (b. 1921)
“There is a relation between the hours of our life and the centuries of time. As the air I breathe is drawn from the great repositories of nature, as the light on my book is yielded by a star a hundred millions of miles distant, as the poise of my body depends on the equilibrium of centrifugal and centripetal forces, so the hours should be instructed by the ages and the ages explained by the hours.”
—Ralph Waldo Emerson (1803–1882)