## Selfish Routing and the Price of Anarchy |

### 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 |

169 | |

191 | |

### Other editions - View all

### Common terms and phrases

2DDP allowable cost functions amount of flow approximation algorithm arbitrarily arbitrary cost functions assume atomic unsplittable instances Braess's Paradox ce(fe Chapter congestion games convex program Corollary cost function c(x defined Definition denote edge cost functions electrical network feasible flow feasible for G flow at Nash flow feasible flow for G flow on edges game theory instance G instance G,r,c instances with cost LCF strategy Lemma Let f linear cost functions lower bounds marginal cost mixed strategies Nash equilibrium Nash flow network design problem networks of parallel networks with linear nonatomic nondecreasing nonlinear program NP-complete objective function optimal flow parallel links Pigou's example players polynomial price of anarchy proof of Theorem Proposition 2.2.2 prove routing game s-t path Section selfish routing set of cost shows single-commodity instance single-commodity networks Stackelberg strategy subgraph subgraph H traffic rates Transportation Science trivial algorithm units of flow upper bound vertex vertices worst-case

### Popular passages

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