Selfish Routing and the Price of Anarchy

Front Cover
MIT Press
0 Reviews
 

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

Popular passages

Page viii - Acknowledgments This book would not have been possible without a great deal of help from

References to this book

All Book Search results »

Bibliographic information