Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time
Journal of the ACM · 31.08.2026 · 73 (4) · 1-40
DOI: 10.1145/3815167 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 11.08.2026. Verfasst von Neil Olver und 2 weiteren Autor:innen. Die Arbeit nennt 34 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
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}
}
EUVIMED