Publications

The Cost of Impatience in Dynamic Matching: Scaling Laws and Operating Regimes

Angela Kohlenberg and Itai Gurvich

Management Science, forthcoming

[paper] [slides]

We study matching queues with abandonment. The simplest of these is the two-sided queue with servers on one side and customers on the other, both arriving dynamically over time and abandoning if not matched by the time their patience elapses. We identify non-asymptotic and universal scaling laws for the matching loss due to abandonment, which we refer to as the “cost-of-impatience.” The scaling laws characterize the way in which this cost depends on the arrival rates and the (possibly different) mean patience of servers and customers.

Our characterization reveals four operating regimes identified by an operational measure of patience that brings together mean patience and utilization. The four regimes subsume the regimes that arise in asymptotic (heavy-traffic) approximations. The scaling laws, specialized to each regime, reveal the fundamental structure of the cost-of-impatience and show that its order-of-magnitude is fully determined by (i) a “winner-take-all” competition between customer impatience and utilization, and (ii) the ability to accumulate inventory on the server side. Practically important is that when servers are impatient, the cost-of-impatience is, up to an order-of-magnitude, given by an insightful expression where only the minimum of the two patience rates appears.

Considering the trade-off between abandonment and capacity costs, we characterize the scaling of the optimal safety capacity as a function of costs, arrival rates, and patience parameters. We prove that the ability to hold inventory of servers means that the optimal safety capacity grows logarithmically in abandonment cost and, in turn, slower than the square-root growth in the single-sided queue.

Working Papers

Quality Versus Quantity in Dynamic Matching with Impatient Agents

Angela Kohlenberg

Submitted April 2024

[paper]

We study the trade-off between match quality and quantity in dynamic matching with impatient agents. In these matching markets, delaying matches may allow for better options to become available as more agents arrive, but can also lead to lost matches as agents depart. Matching decisions must balance the competing objectives of higher-quality matches and a greater number of matches.

We consider a two-sided matching market with impatient, heterogeneous agents and matches that are either high-quality (high reward) or low-quality (low reward). We show that the optimal balance between match quality and quantity is determined by the amount of waiting agents (Inventory Imbalance) and the “cost” of waiting (Reward-Loss Ratio) on each side of the market. A matching market operates in one of four regimes based on informative expressions of the Inventory Imbalance and/or Reward-Loss Ratio.

When excess inventory cannot accumulate on the short side of the market, the market is in either the Quantity-Driven, Quality-Driven, or Flexible regime, based only on the mean patience of each side: either a greedy policy (Quantity-Driven and Flexible) or dedicated policy that only performs high-quality matches (Quality-Driven) is near-optimal. When the Inventory Imbalance is large relative to the Reward-Loss Ratio, the market is the Quantity-Driven regime and a greedy policy is near-optimal. When the Inventory Imbalance is very small relative to the Reward-Loss Ratio, the market is in the Quality-Driven regime and a dedicated policy is near-optimal. Otherwise, the market is the Balanced regime and low-quality matches should only be performed when there is enough inventory on the short side.

Instructor

• OM 502, Operations Management, MBA elective, University of Alberta, Spring 2020 and Summer 2018 [syllabus]. Mean Overall Instructor (2020): 4.5/5.0 (32 students).
• OM 411, Business Process Management, undergraduate elective, University of Alberta, Winter 2020 [syllabus] (course evaluation cancelled due to Covid).
• MGTS 352, Operations Management, undergraduate core, Macewan University, Winter 2020 (course evaluation cancelled due to Covid). 
• FNCE 113, Introduction to Quantitative Decision Making, undergraduate core, Macewan University, Winter 2020 and Fall 2018 (2020 course evaluation cancelled due to Covid). Mean Overall Instructor (2018): 4.6/5.0 (36 students). 

Lab instructor and manager

• MGTSC 501, Data Analysis and Decision Making, MBA core, University of Alberta, Fall 2018 and Fall 2017 [syllabus]. Mean Overall Instructor (2018): 4.6/5.0 (121 students).

Teaching Assistant

• OPNS 912, Service Management and Analytics, MBA elective, Northwestern University, Winter 2024 and Winter 2023.
• OPNS 450, Decision Models and Prescriptive Analytics, MBA elective, Northwestern University, Spring 2023, Winter 2023, Summer 2022, Winter 2022.
• OPNS 430, Operations Management, MBA core, Northwestern University, Fall 2021.
• MGTSC 405, Forecasting, undergraduate elective, University of Alberta, Winter 2018.
• MGTSC 820, Data Analysis and Modeling, Executive MBA core, University of Alberta, Winter 2018.

The Cost of Impatience in Dynamic Matching [slides]

• INFORMS Annual Meeting 2023, Phoenix, USA, October 2023.
• Applied Probability Society (APS) Conference, Nancy, France, June 2023.
• INFORMS Annual Meeting 2022, Indianapolis, USA, October 2022.