Convergence of approximate and packet-routing equilibria to Nash flows over time

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 nonatomic 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 epsilon-equilibria, with epsilon going to 0 -- equilibria converge to dynamic equilibria in the flow-over-time model.

No such convergence results were known.

We show that such a convergence result does hold for both of these settings, in a unified way. More precisely, we introduce a notion of "strict'" epsilon-equilibria, and show that these must converge to the exact dynamic equilibrium in the limit as epsilon goes to 0. We then show that results for the two settings mentioned can be deduced from this with only moderate further technical effort.

This research is joint work with Neil Olver (LSE London) and Laura Vargas Koch (ETH Aachen).