The supermarket game

DOI10.1214/12-SSY093MaRDI QIDQ5168871zbMATH OpenFDO

Authors Jiaming Xu, Bruce Hajek

Publication date 21 July 2014

Full work available at URL https://arxiv.org/abs/1202.2089

zbMATH Keywords

mean field modelNash equilibriumqueueingsupermarket game

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Queues and service in operations research (90B22) Other game-theoretic models (91A40)

Abstract: A supermarket game is considered with $N$ FCFS queues with unit exponential service rate and global Poisson arrival rate $Nlambda$. 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 $Noinfty$ 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 $lambd{a}^{2}le1/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$.

Recommendations

• The supermarket model with bounded queue lengths in equilibrium
• Asymptotic distributions and chaos for the supermarket model
• The concert queueing game: to wait or to be late
• On a doubly dynamically controlled supermarket model with impatient customers
• scientific article; zbMATH DE number 3882172

Cites work

• A particle system in interaction with a rapidly varying environment: mean field limits and applications
• Chaoticity on path space for a queueing network with selection of the shortest queue among several
• Equilibrium strategies and the value of information in a two line queueing system with threshold jockeying
• scientific article; zbMATH DE number 4211245 (Why is no real title available?)
• Large-Population Cost-Coupled LQG Problems With Nonuniform Agents: Individual-Mass Behavior and Decentralized \varepsilon-Nash Equilibria
• Load balancing via random local search in closed and open systems
• Mean field games
• Occupancy Distributions of Homogeneous Queueing Systems Under Opportunistic Scheduling
• On the maximum queue length in the supermarket model
• On the power of (even a little) resource pooling
• Ordinary differential equations in Banach spaces
• Queueing system with selection of the shortest of two queues: An asymptotic approach
• The Effect of Increasing Routing Choice on Resource Pooling
• To queue or not to queue: equilibrium behavior in queueing systems.
• Two Similar Queues in Parallel

Cited in

(10)

• Strategic customer behavior in a queueing system with a loss subsystem
• Information heterogeneity in a retrial queue: throughput and social welfare maximization
• Choosing among heterogeneous server clouds
• An overview for Markov decision processes in queues and networks
• The Impact of Inspection Cost on Equilibrium, Revenue, and Social Welfare in a Single-Server Queue
• Mean Field Equilibrium: Uniqueness, Existence, and Comparative Statics
• Stability of parallel server systems
• Mean field equilibria for resource competition in spatial settings
• Approximations for a queueing game model with join-the-shortest-queue strategy
• Sequential decomposition of discrete-time mean-field games

This page was built for publication: The supermarket game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5168871)