Home | Articles | Past volumes | About | Login | Notify | Contact | Search
 Stochastic Systems > Vol. 3 (2013) open journal systems 

The supermarket game

Jiaming Xu, University of Illinois at Urbana-Champaign
Bruce Hajek, University of Illinois at Urbana-Champaign

A supermarket game is considered with \(N\) FCFS queues with unit exponential service rate and global Poisson arrival rate \(N \lambda\). Upon arrival each customer chooses a number of queues to be sampled uniformly at random and joins the least loaded sampled queue. Customers are assumed to have cost for both waiting and sampling, and they want to minimize their own expected total cost.

We study the supermarket game in a mean field model that corresponds to the limit as \(N\) converges to infinity in the sense that (i) for a fixed symmetric customer strategy, the joint equilibrium distribution of any fixed number of queues converges as \(N \to \infty\) to a product distribution determined by the mean field model and (ii) a Nash equilibrium for the mean field model is an \(\epsilon\)-Nash equilibrium for the finite \(N\) model with \(N\) sufficiently large. It is shown that there always exists a Nash equilibrium for \(\lambda <1\) and the Nash equilibrium is unique with homogeneous waiting cost for \(\lambda \le 1/\sqrt{2}\). Furthermore, we find that the action of sampling more queues by some customers has a positive externality on the other customers in the mean field model, but can have a negative externality for finite \(N\).

AMS 2000 subject classifications: Primary 60K35; secondary 60K25, 91A40.

Keywords: Mean field model, queueing, Nash equilibrium, externality.

Creative Common LOGO

Full Text: PDF

Xu, Jiaming, Hajek, Bruce, The supermarket game, Stochastic Systems, 3, (2013), 405-441 (electronic). DOI: 10.1214/12-SSY093.


[1]    Alanyali, M. and Dashouk, M. (2011). Occupancy distributions of homogeneous queueing systems under opportunistic scheduling. IEEE Transactions on Information Theory 57, 1 (Jan.), 256–266. MR2810282

[2]    Bordenave, C., McDonald, D., and Proutiere, A. (2010). A particle system in interaction with a rapidly varying environment: Mean field limits and applications. Journal on Networks and Heterogeneous Media 5, 31–62. MR2601988

[3]    Bramson, M., Lu, Y., and Prabhakar, B. (2010). Randomized load balancing with general service time distributions. In Proceedings of the ACM SIGMETRICS 2010. New York, NY, USA, 275–286.

[4]    Deimling, K. (1977). Ordinary Differential Equations in Banach Spaces. Vol. 96. Springer. MR0463601

[5]    Ganesh, A., Lilienthal, S., Manjunath, D., Proutiere, A., and Simatos, F. (2010). Load balancing via random local search in closed and open systems. SIGMETRICS Perform. Eval. Rev. 38, 287–298.

[6]    Graham, C. (2000). Chaoticity on path space for a queueing network with selection of the shortest queue among several. J. Appl. Probab. 37, 198–211. MR1761670

[7]    Hassin, R. and Haviv, M. (1994). Equilibrium strategies and the value of informaiton in a two line queueing system with threshold jockeying. Commun. Statist. Stochastic Models 10(2), 415–435. MR1268559

[8]    Hassin, R. and Haviv, M. (2003). To queue or not to queue: equilibrium behavior in queueing systems. International series in Operations Research and Management Science, Springer. MR2006433

[9]    Hassin, R. and Roet-Green, R. Equilibrium in a two dimensional queueing game: When inspecting the queue is costly. preprint (Dec. 2012), available at http://www.math.tau.ac.il/\textasciitildehassin/ricky.pdf.

[10]    Huang, M., Caines, P., and Malhame, R. (2007). Large-population cost-coupled LQG problems with nonuniform agents: Individual-mass behavior and decentralized ϵ-Nash equilibria. IEEE Transactions on Automatic Control 52, 9 (Sept.), 1560–1571. MR2352434

[11]    Kingman, J. (1966). Two similar queues in parallel. Annals of Mathematical Statistics 32, 1314–1323. MR0144394

[12]    Lasry, J. M. and Lions, P. L. (2007). Mean field games. Japanese Journal of Mathematics, 229–260. MR2295621

[13]    Luczak, M. and McDiarmid, C. (2006). On the maximum queue length in the supermarket model. Ann. Probab. 34, 493–527. MR2223949

[14]    Mitzenmacher, M. (1996). The power of two choices in randomized load balancing. Ph.D. thesis, Univ. of California, Berkeley. MR2695522

[15]    Mitzenmacher, M. (2001). The power of two choices in randomized load balancing. IEEE Trans. on Parallel and Distributed Systems 12:10, 1094–1104.

[16]    Sznitman, A. (1991). Topics in propagation of chaos. In Springer Verlag Lecture Notes in Mathematics 1464, P. Hennequin, Ed. Springer-Verlag, 165–251. MR1108185

[17]    Tsitsiklis, J. N. and Xu, K. (2011). On the power of (even a little) centralization in distributed processing. SIGMETRICS Perform. Eval. Rev. 39, 121–132.

[18]    Tsitsiklis, J. N. and Xu, K. (2012). On the power of (even a little) resource pooling. Stochastic Systems 2, 1–66. MR2960735

[19]    Turner, S. (1998). The effect of increasing routing choice on resource pooling. Prob. Eng. Inf. Sci. 12, 109–123. MR1492143

[20]    Vvedenskaya, N. D., Dobrushin, R. L., and Karpelevich, F. I. (1996). Queueing system with selection of the shortest of two queues: An asymptotic approach. Prob. Inf. Trans 32, 15–27. MR1384927

Home | Articles | Past volumes | About | Login | Notify | Contact | Search

Stochastic Systems. ISSN: 1946-5238