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

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

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 $\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.

Computer Science and Game Theory (cs.GT); Artificial Intelligence (cs.AI); Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC)

arXiv:2611.01234 [cs.GT]

(or arXiv:2611.01234v1 [cs.GT] for this version)

https://doi.org/10.48550/arXiv.2611.01234 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.