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:||
|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:||
Brian Hayes is senior writer for American Scientist. He is the author of Infrastructure: A Field Guide to the Industrial Landscape (W. W. Norton, 2005).