every driver were to agree not to use the A–B path, or if that route were closed, every driver would benefit by a 15-minute reduction in travel time. Existence of an equilibrium If one assumes the travel time for each person driving on an edge to be equal, an equilibrium will always exist. Let be the formula for the travel time of each person traveling along edge when people take that edge. Suppose there is a traffic graph with people driving along edge . Let the energy of , , be (If let ). Let the total energy of the traffic graph be the sum of the energies of every edge in the graph. Take a choice of routes that minimizes the total energy. Such a choice must exist because there are finitely many choices of routes. That will be an equilibrium. Assume, for contradiction, this is not the case. Then, there is at least one driver who can switch the route and improve the travel time. Suppose the original route is while the new route is . Let be total energy of the traffic graph, and consider what happens when the route is removed. The energy of each edge will be reduced by and so the will be reduced by . That is simply the total travel time needed to take the original route. If the new route is then added, , the total energy will be increased by the total travel time needed to take the new route. Because the new route is shorter than the original route, must decrease relative to the original configuration, contradicting the assumption that the original set of routes minimized the total energy. Therefore, the choice of routes minimizing total energy is 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