Tata Institute of Fundamental Research

The Concert Queueing Game with a Finite Homogeneous Population

Speaker: Sandeep K. Juneja Tata Institute of Fundamental Research School of Technology and Computer Science Homi Bhabha Roa
Date: Monday, 4 Jul 2011 (all day)
Venue: A-212 (STCS Seminar Room)

(Scan to add to calendar)
Abstract:  We consider the non-cooperative choice of arrival times by individual users, or customers, to a service system that opens at a given time, and where users queue up and are served in order of arrival. Each user wishes to obtain service as early as possible, while minimizing the expected wait in the queue. This problem was recently studied within a simplified fluid model. Here we address the non-asymptotic stochastic system, assuming a finite (possibly random) number of homogeneous users, exponential service times, and linear cost functions. In this setting we show that there exists a unique Nash equilibrium, which is symmetric across users, and characterize the equilibrium arrival-time distribution of each user in terms of a corresponding set of differential equations. We further establish convergence of the Nash equilibrium solution to that of the associated fluid model as the number of users increases to infinity. We also show that the price of anarchy in our system exceeds 2, but approaches this value for a large population size.