Designing Service Menus for Bipartite Queueing Systems

Varun Gupta
Sandeep K Juneja
Tuesday, 18 Jan 2022, 18:30 to 19:30
Via Zoom
We look at the problem of designing a matching system with queues in an environment with multiple types of customers and multiple classes of servers. Customers arrive to the system seeking service by one of many available servers, and the reward or value obtained by a customer depends on both the customer's type as well as the class of server which services the customer. The goal of the system designer is to design a service mechanism that will match customers to servers and balance the two (usually) competing objectives: (1) maximize customers' average service reward and (2) minimize customers' average waiting time delay. We restrict ourselves to a special class of mechanisms in which the system designer offers a static menu of service classes and customers choose which one of them to join upon arrival. A service class is defined by a single queue served by a specific subset of servers under a First-Come-First-Served (FCFS) service discipline. Customers act as rational self-interested utility maximizing agents when choosing which service class to join. We study the problem under (conventional) heavy traffic conditions, that is, in the limit as the traffic intensity of the system approaches one from below, and provide insights into the design tradeoffs of "good" service menus.
The talk will be based on a work-in-progress with Lisa Hillas and Rene Caldentey, and the following paper with Philipp Afeche and Rene Caldentey (
Bio: Varun Gupta studies stochastic modeling and optimization, applied probability, algorithm design and analysis, and mechanism design. He is particularly interested in modeling and optimization of resource allocation policies for multi-server and distributed systems (e.g., third party logistics, cloud infrastructure, health care) from a queueing theoretic perspective, and learning and control in non-stationary environments.
Gupta holds a PhD in computer science from Carnegie Mellon University. He completed his undergraduate studies in computer science and engineering at the Indian Institute of Technology in Delhi where he was awarded the President's Gold Medal. Outside of academia Varun has spent time in industry at Alcatel-Lucent Bell Laboratories, Microsoft Research, and Google Research.