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 an, existence of, existence and/or equilibrium:
“When I think of God, when I think of him as existent, and when I believe him to be existent, my idea of him neither increases nor diminishes. But as it is certain there is a great difference betwixt the simple conception of the existence of an object, and the belief of it, and as this difference lies not in the parts or composition of the idea which we conceive; it follows, that it must lie in the manner in which we conceive it.”
—David Hume (1711–1776)
“Realism holds that things known may continue to exist unaltered when they are not known, or that things may pass in and out of the cognitive relation without prejudice to their reality, or that the existence of a thing is not correlated with or dependent upon the fact that anybody experiences it, perceives it, conceives it, or is in any way aware of it.”
—William Pepperell Montague (1842–1910)
“An “unemployed” existence is a worse negation of life than death itself.”
—José Ortega Y Gasset (1883–1955)
“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)