TIFR Cafeteria and Related Queues - A Game of Arrivals

Sandeep K. Juneja School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Roa
Wednesday, 11 Nov 2009 (all day)
In this talk, we introduce the `cafeteria or the banquet hall queuing problem' strongly motivated by speaker's experience of waiting in the TIFR cafeteria queue: Fixed but a large number of users arrive into a queue which provides service starting at a fixed time, say, 12:15 pm. Users may (and some do) arrive before this time and queue up. Their cost is a function of their waiting time in the queue and time at which service is received. We analyze this system in an asymptotic regime and develop fluid limit for the resultant queuing system. The limiting system may be modeled as a non-atomic game for which we determine the Nash-Wardrop equilibrium arrival strategy under a variety of assumptions on the cost structure. Furthermore, we note that the `price of anarchy' of this system equals 2 under linearity and homogeneity assumptions. We discuss some potential ways to limit this