Coping with Selfishness
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
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.