Routing Games with Edge Priorities

ACM Transactions on Economics and Computation, vol. 10, pp. 1–27

Abstract

Routing games over time are widely studied due to various applications, e.g., transportation, road and air traffic control, logistic in production systems, communication networks like the internet, and financial flows. In this article, we present a new competitive packet routing game with edge priorities motivated by traffic and transportation. In this model a set of selfishly acting players travels through the network over time. If the number of players who want to enter an edge at the same time exceeds the inflow capacity of this edge, then edge priorities with respect to the preceding edge are used to resolve these conflicts, which is similar to right-of-way rules in traffic. We analyze the efficiency of pure Nash equilibria, present an efficient algorithm for computing equilibria in symmetric games, and show that it is NP -hard to decide whether a Nash equilibrium exists in an asymmetric game. Furthermore, we address the problem of constructing optimal priorities.

Authors 3

1. Robert Scheffler

   Brandenburg University of Technology Cottbus-Senftenberg

   Affiliation as printed

   Brandenburg University of Technology, Cottbus, Germany

2. Martin Strehler
   Affiliation as printed

   Brandenburg University of Technology, Zwickau, Germany

3. Laura Vargas Koch Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen, Germany