A Characterization of Universally Optimal Queueing Regimes
For queueing system designers, this provides a theoretical characterization of regimes that guarantee efficiency without parameter tuning.
This paper characterizes queueing regimes that are universally optimal, meaning their equilibrium outcome is socially efficient for all parameter values in an M/M/s queue with strategic customers. The authors find that preemption is unavoidable in such regimes.
We consider an M/M/s queueing model in which customers strategically decide, based on the service reward and waiting cost, whether to join upon arrival or balk and, at any time, whether to remain in the queue or renege. Rational strategic behavior yields an equilibrium whose outcome may be socially efficient or inefficient, depending on the queueing regime. Some regimes yield an efficient equilibrium only under precise calibration to the model parameters. Others are universally optimal, meaning that their equilibrium outcome is efficient for all parameter values. Universal optimality is therefore an appealing property for a planner choosing a queueing regime. We characterize the class of universally optimal queueing regimes. A by-product of our characterization is that preemption plays an unavoidable role in universally optimal regimes.