{"id":"arxiv/2611.01234","url":"https://arxiv.org/abs/2611.01234","tags":["cs.GT","cs.AI","cs.DS","math.OC"],"score":0,"title":"How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?","domain":"cs.GT","source":"arxiv","authors":["Yu Cheng","Tianle Jiang"],"reviews":0,"subject":"cs.GT","summary":"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 consider $ε$-approximate Nash equilibria ($ε$-NE), in which each player uses a strategy whose cost is at most $1 + ε$ times the minimum available cost. We compare the social costs of $ε$-NE and exact Nash equilibria. This lets us quantify, for example, how much a navigation app can reduce total travel time when drivers tolerate routes slightly slower than the fastest available route. For degree-$d$ polynomial…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-31","reactions":{}}