The concert queueing game: to wait or to be late (Q633818)

The authors introduce the concept queueing game. In this game, a finite large number of customers arrive into a queueing system that starts service at a specified opening time. Each customer may choose his arrival time (before or after opening time) and is interested in early service completion with minimal wait. These goals are presented by a cost function which is additive and linear in the waiting time and service completion time. The main subject of the paper is the fluid model obtained by considering the fluid-scale limit of this stochastic queueing system as the number of arrivals becomes large. In the fluid setting, the authors explicitly identify the unique Nash-equilibrium arrival profile for different classes of customers in terms of their cost parameters. The structural results obtained imply that, in equilibrium, the arrival rate is increasing until the closing time. Also, the waiting queue is maximal at the opening time and monotonically decreases thereafter. In single class setting, the authors show that the price of anarchy (PoA, the efficiency loss relative to the socially optimal solution) is exactly two, while in the multi-class setting tight upper and lower bounds on PoA are developed. Several mechanisms to reduce the PoA are considered.