Routing Games
Stub. Selfish routing models, existence/uniqueness of equilibrium flows via potential functions, the price of anarchy of selfish routing (including for nonlinear latencies), and mechanisms for reducing it (e.g. tolls, Braess-edge removal). (AGT ch. 18)
The workhorse chapter on the price of anarchy: nonatomic and atomic selfish routing models, existence and uniqueness of equilibrium flow via a Rosenthal / Beckmann potential function, tight price-of-anarchy bounds as a function of the latency function class, and interventions (edge removal, tolls, Stackelberg routing) that provably reduce it.
Outline (TODO — flesh out each)
- Models and examples — nonatomic vs. atomic congestion games
- Existence, uniqueness, and potential functions
- The price of anarchy of selfish routing
- Reducing the price of anarchy (network design, tolls, Stackelberg)