EUVIMEDDescubrir EUVIMED
Open access · CC BY 4.0

Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time

Neil Olver, Leon Sering, Laura Vargas Koch

Journal of the ACM · 2026-08-31 · 73 (4) · 1-40

DOI: 10.1145/3815167 ↗

At a glance

Journal article in Journal of the ACM, published online on 2026-08-11. Written by Neil Olver and 2 co-authors. 34 references. The full text is freely available (open access, CC BY 4.0).

ResumenDatos bibliográficosCiteRelated studies

Abstract (original language)

We consider a dynamic model of traffic that has received a lot of attention in the past few years. Infinitesimally small agents aim to travel from a source to a destination as quickly as possible. Flow patterns vary over time, and congestion effects are modeled via queues, which form based on the deterministic queueing model whenever the inflow into a link exceeds its capacity. Are equilibria in this model meaningful as a prediction of traffic behavior? For this to be the case, a certain notion of stability under ongoing perturbations is needed. Real traffic consists of discrete, atomic “packets”, rather than being a continuous flow of non-atomic agents. Users may not choose an absolutely quickest route available, if there are multiple routes with very similar travel times. We would hope that in both these situations — a discrete packet model, with packet size going to 0, and ε-equilibria, with ε going to 0 — equilibria converge to continuous and exact equilibria in the flow over time model. No such convergence results were known. We show that such a convergence result does hold in single-commodity instances for both of these settings, in a unified way. More precisely, we introduce a notion of “strict” ε-equilibria, and show that these must converge to the exact dynamic equilibrium in the limit as ε → 0. We then show that results for the two settings mentioned can be deduced from this with only moderate further technical effort.

Cite

APA

Olver, N., Sering, L., & Koch, L. V. (2026). Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time. Journal of the ACM, 73(4), 1-40. https://doi.org/10.1145/3815167

Vancouver

Olver N, Sering L, Koch LV. Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time. Journal of the ACM. 2026;73(4):1-40. doi:10.1145/3815167

BibTeX
@article{Olver2026,
  author = {Olver, Neil and Sering, Leon and Koch, Laura Vargas},
  title = {Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time},
  journal = {Journal of the ACM},
  year = {2026},
  volume = {73},
  number = {4},
  pages = {1--40},
  doi = {10.1145/3815167}
}
Start for free →