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:
“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)
“Suppose that humans happen to be so constructed that they desire the opportunity for freely undertaken productive work. Suppose that they want to be free from the meddling of technocrats and commissars, bankers and tycoons, mad bombers who engage in psychological tests of will with peasants defending their homes, behavioral scientists who can’t tell a pigeon from a poet, or anyone else who tries to wish freedom and dignity out of existence or beat them into oblivion.”
—Noam Chomsky (b. 1928)
“When a person hasn’t in him that which is higher and stronger than all external influences, it is enough for him to catch a good cold in order to lose his equilibrium and begin to see an owl in every bird, to hear a dog’s bark in every sound.”
—Anton Pavlovich Chekhov (1860–1904)