A supermarket game (joint work with Jiaming Xu)is considered with N FCFS exponential server queues. 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. The game is motivated by the study of distributed load-balancing systems, such as in cloud computing of wireless access. We study the supermarket game in a mean field model that corresponds to the limit as N converges to infinity. It is shown that there always exists a Nash equilibrium for arrival rate per queue less than one, and the Nash equilibrium is unique for homogeneous waiting cost for arrival rate less than 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 limit, but not always for finite N. (Full paper at http://arxiv.org/abs/1202.2089.)
Bruce Hajek is a Professor in the Department of Electrical and Computer Engineering and in the Coordinated Science Laboratory at theUniversity of Illinois at Urbana-Champaign, where he has been on the facultysince 1979. His research interests include communication and computernetworks, stochastic systems, combinatorial and nonlinearoptimization, and information theory. He served as Associate Editorfor Communication Networks and Computer Networks for the IEEE Transactionson Information Theory, as Editor-in-Chief of the sameTransactions, and as President of the IEEE InformationTheory Society. He is a member of the US National Academy of Engineeringand he was a winner of the 1973 USA Mathematical Olympiad. He received theEckman Award of the American Automatic Control Council, an NSF PresidentialYoung Investigator Award, an Outstanding Paper Award from theIEEE Control Systems Society, and the IEEE Kobayashi Computer Communications Award.
