How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?

Yu Cheng, Tianle Jiang

We study approximate Nash equilibria in nonatomic congestion games, with the goal of understanding how much the social cost can change when the equilibrium condition is relaxed. We…