Abstract: In this paper, we study atomic dynamic routing games with multiple destinations. We first show that if the first-in–first-out (FIFO) principle is always fulfilled locally to regulate the congestion, then most probably we cannot guarantee the existence of any reasonable approximate Nash equilibrium. By partly discarding the FIFO principle and introducing destination priorities in the regulation rules, we propose a new atomic routing model. In each such game, we prove that a pure strategy Nash equilibrium always exists and can be computed in polynomial time. In addition, the multicommodity routing game can be iteratively decomposed into a series of well-behaved single-destination routing games, which will provide a good characterization of all NEs of the original game.

Key words: Atomic dynamic routing, Nash equilibrium, Multiple destinations, FIFO