You are here

Selfish Routing and The Price of Anarchy

Tim Roughgarden
Publisher: 
MIT Press
Publication Date: 
2005
Number of Pages: 
196
Format: 
Hardcover
Price: 
35.00
ISBN: 
0-262-18243-2
Category: 
Monograph
[Reviewed by
Art Sedighi
, on
08/15/2005
]

The authors takes a different approach to the good-old shortest path problem we all know and love from communication and networking.  Tim proposes a scenario in which the each “packet” is essentially thinking for itself and wants the best way to get to its destination.  There is no overall management of the system, and thus no Quality of Service that is enforced by any single authority.  This scenario, under certain conditions, will in fact have the best results and the most efficient outcome for all the players; a condition which is known as the Nash Equilibrium.  A deviation from such equilibrium will decrease the performance of the overall system, and is calculated value is known as the Price of Anarchy.

The author essentially plays with different cost functions (linear, quadratic, cubic, etc) to determine what the Price of Anarchy would be under each condition.   From the cost condition, one can determine what the Nash Equilibrium would be, and from it, one can determine the cost of not being in equilibrium.  This concept leads to a very interesting notion; one that we rarely realize: if a network is at equilibrium, adding more resources could decrease performance.  This notion is known as Braess’s Paradox throughout the text.  Another school of thought, Pigou’s theory, demonstrates that selfishness does not generate a socially optimal outcome.  The text battles with these two schools of thought, and makes a compelling story for each one. 

This book is highly recommended for Computer Scientists who are interested in Networking Theory and Communication.  The author in this short text introduces a fascinating concept that affects both social welfare and the world of computers.


Art Sedighi received his B.S. degree in Electrical Engineering and will receive his M.S. Degree in Computer Science from Rensselaer in 1998 and 2004 respectively, and is currently pursuing his MS in Bioinformatics from Johns Hopkins University. He is a solutions architect with Platform Computing where he architects enterprise-wide grid solutions for fortune 500 firms in the financial, pharmaceutical and telecommunication industries. His research interests include Grid Computing, Software Engineering and Bioinformatics.

Preface vii
I INTRODUCTION AND PRELIMINARIES 1
1 Introduction 3
2 Preliminaries 17
II BOUNDING THE PRICE OF ANARCHY 49
3 How Bad Is Selfish Routing? 51
4 Extensions 85
III COPING WITH SELFISHNESS 119
5 Bounding and Detecting Braess's Paradox 121
6 Stackelberg Routing 151
References 169
Index 191