Skip to main content

The Supermarket Game

Publication ,  Journal Article
Xu, J; Hajek, B
Published in: Stochastic Systems
December 2013

A supermarket game is considered with N FCFS queues with unit exponential service rate and global Poisson arrival rate Nλ. 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 a product distribution determined by the mean field model and (ii) a Nash equilibrium for the mean field model is an ε-Nash equilibrium for the finite N model with N sufficiently large. It is shown that there always exists a Nash equilibrium for λ < 1 and the Nash equilibrium is unique with homogeneous waiting cost for [Formula: see text]. 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.

Duke Scholars

Published In

Stochastic Systems

DOI

EISSN

1946-5238

ISSN

1946-5238

Publication Date

December 2013

Volume

3

Issue

2

Start / End Page

405 / 441

Publisher

Institute for Operations Research and the Management Sciences (INFORMS)

Related Subject Headings

  • 0899 Other Information and Computing Sciences
  • 0104 Statistics
  • 0102 Applied Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Xu, J., & Hajek, B. (2013). The Supermarket Game. Stochastic Systems, 3(2), 405–441. https://doi.org/10.1287/12-ssy093
Xu, Jiaming, and Bruce Hajek. “The Supermarket Game.” Stochastic Systems 3, no. 2 (December 2013): 405–41. https://doi.org/10.1287/12-ssy093.
Xu J, Hajek B. The Supermarket Game. Stochastic Systems. 2013 Dec;3(2):405–41.
Xu, Jiaming, and Bruce Hajek. “The Supermarket Game.” Stochastic Systems, vol. 3, no. 2, Institute for Operations Research and the Management Sciences (INFORMS), Dec. 2013, pp. 405–41. Crossref, doi:10.1287/12-ssy093.
Xu J, Hajek B. The Supermarket Game. Stochastic Systems. Institute for Operations Research and the Management Sciences (INFORMS); 2013 Dec;3(2):405–441.

Published In

Stochastic Systems

DOI

EISSN

1946-5238

ISSN

1946-5238

Publication Date

December 2013

Volume

3

Issue

2

Start / End Page

405 / 441

Publisher

Institute for Operations Research and the Management Sciences (INFORMS)

Related Subject Headings

  • 0899 Other Information and Computing Sciences
  • 0104 Statistics
  • 0102 Applied Mathematics