Preface vii
I INTRODUCTION AND PRELIMINARIES 1 Introduction 3
1.1 Selfish Routing 3
1.2 Two Motivating Examples 3
1.3 Applications and Caveats 6
1.4 How to Read this Book 11
1.5 Notes 12
2 Preliminaries 17
2.1 The Model 17
2.2 Flows at Nash Equilibrium 20
2.3 The Price of Anarchy 21
2.4 A Characterization of Optimal Flows 22
2.5 Examples 28
2.6 Existence and Uniqueness of Nash Flows 34
2.7 Nash Flows in Single-Commodity Networks 37
2.8 Notes 41
II BOUNDING THE PRICE OF ANARCHY
3 How Bad Is Selfish Routing? 51
3.1 Overview 51
3.2 The Price of Anarchy with Linear Cost Functions 53
3.3 A General Upper Bound on the Price of Anarchy 58
3.4 Matching Lower Bounds in Simple Networks 62
3.5 Computing the Price of Anarchy 69
3.6 A Bicriteria Bound in General Networks 73
3.7 Notes 77
4 Extensions 85
4.1 Nonatomic Congestion Games 85
4.2 Approximate Nash Flows 88
4.3 Edge Capacities 92
4.4 Atomic Selfish Routing 99
4.5 A Quick-and-Dirty Bound on the Price of Anarchy 104
4.6 Better Bounds for Many Traffic Rates 107
4.7 Maximum Cost 110
4.8 Notes 114
III COPING WITH SELFISHNESS
5 Bounding and Detecting Braess's Paradox 121
5.1 Overview 121
5.2 Bounding Braess's Paradox 122
5.3 Detecting Braess's Paradox 132
5.4 Notes 146
6 Stackelberg Routing 151
6.1 Overview 151
6.2 Stackelberg Strategies and Induced Equilibria 152
6.3 Three Stackelberg Strategies 153
6.4 Upper Bounds for Networks of Parallel Links 155
6.5 Lower Bounds in More General Networks 159
6.6 The Complexity of Computing Optimal Strategies 162
6.7 Notes 165
References 169
Index 191
