When Does Diversity of Agent Preferences Improve Outcomes in Selfish Routing
summary
Shows that heterogeneity helps exactly for networks with a specific structure and gives tight constructions otherwise. Diversity always lowers total travel time for single origin destination when the graph is series-parallel and for multi‑commodity instances when the overlap is block‑matching. Provides matching lower bounds by embedding a small bad gadget (the brace graph) and proves a linear worst case bound on the deviation ratio via an alternating path argument that counts alternations eta.
AI-written summary · about
chapters (15)
- 0:00Intro
- 1:57Motivating example 1: risk-aversion
- 5:36Model
- 9:29Cost of flow
- 11:37Questions
- 14:45Equilibrium definition
- 16:28Comparing equilibria with parameter
- 22:57Price of Risk Aversion (PRA) for Arbitrary Latency Functions
- 26:37Heterogeneous vs Homogeneous
- 28:39Network topologies
- 34:01Single commodity: sufficiency
- 35:49Single commodity: necessity
- 36:46Multi-commodity: sufficiency
- 38:31Multi-commodity: necessity
- 41:11Summary