Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914670408892416 |
|---|---|
| author | Olver, Neil Sering, Leon Koch, Laura Vargas |
| author_facet | Olver, Neil Sering, Leon Koch, Laura Vargas |
| contents | 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 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'' $ε$-equilibria, and show that these must converge to the exact dynamic equilibrium in the limit as $ε\to 0$. We then show that results for the two settings mentioned can be deduced from this with only moderate further technical effort. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_04935 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time Olver, Neil Sering, Leon Koch, Laura Vargas Computer Science and Game Theory Optimization and Control 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 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'' $ε$-equilibria, and show that these must converge to the exact dynamic equilibrium in the limit as $ε\to 0$. We then show that results for the two settings mentioned can be deduced from this with only moderate further technical effort. |
| title | Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time |
| topic | Computer Science and Game Theory Optimization and Control |
| url | https://arxiv.org/abs/2402.04935 |