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 very existence of government at all, infers inequality. The citizen who is preferred to office becomes the superior to those who are not, so long as he is the repository of power, and the child inherits the wealth of the parent as a controlling law of society.”
—James Fenimore Cooper (1789–1851)
“The hour when you say, “What does my happiness matter? It is poverty and filth, and a wretched complacency. Yet my happiness should justify existence itself!””
—Friedrich Nietzsche (1844–1900)
“That doctrine [of peace at any price] has done more mischief than any I can well recall that have been afloat in this country. It has occasioned more wars than any of the most ruthless conquerors. It has disturbed and nearly destroyed that political equilibrium so necessary to the liberties and the welfare of the world.”
—Benjamin Disraeli (1804–1881)