Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.04811 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909482760536064 |
|---|---|
| author | Schmand, Daniel Schürenberg, Torben Strehler, Martin |
| author_facet | Schmand, Daniel Schürenberg, Torben Strehler, Martin |
| contents | We investigate packet routing games in which network users selfishly route themselves through a network over discrete time, aiming to reach the destination as quickly as possible. Conflicts due to limited capacities are resolved by the first-in, first-out (FIFO) principle. Building upon the line of research on packet routing games initiated by Werth et al., we derive the first non-trivial bounds for packet routing games with FIFO. Specifically, we show that the price of anarchy is at most 2 for the important and well-motivated class of uniformly fastest route equilibria introduced by Scarsini et al. on any linear multigraph. We complement our results with a series of instances on linear multigraphs, where the price of stability converges to at least $\frac{e}{e-1}$. Furthermore, our instances provide a lower bound for the price of anarchy of continuous Nash flows over time on linear multigraphs which establishes the first lower bound of $\frac{e}{e-1}$ on a graph class where the monotonicity conjecture is proven by Correa et al. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_04811 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Price of Anarchy in Packet Routing Games with FIFO Schmand, Daniel Schürenberg, Torben Strehler, Martin Computer Science and Game Theory We investigate packet routing games in which network users selfishly route themselves through a network over discrete time, aiming to reach the destination as quickly as possible. Conflicts due to limited capacities are resolved by the first-in, first-out (FIFO) principle. Building upon the line of research on packet routing games initiated by Werth et al., we derive the first non-trivial bounds for packet routing games with FIFO. Specifically, we show that the price of anarchy is at most 2 for the important and well-motivated class of uniformly fastest route equilibria introduced by Scarsini et al. on any linear multigraph. We complement our results with a series of instances on linear multigraphs, where the price of stability converges to at least $\frac{e}{e-1}$. Furthermore, our instances provide a lower bound for the price of anarchy of continuous Nash flows over time on linear multigraphs which establishes the first lower bound of $\frac{e}{e-1}$ on a graph class where the monotonicity conjecture is proven by Correa et al. |
| title | On the Price of Anarchy in Packet Routing Games with FIFO |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2502.04811 |