The Price of Anarchy for Instantaneous Dynamic Equilibria
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2020
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909315274637312 |
|---|---|
| author | Graf, Lukas Harks, Tobias |
| author_facet | Graf, Lukas Harks, Tobias |
| contents | We consider flows over time within the deterministic queueing model and study the solution concept of instantaneous dynamic equilibrium (IDE) in which flow particles select at every decision point a currently shortest path. The length of such a path is measured by the physical travel time plus the time spent in queues. Although IDE have been studied since the eighties, the efficiency of the solution concept is not well understood. We study the price of anarchy for this model and show an upper bound of order $\mathcal{O}(U\cdot τ)$ for single-sink instances, where $U$ denotes the total inflow volume and $τ$ the sum of edge travel times. We complement this upper bound with a family of quite complex instances proving a lower bound of order $Ω(U\cdot\logτ)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2007_07794 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | The Price of Anarchy for Instantaneous Dynamic Equilibria Graf, Lukas Harks, Tobias Computer Science and Game Theory Optimization and Control We consider flows over time within the deterministic queueing model and study the solution concept of instantaneous dynamic equilibrium (IDE) in which flow particles select at every decision point a currently shortest path. The length of such a path is measured by the physical travel time plus the time spent in queues. Although IDE have been studied since the eighties, the efficiency of the solution concept is not well understood. We study the price of anarchy for this model and show an upper bound of order $\mathcal{O}(U\cdot τ)$ for single-sink instances, where $U$ denotes the total inflow volume and $τ$ the sum of edge travel times. We complement this upper bound with a family of quite complex instances proving a lower bound of order $Ω(U\cdot\logτ)$. |
| title | The Price of Anarchy for Instantaneous Dynamic Equilibria |
| topic | Computer Science and Game Theory Optimization and Control |
| url | https://arxiv.org/abs/2007.07794 |