Game of arrivals at a two queue network with heterogeneous route choice

Agniv Bandyopadhyay
Varun Ramanathan
Friday, 23 Jun 2023, 16:00 to 17:00
Considerable research has focused on modelling customer arrival time to queues as games where customers are strategic and non-cooperative in selecting their arrivals and their costs are a function of the queueing delays as well as service completion times. Customers are typically modelled as fluid or non-atomic particles and services are assumed to have a deterministic rate. Most applications involving strategic customers who think about when to join a queuing system fit this setting including customers arriving at a service provider(s), traffic networks and so on. Most of the literature has focused on a single queue. Some works consider tandem and more general queuing networks where customers have homogeneous routes. This homogeneity leads to substantial analytical simplification. However, there are many practical settings where more than one queue is involved and customers have different routes. Motivated by this, we consider a queuing network that opens at a specified time, where customers are non-atomic and belong to different classes. Each class has its own route, and as is typical in the literature, the costs are a linear function of waiting and service completion time. We restrict ourselves to a two class, two queue network: this simplification is well motivated as the diversity in solution structure as a function of problem parameters is substantial even in this simple setting (e.g., a specific routing structure involves eight different regions), suggesting a combinatorial blow up as the number of queues, routes and customer classes increase. We identify the unique Nash equilibrium customer arrival profile when the customer linear cost preferences are different. When customer cost preferences match, under certain parametric settings, the equilibrium arrival profiles may not be unique and may lie in a convex set. We further make a surprising observation that in some parametric settings, customers in one class may arrive in disjoint intervals, although the union of the arrival times across the two classes is always an interval. Further, the two classes may arrive in contiguous intervals or in overlapping intervals, and at varying rates within an interval, depending upon the problem parameters. In this talk, we will cover the existing works on single queue setting and tandem networks. Following that, if time permits, we will go through the analysis of the two queue settings.
This talk will be based on joint work with Sandeep Juneja.