Feature-Based Dynamic Matching

Motivated by matching platforms that match agents in a centralized manner, we study dynamic two-sided matching in a setting where both customers (demand) and service providers (supply) are heterogeneous and the pool of service providers is limited. We model heterogeneity on the two sides of the market by demand weight vectors drawn independently and identically distributed (i.i.d.) from some distribution and supply feature vectors drawn i.i.d. from a (possibly) different distribution. The matching of a demand-supply pair generates a matching value that depends on their weight and feature vectors. We adopt a notion of regret, specifically the additive loss relative to the value (per match) achievable in the limiting hindsight optimum as our performance metric for matching policies. Simple myopic policies suffer nonvanishing $\mathrm{\Omega }(1)$ regret in large markets. We propose a forward-looking supply-aware policy dubbed simulate-optimize-assign-repeat (SOAR) that balances between producing high match value for the current match and preserving valuable supply for future customers. We prove that SOAR achieves the optimal regret scaling under different assumptions on the demand and supply distributions. En route to proving our guarantees, we develop a novel framework for analyzing the performance of our SOAR policy that may be of broader interest. As a corollary of our techniques, we also resolve an open problem posed previously.

Funding: This work was supported by the Division of Civil, Mechanical and Manufacturing Innovation [Grant CMMI-1653477] and the National Natural Science Foundation of China [Grants NSFC-72394361 and NSFC-72501250].

Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2024.0730.