The Concert Queueing Game: Fluid Regime with Random Order Service

The concert queueing problem corresponds to determining the equilibrium arrival profile of non-cooperative customers selecting their arrival times to a queue where the service opens at a specified time. The customers are allowed to arrive before or after this time. This problem has a variety of queuing applications including how people queue at airport, movie theaters, passport offices, ration lines, etc. This also captures the settings where large computational jobs are sent to servers that open for service at a specified time. Substantial literature is devoted to studying the more tractable fluid version of this problem, that is, each customer is considered an infinitesimal particle, resulting in a non-atomic game between customers. This allows for explicit determination of the unique equilibrium arrival profile in many such settings as well as the associated socially optimal centralized solution. The knowledge of both then allows the computation of price of anarchy (PoA) in the system. The literature thus far focuses on queues with the first come first serve (FCFS) service discipline. In this paper, we again consider the fluid regime and extend the analysis to the case where the service discipline is random order service (ROS). This is equivalent to the practically equally important processor sharing regime when the service times are exponential. The latter is relevant in computational settings while the former is a good approximation to settings where a customer is selected more or less at random by the server.