How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?
원문 초록
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 원문에서 확인하세요.
- arXiv:2611.01234v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.