Selfish Routing and the Price of Anarchy

by Tim Roughgarden

Book Overview

An analysis of the loss in performance caused by selfish, uncoordinated behavior in networks.

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...

• Format: Paperback
• Language: English
• ISBN: 0262549328
• ISBN13: 9780262549325
• Release Date: September 2023
• Publisher: MIT Press
• Length: 240 Pages
• Weight: 0.73 lbs.
• Dimensions: 0.4" x 7.0" x 9.0"
• Age Range: 18 years and up
• Grade Range: Postsecondary and higher

Customer Reviews

Bringing Theory to Practice

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 behav

Interesting overview of an important subject

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 r