Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time
<|reference_start|>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 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 $\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 in single-commodity instances 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 \to 0$. We then show that results for the two settings mentioned can be deduced from this with only moderate further technical effort.<|reference_end|>
@article{olver2024convergence,
    title={Convergence of Approximate and Packet Routing Equilibria to Nash Flows
  Over Time},
    author={Neil Olver, Leon Sering, Laura Vargas Koch},
    journal={arXiv preprint arXiv:2402.04935},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.04935},
    primaryClass={cs.GT math.OC}
}