Congestion Games

Follow this topic Ask about this topic

Latest papers

11 papers1 paper in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?
Oct 31, 2026Yu Cheng, Tianle JiangCongestion Games
Brown University. · Duke University.
Warned alike, AI agents avoid the less-crowded road while people take it
Sep 25, 2026Takahiro Ezaki, Naoto Imura, Katsuhiro NishinariCongestion Games Multi-Agent Coordination
Research Center for Advanced Science and Technology, The University of Tokyo, 4-6-1 Komaba, Meguro-ku, Tokyo 153-8904, Japan · Department of Aeronautics and Astronautics, School of Engineering, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan
Competitive mediator games and urban CAV routing markets
Aug 10, 2026Grzegorz JamrózMechanism Design Game Theory
Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland
Natural Invariant Measures for Chaotic Game Dynamics: Finding Order in Chaos
Jul 23, 2026Jakub Bielawski, Thiparat Chotibut, Fryderyk Falniowski +2Dynamical Systems Game Theory
Department of Mathematics, Krakow University of Economics, Rakowicka 27, 31-510 Kraków, Poland · Chula Intelligent and Complex Systems Lab, Department of Physics, Faculty of Science, Chulalongkorn University,Bangkok 10330, Thailand · Department of Mathematical Sciences, Indiana University Indianapolis,402 N. Blackford Street, Indianapolis, Indiana 46202, USA +1
Paradoxes of Game Theoretic Equilibria and Price of Anarchy
Jul 13, 2026Georgios Piliouras, Ian Gemp, Siqi Liu +1Nash Equilibrium Game Theory
Google Deepmind, UK
The Price of Anarchy in Disaggregated Inference
Jun 11, 2026Athos GeorgiouLLM Inference Efficiency Game Theory
NCA
Three Phases of Expert Routing: How Load Balance Evolves During Mixture-of-Experts Training
Apr 5, 2026Charafeddine MouzouniCongestion Games Expert Load Balancing
OPIT – Open Institute of Technology, and Cohorte AI, Paris, France.
Strategic Infrastructure Design via Multi-Agent Congestion Games with Joint Placement and Pricing
Mar 23, 2026Niloofar Aminikalibar, Farzaneh Farhadi, Maria ChliCongestion Games Multi-Agent System Optimization
Aston University, Birmingham, UK, B4 7ET
Zeroth-Order Stackelberg Control in Combinatorial Congestion Games
Feb 26, 2026Saeed Masiha, Sepehr Elahi, Negar Kiyavash +1Frank-Wolfe Algorithms Stackelberg Games
EPFL School of Management of Technology · EPFL Department of Computer and Communications Sciences
Socially-Weighted Alignment: A Game-Theoretic Framework for Multi-Agent LLM Systems
Feb 16, 2026Furkan Mumcu, Yasin YilmazCongestion Games Multi-Agent LLM Systems
University of South Florida
Chaos persists in large-scale multi-agent learning despite adaptive learning rates
Jun 1, 2023Emmanouil-Vasileios Vlatakis-Gkaragkounis, Konstantinos Metaxas, Lampros Flokas +1Adaptive Learning Rate Congestion Games
University of California, Berkeley. · Columbia University. · Singapore University of Technology and Design. +1

Oct 31, 2026J/K move · Enter open · S save

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

Yu Cheng, Tianle Jiang

Brown University. · Duke University.

Congestion Games

Open paper AskPDF arXiv

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.