Atomic routing in a deterministic queuing model

• New model for atomic dynamic routing games (bottleneck and makespan/sum objective).
• Polynomial time algorithms for computing maximum and quickest dynamic flows.
• Greedy-type methods compute Nash equilibria in the dynamic game with sum objective.
• Dynamic minimum bottleneck flows and ”narrowest paths” are NP-hard to compute.
• Nash equilibria for bottleneck objective may not exist, test and decision are NP-hard.

The issue of selfish routing through a network has received a lot of attention in recent years. We study an atomic dynamic routing scenario, where players allocate resources with load dependent costs only for some limited time.Our paper introduces a natural discrete version of the deterministic queuing model introduced by Koch and Skutella (2011). In this model the time a user needs to traverse an edge  ee is given by a constant travel time and the waiting time in a queue at the end of  ee. At each discrete time step the first ueue  users of the queue proceed to the end vertex of  ee, where ueue denotes the capacity of the edge  ee. An important aspect of this model is that it ensures the FIFOFIFO  property.We study the complexity of central algorithmic questions for this model such as determining an optimal flow in an empty network, an optimal path in a congested network or a maximum dynamic flow and the question whether a given flow is a Nash equilibrium.For the bottleneck case, where the cost of each user is the travel time of the slowest edge on her path, the main results here are mostly bad news. Computing social optima and Nash equilibria turns out to be NP-complete and the Price of Anarchy is given by the number of users.We also consider the makespan objective (arrival time of the last user) and show that optimal solutions and Nash equilibria in these games, where every user selfishly tries to minimize her travel time, can be found efficiently.