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. [21], 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. [16] 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. [5].

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the Price of Anarchy in Packet Routing Games with FIFO

  • Daniel Schmand,
  • Torben Schürenberg,
  • Martin Strehler

摘要

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. [21], 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. [16] 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. [5].