TY - GEN

T1 - The supermarket game

AU - Xu, Jiaming

AU - Hajek, Bruce

PY - 2012

Y1 - 2012

N2 - 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 e-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 for λ 2 ≤ 1/2. Furthermore, we find that the action of sampling more queues by some customers has a positive externality on the other customers.

AB - 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 e-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 for λ 2 ≤ 1/2. Furthermore, we find that the action of sampling more queues by some customers has a positive externality on the other customers.

UR - http://www.scopus.com/inward/record.url?scp=84867527935&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867527935&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2012.6283969

DO - 10.1109/ISIT.2012.6283969

M3 - Conference contribution

AN - SCOPUS:84867527935

SN - 9781467325790

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2511

EP - 2515

BT - 2012 IEEE International Symposium on Information Theory Proceedings, ISIT 2012

T2 - 2012 IEEE International Symposium on Information Theory, ISIT 2012

Y2 - 1 July 2012 through 6 July 2012

ER -