Data-Driven Matching for Impatient and Heterogeneous Demand and Supply

This paper develops a framework that integrates finite-sample statistical learning with queueing asymptotic analysis to design matching policies. The stochastic matching model we consider assumes heterogeneous demand (customers) and heterogeneous supply (workers) arrive randomly over time, each with a randomly sampled patience time, and are lost (renege) if forced to wait longer than that time to be matched. Because the interarrival and patience-time distributions are unknown, matching decisions must be made based on historical (offline) data. We leverage asymptotic analysis to formulate a deterministic, data-driven (fluid) matching problem (DDMP) that approximates the original stochastic matching problem. We establish finite-sample statistical guarantees on the objective value gap between the DDMP solution and the ground-truth matching problem solution, which requires a novel uniform error bound involving the patience-time quantile function. We show that a discrete-review, estimate-then-match-type policy is $ϵ-$asymptotically optimal with high probability as arrival rates grow large.

Funding: We acknowledge the Postdoctoral Principal Researcher Funding provided by The University of Chicago Booth School of Business. This work was partially supported by NSFC (National Natural Science Foundation of China) [Grant 72571122], and The Chinese University of Hong Kong’s Improvement on Competitiveness in Hiring New Faculties Funding Scheme.

Supplemental Material: The online appendix is available at https://doi.org/10.1287/moor.2025.1115.