Braess's Paradox - How Far From Optimal Is Traffic at Equilibrium

How Far From Optimal Is Traffic At Equilibrium

At worst, traffic in equilibrium is twice as bad as socially optimal

Proof

= starting point for car j

= target for car j

Strategies for car j are possible paths from to

Each edge e has a travel function for some

Energy on edge e with x drivers:

Total time spent by all drivers on that edge:

((where there are x terms))

E(e) is less than or equal to T(e) and

\begin{align} L_e(1) + \cdots + L_e(x) &= a_e(1+2+\cdots+x) + b_e x \\ & = a_e \tfrac{x (x+1)}{2} + b_e x \\ & = x ( a_e \tfrac{x+1}{2} + b_e ) \\ & \geq \tfrac{1}{2} x ( a_e x + b_e ) \\ & = \tfrac{1}{2} T(e) \\ \end{align}

Resulting Inequality

If Z is a traffic pattern:

If we start from a socially optimal traffic pattern Z and end in an equilibrium pattern Z':

\begin{align} SocialCost(Z') & \leq 2 E(Z') \\ & \leq 2 E(Z) \\ & \leq 2 SocialCost(Z) \\ \end{align}

Thus we can see that worst is twice as bad as optimal.

Read more about this topic:  Braess's Paradox

Famous quotes containing the words how far, optimal, traffic and/or equilibrium:

    “It may be tempting to focus on the fact that, even among those who support equality, men’s involvement as fathers remains a far distance from what most women want and most children need. Yet it is also important to acknowledge how far and how fast many men have moved towards a pattern that not long ago virtually all men considered anathema.”
    —Katherine Gerson (20th century)

    “In the most desirable conditions, the child learns to manage anxiety by being exposed to just the right amounts of it, not much more and not much less. This optimal amount of anxiety varies with the child’s age and temperament. It may also vary with cultural values.... There is no mathematical formula for calculating exact amounts of optimal anxiety. This is why child rearing is an art and not a science.”
    —Alicia F. Lieberman (20th century)

    “There was a girl who was running the traffic desk, and there was a woman who was on the overnight for radio as a producer, and my desk assistant was a woman. So when the world came to an end, we took over.”
    —Marya McLaughlin, U.S. television newswoman. As quoted in Women in Television News, ch. 3, by Judith S. Gelfman (1976)

    “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)