Selfish Routing and the Price of Anarchy

Front Cover
MIT Press, May 6, 2005 - Computers - 240 pages
0 Reviews
Reviews aren't verified, but Google checks for and removes fake content when it's identified
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 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.

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Introduction
3
13 Applications and Caveats
6
14 How to Read this Book
11
15 Notes
12
Preliminaries
17
22 Flows at Nash Equilibrium
20
23 The Price of Anarchy
22
25 Examples
28
43 Edge Capacities
93
44 Atomic Selfish Routing
99
45 A QuickandDirty Bound on the Price of Anarchy
104
46 Better Bounds for Many Traffic Rates
107
47 Maximum Cost
110
48 Notes
114
Bounding and Detecting Braesss Paradox
121
52 Bounding Braesss Paradox
122

26 Existence and Uniqueness of Nash Flows
34
27 Nash Flows in SingleCommodity Networks
37
28 Notes
41
How Bad Is Selfish Routing?
51
32 The Price of Anarchy with Linear Cost Functions
53
33 A General Upper Bound on the Price of Anarchy
58
34 Matching Lower Bounds in Simple Networks
62
35 Computing the Price of Anarchy
69
36 A Bicriteria Bound in General Networks
73
37 Notes
77
Extensions
85
42 Approximate Nash Flows
89
53 Detecting Braesss Paradox
132
54 Notes
146
Stackelberg Routing
151
62 Stackelberg Strategies and Induced Equilibria
152
63 Three Stackelberg Strategies
153
64 Upper Bounds for Networks of Parallel Links
155
65 Lower Bounds in More General Networks
159
66 The Complexity of Computing Optimal Strategies
162
67 Notes
165
References
169
Index
191
Copyright

Other editions - View all

Common terms and phrases

About the author (2005)

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

Bibliographic information