Strategic Arrivals into Queueing Networks: The Network Concert Queueing Game

Queueing networks models typically assume that the arrival process is exogenous and unaffected by admission control, scheduling policies, etc. In many situations, however, users choose the time of their arrival strategically, taking delay and other metrics into account. In this paper, we develop a framework to study such strategic arrivals into queueing networks. We study the population game wherein users strategically choose when to arrive at a parallel queueing network and upon arrival, which of the queues to join. The queues start service at given times, which can potentially be different. We characterize the (strategic) arrival process at each of the queues and the price of anarchy of the ensuing strategic arrival game. We then extend the analysis to multiple populations of users, each with a different cost metric. The equilibrium arrival profile and price of anarchy are derived. Finally, we extend this to general feedforward network architectures by modeling the arrival timing game as a two-stage extensive form game. We prove the existence and essential uniqueness of equilibria. We also study more specific network topologies, like tandem and trellis networks, and we derive the equilibrium arrival and routing profiles. We show that there exists an equivalent parallel queueing network that has the same equilibrium arrival profile. Thus, the price of anarchy of the arrival game is then implied by that of the parallel queueing network.