FREE Delivery in the UK.
Only 1 left in stock (more on the way).
Dispatched from and sold by Amazon. Gift-wrap available.
Selfish Routing and the P... has been added to your Basket

Dispatch to:
To see addresses, please
Or
Please enter a valid UK postcode.
Or
+ £2.80 UK delivery
Used: Good | Details
Condition: Used: Good
Comment: Shows some signs of wear, and may have some markings on the inside. 100% Money Back Guarantee. Shipped to over one million happy customers.
Have one to sell?
Flip to back Flip to front
Listen Playing... Paused   You're listening to a sample of the Audible audio edition.
Learn more
See all 2 images

Selfish Routing and the Price of Anarchy Hardcover – 10 Jun 2005

4.7 out of 5 stars
5 star
2
4 star
1
3 star
0
2 star
0
1 star
0
4.7 out of 5 stars 3 reviews from the U.S.

See all 2 formats and editions Hide other formats and editions
Amazon Price
New from Used from
Hardcover
"Please retry"
£32.95
£19.11 £11.21
Note: This item is eligible for click and collect. Details
Pick up your parcel at a time and place that suits you.
  • Choose from over 13,000 locations across the UK
  • Prime members get unlimited deliveries at no additional cost
How to order to an Amazon Pickup Location?
  1. Find your preferred location and add it to your address book
  2. Dispatch to this address when you check out
Learn more
£32.95 FREE Delivery in the UK. Only 1 left in stock (more on the way). Dispatched from and sold by Amazon. Gift-wrap available.
click to open popover

Enter your mobile number or email address below and we'll send you a link to download the free Kindle App. Then you can start reading Kindle books on your smartphone, tablet, or computer - no Kindle device required.

  • Apple
  • Android
  • Windows Phone

To get the free app, enter your mobile phone number.



Product details

Product description

Review

--Vijay V. Vazirani, College of Computing, Georgia Institute of Technology

--Noam Nisan, School of Computer Science and Engineering, Hebrew University of Jerusalem

--Christos Papadimitriou, C. Lester Hogan Professor of Computer Science, University of California, Berkeley

" 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

" 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

" In recent years we have seen a fascinating confluence of ideas from algorithmic computer science and game theory, chiefly in the service of advancing our understanding of the technological and sociological mystery that is the Internet. Nowhere is the excitement, novelty, power, and elegance of these new ideas exemplified better than in Tim Roughgarden's doctoral dissertation, which is the basis for this important book." --Christos Papadimitriou, C. Lester Hogan Professor of Computer Science, University of California, Berkeley

& quot; 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.& quot; --Noam Nisan, School of Computer Science and Engineering, Hebrew University of Jerusalem

& quot; 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.& quot; --Vijay V. Vazirani, College of Computing, Georgia Institute of Technology

& quot; In recent years we have seen a fascinating confluence of ideas from algorithmic computer science and game theory, chiefly in the service of advancing our understanding of the technological and sociological mystery that is the Internet. Nowhere is the excitement, novelty, power, and elegance of these new ideas exemplified better than in Tim Roughgarden's doctoral dissertation, which is the basis for this important book.& quot; --Christos Papadimitriou, C. Lester Hogan Professor of Computer Science, University of California, Berkeley

"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

"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

"In recent years we have seen a fascinating confluence of ideas from algorithmic computer science and game theory, chiefly in the service of advancing our understanding of the technological and sociological mystery that is the Internet. Nowhere is the excitement, novelty, power, and elegance of these new ideas exemplified better than in Tim Roughgarden's doctoral dissertation, which is the basis for this important book."--Christos Papadimitriou, C. Lester Hogan Professor of Computer Science, University of California, Berkeley

About the Author

Tim Roughgarden is Assistant Professor of Computer Science at Stanford University and recipient of the ACM's Grace Hopper Award.

Customer Reviews

There are no customer reviews yet on Amazon.co.uk.
5 star
4 star
3 star
2 star
1 star

Most Helpful Customer Reviews on Amazon.com (beta) (May include reviews from Early Reviewer Rewards Program)

Amazon.com: 4.7 out of 5 stars 3 reviews
5.0 out of 5 stars The lost of optimality due to selfish routing 2 Mar. 2011
By Daniel O. Cajueiro - Published on Amazon.com
Format: Hardcover Verified Purchase
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.
2 of 3 people found the following review helpful
4.0 out of 5 stars Interesting overview of an important subject 9 Dec. 2005
By Dr. Lee D. Carlson - Published on Amazon.com
Format: Hardcover Verified Purchase
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.
6 of 7 people found the following review helpful
5.0 out of 5 stars Bringing Theory to Practice 3 Jan. 2006
By Subhankar Ray - Published on Amazon.com
Format: 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.
Were these reviews helpful? Let us know