Roughgarden T. Selfish Routing and the Price of Anarchy

MIT Press, 2005. — 208 p.The last several years have seen a tremendous surge of activity at the interface of computer science and economics. This book is a brief introduction to two intertwined facets of this emerging research area, the price of anarchy and selfish routing.
The price of anarchy measures the extent to which competition approximates cooperation. It is a rendezvous between the idea of an equilibrium, an idea fundamental to game theory, and the concept of approximation, which is ubiquitous in theoretical computer science. Selfish routing refers to a mathematical model of traffic in a congested network, and it is the price of anarchy's biggest success story so far. This model is interesting in its own right and has a long history and a wide array of applications. In addition to serving as an introduction, this book provides sufficient preparation for original research in these two areas.
This is a research monograph, not a textbook. Nevertheless, I have endeavored to keep the discussion at a level accessible to an eager first- or second-year doctoral student in a mathematical discipline. Some parts of the book may fall short of this goal, but I hope they are few and far between.
Realistically, I expect that researchers and graduate students in theoretical computer science or in optimization will have the easiest time understanding and appreciating this book. On the other hand, I earnestly hope that readers coming from other parts of computer science and operations research, and from economics, electrical engineering, mathematics, and transportation science will find something that interests them. When I betray my roots as a theoretical computer scientist, be it with jargon, interminable discussions of NP-completeness, or an untreatable addiction to worst-case analysis, I have tried to be honest about it. I hope that readers from other fields will have little trouble looking past these biases.Introduction and PreliminariesPreliminaries
Bounding the Price of Anarchy
How Bad Is Selfish Routing?
Extensions
Coping with Selfishness
Bounding and Detecting Braess's Paradox
Stackelberg Routing