arXiv preprint ·
How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 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 $ε$-NE, with matching instances for every $ε$. For small $ε$, the largest possible relative reduction and increase in general congestion games are both $Θ(\sqrt{dε})$, independently of the number of resources and populations. In contrast, on series-parallel networks of depth $h$, the largest possible relative reduction is $Θ(hε)$, while the largest possible relative increase is known to be $ε$. 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
A Compute Center Anyone Can Join: A Peer-to-Peer System for AI Inference
The Competitive Ratio of Online Budgeted Allocation is Strictly Smaller than $1-1/e$
On the Convergence of Alternating Regret Matching Algorithms
When Is a Game a Markov Decision Process? Correspondences Between Game Theory and Reinforcement Learning
Classification Aggregation with Multiple Memberships
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.