Lune

FOCS2021Top-tier venue

Continuity, Uniqueness and Long-Term Behavior of Nash Flows Over Time

Neil Olver, Leon Sering, Laura Vargas Koch

Abstract

We consider a dynamic model of traffic that has received a lot of attention in the past few years. Users control infinitesimal flow particles aiming to travel from a source to destination as quickly as possible. Flow patterns vary over time, and congestion effects are modeled via queues, which form whenever the inflow into a link exceeds its capacity. Despite lots of interest, some very basic questions remain open in this model. We resolve a number of them: • We show uniqueness of journey times in equilibria. • We show continuity of equilibria: small perturbations to the instance or to the traffic situation at some moment cannot lead to wildly different equilibrium evolutions. • We demonstrate that, assuming constant inflow into the network at the source, equilibria always settle down into a “steady state” in which the behavior extends forever in a linear fashion. One of our main conceptual contributions is to show that the answer to the first two questions, on uniqueness and continuity, are intimately connected to the third. Our result also shows very clearly that resolving uniqueness and continuity, despite initial appearances, cannot be resolved by analytic techniques, but are related to very combinatorial aspects of the model. To resolve the third question, we substantially extend the approach of Cominetti et al. [1], who show a steady-state result in the regime where the input flow rate is smaller than the network capacity. The full version of this extended abstract can be found on the arXiv preprint server as article 2111.06877

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

2 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time cites Machine-Learned Prediction Equilibrium for Dynamic Traffic Assignment
  • Tolls for Dynamic Equilibrium Flows cites Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. Tolls for Dynamic Equilibrium FlowsLukas Graf, Tobias Harks, Julian SchwarzSODA 2025 · 2 citations
  2. Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over TimeNeil Olver, Leon Sering, Laura Vargas KochFOCS 2023

Builds on2

  1. Machine-Learned Prediction Equilibrium for Dynamic Traffic AssignmentLukas Graf, Tobias Harks, Kostas Kollias, Michael MarklAAAI 2022 · 7 citations
  2. Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over TimeNeil Olver, Leon Sering, Laura Vargas KochFOCS 2023

Related papers

  1. The route to chaos in routing games: When is price of anarchy too optimistic?Thiparat Chotibut, Fryderyk Falniowski, Michal Misiurewicz, Georgios PiliourasNeurIPS 2020 · 34 citations
  2. How Many Lines to Paint the City: Exact Edge-Cover in Temporal GraphsArgyrios Deligkas, Michelle Döring, Eduard Eiben, Tiger-Lily Goldsmith et al.AAAI 2025 · 8 citations
  3. Congested Bandits: Optimal Routing via Short-term ResetsPranjal Awasthi, Kush Bhatia, Sreenivas Gollapudi, Kostas KolliasICML 2022 · 5 citations
  4. Adaptive Approximation Schemes for Matching QueuesAlireza AmaniHamedani, Ali Aouad, Amin SaberiSTOC 2025 · 4 citations
  5. Hop-constrained oblivious routingMohsen Ghaffari, Bernhard Haeupler, Goran ZuzicSTOC 2021 · 15 citations
Dusk over the sea between two cliffs drawn in fine vertical lines