2025/02/07 by Daniel Schmand, Schmand, Daniel, Torben Schürenberg +3
Computer Science · #Computer Science and Game Theory (cs.GT) #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Network Traffic and Congestion Control #Software-Defined Networks and 5G
paper · pdf · doi:10.48550/arxiv.2502.04811
openalex publication_date 2025/02/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (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 (e)/(e-1) on a graph class where the monotonicity conjecture is proven by Correa et al.