Selfish Routing and the Price of Anarchy
By Tim Roughgarden
By Tim Roughgarden
Category: Science & Technology
-
$50.00
Sep 19, 2023 | ISBN 9780262549325
Buy the Paperback:
YOU MAY ALSO LIKE
The Change Function
The Complete Idiot’s Guide to Marketing, 2nd edition
Table Of Contents
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
21 Books You’ve Been Meaning to Read
Just for joining you’ll get personalized recommendations on your dashboard daily and features only for members.
Find Out More Join Now Sign In