American Scientist

Selfish Routing and the Price of Anarchy. Tim Roughgarden. ix + 196 pp. The MIT Press, 2005. $35.

Suppose you have two routes home from the office. Main Street is never congested, but it has many stoplights, and so the trip always takes an hour. The freeway has a higher speed limit and will get you home in 30 minutes if traffic is light; however, if more than half the commuters in town crowd onto the freeway, traffic freezes up, and that route too takes an hour. Which way should you go?

Assuming that travel time is the only factor at issue, you have nothing to lose by taking the freeway. If you get lucky, you save half an hour; if not, you're no worse off than you would have been on Main Street. The trouble is, everyone else in town reasons the same way, with the result that everyone endures a full hour of bumper-to-bumper on the freeway, while Main Street is deserted. Looking at the situation from a more global point of view, there is clearly a better solution. If the stream of traffic were divided half-and-half between the two roads, no one would have a longer trip, and half the drivers would get home 30 minutes sooner. The average travel time would fall from an hour to 45 minutes.

This curious phenomenon, first described in 1920 by the British economist Arthur Cecil Pigou, is the point of departure for Tim Roughgarden's book Selfish Routing and the Price of Anarchy. "Selfish routing" is the process of choosing a path based strictly on one's own interests, without regard for how that choice may affect anyone else; "the price of anarchy" is the penalty that may have to be paid for this oblivious individualism. These twin concepts have applications not only in highway engineering but also in the design of communications networks, including the Internet. But applications are not really the focus of this book. It is a work of mathematics and theoretical computer science, more concerned with proofs than with practical advice for commuters.

The failure of selfish routing to produce an optimal outcome in Pigou's problem runs counter to some of the intellectual trends of our time. Systems of interacting, autonomous agents are very much in vogue as problem-solving devices and models of complex behavior. In economics, for example, agents competing in a free market are said to achieve a better allocation of resources than any central planning authority could. In biology, "leaderless" algorithms are invoked to explain the flocking of birds, the foraging of ants and the aggregation of cells to form tissues and organs. The powerful appeal of such methods and models is their promise to find optimal solutions through the collective action of simple agents that individually may not even understand the nature of the problem. But, as Pigou showed, it doesn't always work.

Pigou's example is not even the most dramatic failure of selfish routing; there is also Braess's paradox, named for Dietrich Braess of Ruhr University in Bochum, who discovered it in 1968. Explaining this one requires a diagram:

Again there are two ways home, but now each of the routes consists of two segments. Driving a segment labeled 1 takes one hour, regardless of traffic conditions. Travel time on the segments labeled x is proportional to the fraction of traffic traversing the segment; in other words, you can drive an x segment in no time at all if there's no one on the road, but when everyone chooses the segment, it takes a full hour. On this network selfish routing can be expected to produce an equilibrium where traffic splits evenly between the two paths, and everyone gets home in an hour and a half.

Here's where the paradox arises. Suppose we build an additional road of unlimited capacity and zero travel time connecting the midpoints of the two routes, so that drivers can switch from one path to the other:

The new link seems to offer a potential savings in travel time. Since x is never greater than 1 and may be less, a selfish router will always prefer the x segments to the 1 segments. The obvious route of choice follows the first x segment, then the cross connector, and finally the second x segment. But when everyone makes that choice, all drivers wind up spending two hours on the road instead of 90 minutes. Roughgarden states the moral: "With selfish routing, network improvements can degrade network performance."

The problems and paradoxes of selfish routing have been known for decades; Roughgarden's contribution is to work out careful, quantitative estimates of just how much we may have to pay for the privilege of choosing our routes without regard for the commonweal. His analysis is framed in terms of worst-case outcomes; he defines the price of anarchy as "the worst possible ratio between the average travel time of a selfish solution and the smallest achievable average travel time." For example, in the version of Braess's paradox described here, the worst-case price of anarchy is 4/3. Variations on the problem can get much worse: If the mathematical function that relates traffic density to travel time can take any form at all, there is no bound on the price of anarchy. We might never get home.

Roughgarden's book began as a doctoral dissertation and is a fairly challenging work for the casual reader. But the puzzles being solved are worth the effort, and Roughgarden attacks them with a lively mix of game theory, economics and analysis of algorithms. There are also informative notes on the history of the field. But one longs for a bit more detail on what these theoretical results imply where the rubber meets the road. A number of traffic-control devices—carpool lanes, time-of-day tolls, on-ramp metering—seem to address issues related to selfish routing, and it would be useful to know what Roughgarden's mathematics might have to say about their effectiveness.