How much worse is everyone's trip when each driver chooses their own route?
Topics 11 to 15 asked who gains when several players choose. These nine go further: what changes when the moves come in turns (25), when players hold secrets (26), when they meet again (27), when they learn as they go (28), when a shared signal is allowed (29), when each chooses a route (30), when the question is how hard an equilibrium is to find (31), the one place where quantum physics changes a game's value (32), and then a market you design and attack yourself (33).
When each driver picks their own route, nobody is steering the whole, and the result need not be the best the system could do. How bad can it get? The question is the same as asking how much an equilibrium (topic 11) falls short of the best possible plan (topic 03). Tim Roughgarden and Éva Tardos answered it in 2002 for road networks: the ratio is the price of anarchy.
The smallest example is Pigou's. One road always takes 1. The other takes as long as the share of traffic on it. Whatever the others do, the second road is never worse for you, so everyone takes it, and the average trip is 1. If instead half the drivers were sent each way, the second road would take 1/2 for them and the first 1 for the rest, and the average trip would be 3/4. Selfishness costs one third more.
A stranger fact is Braess's paradox (1968). Add a road, free to use, and every driver's trip gets longer. The new road is attractive to each driver one at a time, so they all use it, and together they jam the two roads that were fine before.
The price of anarchy for this kind of network can be bounded without knowing the network: with delays that are linear in the traffic (a fixed part plus a part proportional to the flow), it is never worse than 4/3. Both of the examples above reach that bound.
Pigou. Let x be the share on the crowded road. The average trip is C(x) = x · x + (1 − x) · 1 = x2 − x + 1. At the equilibrium x = 1 this is 1. It is minimised at x = 1/2, where it is 3/4. The ratio is 4/3.
Wardrop's condition. An equilibrium of selfish routing is a flow in which every route that carries traffic has the same trip time, and no unused route is faster. Equivalently, it is the flow that minimises the Beckmann potential, the sum over roads of the area under the delay curve; the best plan instead minimises total trip time. They differ because each driver ignores the delay they add for everyone else.
Braess. With one unit of traffic, delays as in the figure. Routes: S-A-E, S-B-E and (when open) S-A-B-E. Closed: by symmetry half and half, each trip 1/2 + 1 = 3/2. Open: if everyone takes S-A-B-E the trips are 1 + 0 + 1 = 2, while S-A-E would also take 1 + 1 = 2, so nobody gains by leaving: this is the equilibrium (minimising the potential over a grid of 200 steps finds it, flows (0, 0, 1)). Every trip is 2. The best plan is still 3/2, so the price of anarchy is 4/3.
Theorem (Roughgarden and Tardos, 2002). If every road's delay is a linear function of its traffic, the price of anarchy is at most 4/3. Both examples above attain it, so the bound cannot be improved. For delays that rise faster (polynomials of degree d), the bound worsens as d grows.
Slide the share of traffic on Pigou's crowded road, then press the button to open Braess's shortcut. The page finds the equilibrium by minimising the potential on a grid and prints the trip time next to the best plan's.
Real cities Youn, Gastner and Jeong (Physical Review Letters 101, 128701 (2008)) analysed the road networks of Boston, New York and London with models of this kind. Their abstract reports that uncoordinated drivers can waste a considerable amount of their travel time and that, counterintuitively, simply blocking certain streets can partially improve traffic conditions. Whether a given real closure helps is an empirical question; Braess's paradox says only that it is possible.
Networks that are not roads The same model describes data packets choosing routes through the internet and power flowing through a grid. The 4/3 bound is a statement about any network of that kind, whatever its size or shape.
The sources Roughgarden and Tardos, Journal of the ACM 49, 236 (2002), doi:10.1145/506147.506153. Braess, Unternehmensforschung 12, 258 (1968), doi:10.1007/bf01918335.
No quantum link is claimed for this topic.
Check yourself
In Pigou's example, everyone takes the crowded road (trip time equal to the share on it) rather than the road that always takes 1. How does the average trip compare with the best plan?
The equilibrium has everyone on the crowded road, so the average trip is 1. Splitting traffic half and half gives x² + (1 − x) = 1/4 + 1/2 = 3/4. The ratio, the price of anarchy, is 4/3, the worst possible for linear delays.