with Jan A. Van Mieghem
Abstract
We consider a simple timing game in which strategic agents select arrival times to a service facility. Agents find congestion costly and hence try to arrive when the system is under-utilized. Working in discrete time, we characterize pure strategy equilibria for the case of ample service capacity. In this case, agents try to spread themselves out as much as possible and their self-interested actions will lead to a socially optimal outcome if all agents have the same well-behaved delay cost function. For even modest sized problems, the set of possible pure strategy equilibria is quite large, making implementation potentially cumbersome. We consequently examine mixed strategy equilibria and show that there is a unique symmetric equilibrium. Not only is this equilibrium independent of the number of agents and their individual delay cost functions, the arrival pattern it generates approaches a Poisson process as the number of agents and arrival points gets large. Our results extend to the case of limited capacity given an appropriate initialization of the system. In this setting, we also argue that for any initialization, competition among customers will equate the expected workload across the horizon and thus move the system to steady state very quickly. Our model lends support to the traditional literature on strategic behavior in queuing systems. This work has generally assumed that customers arrive according to a renewal process but act strategically upon arrival. We show that assuming renewal arrivals is an acceptable assumption given a large population and long horizon.