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:
“This perceiving, active being is what I call mind, spirit, soul, or myself. By which words I do not denote any one of my ideas, but a thing entirely distinct from them, wherein they exist, or, which is the same thing, whereby they are perceived; for the existence of an idea consists in being perceived.”
—George Berkeley (1685–1753)
“Truth exists. The sole purpose of this proposition is to assert the existence of truth against imbeciles and sceptics.”
—Edward Herbert Of Cherbury, Lord (1583–1648)
“I consider, then, the power to annul a law of the United States, assumed by one state, incompatible with the existence of the Union, contradicted expressly by the letter of the Constitution, unauthorized by its spirit, inconsistent with every principle on which it was founded, and destructive of the great object for which it was formed.”
—Andrew Jackson (1767–1845)
“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)