To Wait or Get Late: Strategic and Transitory Queueing Systems

Mon., Oct 22, 2012

2:30 - 3:30 PM

400 Cory Hall (Hughes Room)

2:30 - 3:30 PM

400 Cory Hall (Hughes Room)

In the first part of the talk, we introduce the ``concert arrival game". This new model is introduced to capture the tradeoff in decision-making when users must decide whether to arrive early and wait in a queue, or arrive late but miss out on opportunities (e.g., best seats at a concert). With such decision-making by the users, it is a folly to assume that the arrival process is exogenous, and a well-behaved renewal process. Thus, under the fluid model, we characterize the equilibrium arrival profile and characterize the ``price of anarchy" (PoA), the loss in social welfare due to strategically arriving users. We also give some simple mechanisms to reduce it.

Motivated by the above, in the second part of the talk, we introduce the Delta(i)/GI/1 queue - a new model for transitory queueing systems in which a each user picks their time of arrival from a common distribution such that the arrival process need no longer be one with independent inter-arrival times. We derive the fluid and diffusion process limits for such a model. We find that the limiting queue length process is a reflection of a combination of a Brownian motion and a Brownian bridge. The convergence is established in the M1 topology, and we also show that it is not possible to it in the stronger J1 topology. Such models allow us to study transitory queueing systems which are not very amenable to extant techniques in queueing theory.

Bio: Rahul Jain is the K. C. Dahlberg Early Career Chair and an Assistant Professor in the EE & ISE Departments at the University of Southern California, Los Angeles, CA. He received his B.Tech from IIT Kanpur, and an MA in Statistics and a PhD in EECS from the University of California, Berkeley. Prior to joining USC in Fall 2008, he was at the IBM T J Watson Research Center, Yorktown Heights, NY. He is a recipient of the NSF CAREER award in 2010, the ONR Young Investigator award in 2012, an IBM Faculty award in 2010, the James H. Zumberge Faculty Research and Innovation Award in 2009 and a Best paper award at The ValueTools Conference 2009. His interests span game theory and network economics, queueing theory, stochastic models, optimization and learning with applications to communication networks and power systems.

Motivated by the above, in the second part of the talk, we introduce the Delta(i)/GI/1 queue - a new model for transitory queueing systems in which a each user picks their time of arrival from a common distribution such that the arrival process need no longer be one with independent inter-arrival times. We derive the fluid and diffusion process limits for such a model. We find that the limiting queue length process is a reflection of a combination of a Brownian motion and a Brownian bridge. The convergence is established in the M1 topology, and we also show that it is not possible to it in the stronger J1 topology. Such models allow us to study transitory queueing systems which are not very amenable to extant techniques in queueing theory.

Bio: Rahul Jain is the K. C. Dahlberg Early Career Chair and an Assistant Professor in the EE & ISE Departments at the University of Southern California, Los Angeles, CA. He received his B.Tech from IIT Kanpur, and an MA in Statistics and a PhD in EECS from the University of California, Berkeley. Prior to joining USC in Fall 2008, he was at the IBM T J Watson Research Center, Yorktown Heights, NY. He is a recipient of the NSF CAREER award in 2010, the ONR Young Investigator award in 2012, an IBM Faculty award in 2010, the James H. Zumberge Faculty Research and Innovation Award in 2009 and a Best paper award at The ValueTools Conference 2009. His interests span game theory and network economics, queueing theory, stochastic models, optimization and learning with applications to communication networks and power systems.

UC Berkeley Networking

Ashwin Pananjady and Orhan Ocal

Last Modification Date: Wednesday, February 10, 2016

Ashwin Pananjady and Orhan Ocal

Last Modification Date: Wednesday, February 10, 2016