Selfish Routing and the Price of Anarchy [Hardcover]

Tim Roughgarden (Author)

Book Description

Publication Date: May 6, 2005

Most of us prefer to commute by the shortest route available, without taking into account the traffic congestion that we cause for others. Many networks, including computer networks, suffer from some type of this "selfish routing." In Selfish Routing and the Price of Anarchy, Tim Roughgarden studies the loss of social welfare caused by selfish, uncoordinated behavior in networks. He quantifies the price of anarchy -- the worst-possible loss of social welfare from selfish routing -- and also discusses several methods for improving the price of anarchy with centralized control.Roughgarden begins with a relatively nontechnical introduction to selfish routing, describing two important examples that motivate the problems that follow. The first, Pigou's Example, demonstrates that selfish behavior need not generate a socially optimal outcome. The second, the counterintiuitve Braess's Paradox, shows that network improvements can degrade network performance. He then develops techniques for quantifying the price of anarchy (with Pigou's Example playing a central role). Next, he analyzes Braess's Paradox and the computational complexity of detecting it algorithmically, and he describes Stackelberg routing, which improves the price of anarchy using a modest degree of central control. Finally, he defines several open problems that may inspire further research. Roughgarden's work will be of interest not only to researchers and graduate students in theoretical computer science and optimization but also to other computer scientists, as well as to economists, electrical engineers, and mathematicians.

Editorial Reviews

Review

"Distributed competitive decision making, as opposed to centralized planning, is emerging as the norm in modern systems such as the Internet. The exciting area of algorithmic game theory, which combines methodology from two rich fields, attempts to identify and understand new issues arising as a consequence of this fact. This book provides a vivid glimpse into this area by dealing comprehensively with one of its well-studied problems."--Vijay V. Vazirani, College of Computing, Georgia Institute of Technology

"Recent trends in the analysis and design of computer networks take into account rationally selfish behavior by the network's different components. This book introduces this exciting interdisciplinary type of analysis and presents some of its clearest and most influential applications." Noam Nisan, School of Computer Science and Engineering, Hebrew University of Jerusalem

"Recent trends in the analysis and design of computer networks take into account rationally-selfish behavior by the network's different components. This book introduces this exciting interdisciplinary type of analysis and presents some of its clearest and most influential applications."--Noam Nisan, School of Computer Science and Engineering, Hebrew University of Jerusalem

From the Inside Flap

"Recent trends in the analysis and design of computer networks take into account rationally-selfish behavior by the network's different components. This book introduces this exciting interdisciplinary type of analysis and presents some of its clearest and most influential applications."
--Noam Nisan, School of Computer Science and Engineering, Hebrew University of Jerusalem

See all Editorial Reviews

Product Details

• Hardcover: 240 pages
• Publisher: The MIT Press (May 6, 2005)
• Language: English
• ISBN-10: 0262182432
• ISBN-13: 978-0262182430
• Product Dimensions: 9.3 x 7.2 x 0.7 inches
• Shipping Weight: 1.4 pounds (View shipping rates and policies)
• Average Customer Review: 4.7 out of 5 stars  See all reviews (3 customer reviews)
• Amazon Best Sellers Rank: #1,889,144 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

5 of 6 people found the following review helpful:

5.0 out of 5 stars Bringing Theory to Practice, January 2, 2006

By 

Subhankar Ray (Plano, Texas USA) - See all my reviews
(REAL NAME)   

This review is from: Selfish Routing and the Price of Anarchy (Hardcover)

Besides containing original results from the author's own PHD thesis, the book has complied results and concepts that can not only jump start a new comer in the field, but also give practical tools for network designers. Starting from the very simple description of Pigou's example, Braess's Paradox, the chapter 2 on preliminary [describing Nash equilibrium, optimal flow], and the most interesting author's note [at the end of each chapter] are very well articulated. Author is very careful about introducing any new term/concept so that he does not lose the reader's attention.


Chapter 3 describes the "worst possible" [the upper bound of the price of anarchy] ratio between the cost of a flow at Nash equilibrium and that of a socially optimal outcome. Author considers cost functions that are linear, quadratic, cubic, polynomial, and M/M/1 delay function.

Chapter 4 extends the results/ bounds from the previous chapters for more general and complicated situations like generalized selfish routing beyond networks [Nonatomic Congestion Games], approximate equilibrium [approximate Nash Flows], selfish routing with explicit edge capacities, and with finite number of network users each controlling a non-negligible amount of flow [that may or may not split]. Example 4.6.1 and the subsequent results shows that the "worst- case inefficiency (or the upper bounds of price of anarchy) of selfish routing should be achieved by only a particular finite range of traffic rates"

Chapter 5 & 6 addresses the interesting design aspects with practical implications, answering the questions how to use a modest degree of centralized control so that selfish routing results in a socially desirable outcome. General network design with arbitrary cost functions, linear network design with linear cost function, Polynomial and Incline network design are considered with and without taxes. In chapter 6, Stackelberg games/routing is studied to see how much central authority can reduce the price of anarchy in a network used by both selfish individuals and some authority. Even though, the strategy reduces the price of anarchy to a constant, the computation complexity is NP hard. However, author stated that there is a fully polynomial-time approximation can be used under certain conditions.

The book started with Pigou's example to show that "selfish behavior need not produce a socially optimal outcome", and Braess's Paradox -"with selfish routing, network improvements can degrade network performance". These statements can seem to be too strong if you ignore the caveats at the section 1.3.4, and the differences with the more general game theory issues beyond networks. Also some readers can correlate this "selfish behavior" with the power of individual dreams/greed that is driving the free market. The "selfish behavior" in this book is different than the one we see in the free market economy which is a closed loop system with feedback to promote sustainable win/win selfish behavior in the long run among the participants. On the other hand the author has considered "centralized optimization" as a separate entity from the selfish participants in the game resembling more like a centralized socialistic government. In an "ideal" free democratic society, "centralized optimization" is by the participants, for the participants.

5.0 out of 5 stars The lost of optimality due to selfish routing, March 2, 2011

By 

Daniel O. Cajueiro "An engineer who is profes... (Brasilia, Brazil) - See all my reviews
(REAL NAME)   

Amazon Verified Purchase

This review is from: Selfish Routing and the Price of Anarchy (Hardcover)

This book presents a wonderful introduction to the mathematical (and computational) foundations of the lost of optimality that arises in selfish routing using the style Definition - Theorem - Examples. It intends to characterize and to provide strategies to deal with the problem of selfish routing and lost of optimality. This book also presents a link between computer science and economic theory.

I believe that this book is an easy reading for those acquainted with real analysis and optimization in Rn.

Although it is not necessary, for those that are not acquainted with the techniques of algorithm game theory and basic notions of game theory, I suggest to read this book in the companion of Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations by Yoav Shoham.

1 of 2 people found the following review helpful:

4.0 out of 5 stars Interesting overview of an important subject, December 9, 2005

By 

Dr. Lee D. Carlson (Baltimore, Maryland USA) - See all my reviews
(VINE VOICE)    (HALL OF FAME REVIEWER)    (REAL NAME)   

Amazon Verified Purchase

This review is from: Selfish Routing and the Price of Anarchy (Hardcover)

Anyone who has observed the behavior of real networks understands fully the tradeoffs that are involved in performance versus cost. What is typically not understood in real business contexts is that such tradeoffs can be analyzed quantitatively using various tools from mathematics. Network managers frequently shy away from using these tools, usually viewing them as esoteric or too complicated to be practical. They instead rely on intuition or some vague notion of commonsense to guide their decisions on bandwidth assignments, load balancing, and so on.

That the latter approach can sometimes lead to trouble is exemplified by the results of this book. Throughout its pages, the author gives simple examples and straightforward mathematical theory to illustrate the issues that can arise in network traffic management. It is readily apparent when reading it, especially the discussion of Braess's Paradox, that a simple, commonsense belief, such as the belief that adding a link to a network will relieve congestion, should be viewed with caution.

What the author wants to study in the book is more general, as he is interested in finding out to what extent networks can be left to the users, and not managed centrally, in order to have the most optimal performance. When users of a network decide for themselves what paths to take in the network, and if their decisions are made without considering the effects on other users, this is called `selfish routing.' Will selfish routing result in the best distribution of traffic flow in a particular network? If not, what is the worst possible loss of social welfare that can result from selfish routing? What the author asks, is the `price of anarchy'?

To motivate his answers to these questions, the author begins with two examples. One of these examples, called `Pigou's example, deals with a simple source-sink network with two links, one of which has a fixed cost and the other a linear one. This example illustrates the fact that selfish behavior does not necessarily optimize social welfare. The second example is called Braess's Paradox, and illustrates the fact that making network improvements can actually adversely affect network performance.

Readers are expected of course to have the necessary mathematical background in order to gain anything from this book. Network design engineers typically have this background, but network managers typically do not. The book therefore will not get the attention it needs from the latter class of people. This is unfortunate since it is the network manager who typically needs to understand the issues and results discussed in this book. They are rigorous results from a mathematical perspective, but there are plenty of historical and empirical data that support them. Very important throughout the book is the notion of a network flow at Nash equilibrium and of an optimal flow. The price of anarchy is defined to be the worst possible ratio between the costs of these two flows.

The reader will find that it is the collection of cost functions that are most important to the calculation of the price of anarchy. He calculates the price of anarchy with cost functions that are linear, quadratic, cubic, p-th order polynomials, and certain functions used in queuing theory. An interesting construction he uses in his analysis is the `anarchy value' of a collection C of cost functions, which he shows gives an upper bound for the price of anarchy of every instance of the network with cost functions in C. This upper bound is independent of the complexity of the network and the number of commodities that are using it. Optimal and Nash flows are shown to be identical, but with different cost functions. One very interesting calculation that the author performs, and one that is very important for network managers, involves comparing the cost of a flow at Nash equilibrium to that of an optimal flow that must route additional traffic. He shows that this comparison is equivalent to comparing a Nash flow in a better network to an optimal flow in the original network. The conclusion of this analysis is that the benefit of central control is exceeded by the benefit of improvements in link technology. For the queuing cost functions (M/M/1 queues to be exact), one needs to double the capacity of every link in order to beat optimal routing.

Since Braess's Paradox is a real issue, it is important to design networks that do not exhibit it. The author approaches this design problem by finding a subgraph of the original network that minimizes the common cost of all traffic in a Nash flow for this subgraph. Because the number of subgraphs is exponential in the size of the instance the author has to resort to approximate algorithms. He calls these approximations `C-approximation' algorithms since they give a solution that is bounded above by C times the optimal solution, where C is a positive real number and is called the `approximation ratio' or `performance guarantee' of the algorithm. The author realizes that such approximations may not exist for NP-hard problems, the author tries to find upper and lower bounds on C. This allows him to find upper and lower bounds on the severity of Braess's paradox for the worst possible case. These bounds of course depend on the cost functions, and the author studies four versions of cost functions, namely where they are arbitrary, linear, polynomial, and "incline." All of these bounds are proven with the assumption that P is not equal to NP. For linear cost functions, he proves that for every e > 0 there is no (4/3 - e)-approximation algorithm and there is no ([n/2] - e)-approximation algorithm for arbitrary cost functions. In addition, he proves that there is no o(p/lnp)-approximation algorithm for polynomial cost functions of order p. For general cost functions and large networks, the conclusion reached is that Braess's Paradox can be arbitrarily severe.