🛣️

A city builds a new road to ease traffic, and traffic gets worse. This is not a mistake in the asphalt; it is a theorem. Selfish drivers, each taking the fastest route, can be led by a new option into a jam that hurts everyone.

Price of anarchy and Braess’s paradox

Equilibrium does not mean efficient. The price of anarchy measures how much selfish behaviour costs compared with a coordinated optimum. For traffic with linear costs the waste is capped at a third, but the direction of “improvement” can be counterintuitive: removing options sometimes helps, and adding them can hurt.

From earlier lessons

Two quick ones before we start.

In a congestion game, a driver's cost rises with the number of...

A Nash equilibrium of a routing game is generally...

Predict, then play

Two demonstrations. Braess: four thousand drivers on two routes, then add a zero-cost shortcut. Pigou: measure how much selfish routing wastes.

Why did that happen?

Take a guess, then reveal the reason

Each driver chases their own fastest route, ignoring the delay they add to others. The free shortcut looks individually attractive, so everyone floods onto it, overloading the congestible segments it connects. At the new equilibrium no one can improve alone, yet all are worse off than before the road existed. The gap between what selfish play produces and what coordination could achieve is the price of anarchy, and Braess shows adding options can widen it.

The math

Definition, price of anarchy

The price of anarchy is the ratio of the total cost at the worst Nash equilibrium to the cost of the socially optimal outcome. It measures the inefficiency of selfish behaviour. For nonatomic routing, where each traveller is infinitesimal, with nonnegative affine latency functions, the price of anarchy is at most $4/3$ .

Pigou. One unit of traffic chooses between a fixed link (cost $1$ ) and a congestible link (cost equal to its load). Selfishly, everyone takes the congestible link (cost $1$ , tied with the fixed one) for total cost $1$ . The optimum splits traffic in half, giving total cost $\tfrac12(1) + \tfrac12(\tfrac12) = 0.75$ . The price of anarchy is $1 / 0.75 = 4/3$ .

Braess. Four thousand drivers, two routes each costing $\tfrac{x}{100} + 45$ . Before any shortcut, traffic splits $2000/2000$ , so each pays $\tfrac{2000}{100} + 45 = 65$ . Add a zero-cost shortcut linking the two congestible halves: every driver now takes both congestible segments, and at equilibrium each pays $\tfrac{4000}{100} + \tfrac{4000}{100} = 80 > 65$ . The extra road made the equilibrium worse.

Work it out

Pigou's 4/3 and Braess's 65 to 80

Pigou. With load $f$ on the congestible link, total cost is $(1-f)\cdot 1 + f\cdot f$ . Selfish drivers push $f$ to $1$ (the congestible link never looks worse than the fixed one to an individual), giving cost $1$ . Minimizing $(1-f) + f^2$ gives $f = \tfrac12$ and cost $0.75$ . Ratio $4/3$ .

Braess. Before: each route carries 2000, cost $2000/100 + 45 = 65$ . After the shortcut, the dominant route for each driver uses two congestible segments each carrying all 4000, so each driver’s time is $40 + 40 = 80$ . Checking it is an equilibrium: deviating to an old pure route would cost $40 + 45 = 85 > 80$ , so no one leaves. The free road raised everyone’s time from 65 to 80.

Key idea

In nonatomic routing with nonnegative affine latency, selfish routing costs at most 4/3 of the optimum. Yet adding a road can make the equilibrium strictly worse, which is Braess’s paradox.

Check yourself

Check yourselfapply

In the Pigou example, selfish routing costs 1 and the optimum costs 0.75. What is the price of anarchy?

Check yourselfanalyse

Braess's paradox shows that adding a road raised travel time from 65 to 80. How is 80 an equilibrium?

Check yourselfbrings back: congestion games

Congestion games guarantee an equilibrium exists. What does this lesson add?

Sources

Roughgarden, T., and Tardos, E. (2002). How bad is selfish routing? Journal of the ACM, 49(2), 236-259.
Braess, D. (1968). Uber ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung, 12, 258-268.

Price of anarchy and Braess's paradox