arXiv:2611.01234v1 cs.GT

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

Yu Cheng, Tianle Jiang

제출 2026-11-03

원문 초록

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 $\epsilon$-approximate Nash equilibria ($\epsilon$-NE), in which each player uses a strategy whose cost is at most $1 + \epsilon$ times the minimum available cost. We compare the social costs of $\epsilon$-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 latencies in both general nonatomic congestion games and single-commodity routing games on series-parallel networks, we give tight lower and upper bounds on the relative change in social cost from an exact Nash equilibrium to any $\epsilon$-NE, with matching instances for every $\epsilon$. For small $\epsilon$, the largest possible relative reduction and increase in general congestion games are both $\Theta(\sqrt{d\epsilon})$, independently of the number of resources and populations. In contrast, on series-parallel networks of depth $h$, the largest possible relative reduction is $\Theta(h\epsilon)$, while the largest possible relative increase is known to be $\epsilon$. For the classes of games we study, these results give a tight and quantitative characterization of the possible changes in social cost and establish a separation between general and series-parallel networks.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2611.01234v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.