Atomic routing in a deterministic queuing model

Abstract

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 e is given by a constant travel time and the waiting time in a queue at the end of e. At each discrete time step the first ue users of the queue proceed to the end vertex of e, where ue denotes the capacity of the edge e. An important aspect of this model is that it ensures the FIFO 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.

Keywords

• (I) Game theory
• (B) Routing
• Dynamic atomic unsplittable flows
• Equilibria
• Optimal solutions
• Complexity