Existence of An Equilibrium
Let be the formula for the cost of people driving along edge . If a traffic graph has linear edges (those of the form where and are constants) then an equilibrium will always exist.
Suppose we have a linear traffic graph with people driving along edge . Let the energy of e, be
(If let ). Let the total energy of the traffic graph be the sum of the energies of every edge in the graph.
Suppose that the distribution for the traffic graph is not an equilibrium. There must be at least one driver who can switch their route and improve total travel time. Suppose their original route is while their 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 . Note that this is simply the total travel time needed to take the original route. If we then add the new route, 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. If we repeat this process, will continue to decrease. As must remain positive, eventually an equilibrium must occur.
Read more about this topic: Braess's Paradox
Famous quotes containing the words existence of, existence and/or equilibrium:
“The existence of good bad literature—the fact that one can be amused or excited or even moved by a book that one’s intellect simply refuses to take seriously—is a reminder that art is not the same thing as cerebration.”
—George Orwell (1903–1950)
“The star is the ultimate American verification of Jean Jacques Rousseau’s Emile. His mere existence proves the perfectability of any man or woman. Oh wonderful pliability of human nature, in a society where anyone can become a celebrity! And where any celebrity ... may become a star!”
—Daniel J. Boorstin (b. 1914)
“They who feel cannot keep their minds in the equilibrium of a pair of scales: fear and hope have no equiponderant weights.”
—Horace Walpole (1717–1797)