An ɛ-Nash Equilibrium with High Probability for Strategic Customers in Heavy Traffic

A multiclass queue with many servers is considered, where customers make a join-or-leave decision upon arrival based on queue length information, without knowing the state of other queues. A game theoretic formulation is proposed and analyzed, that takes advantage of a phenomenon unique to heavy traffic regimes, namely, Reiman’s snaphshot principle, by which waiting times are predicted with high precision by the information available upon arrival. The payoff considered is given as a random variable, which depends on the customer’s decision, accounting for waiting time in the queue and penalty for leaving. The notion of an equilibrium is only meaningful in an asymptotic framework, which is taken here to be the Halfin-Whitt heavy traffic regime. The main result is the identification of an ɛ-Nash equilibrium with probability approaching 1. On the way to proving this result, new diffusion limit results for systems with finite buffers are obtained.