Feature-Based Dynamic Matching

• 成果类型: Article; Early Access
• 署名作者: Chen, Yilun; Kanoria, Yash; Kumar, Akshit; Zhang, Wenxin
• 署名单位: The Chinese University of Hong Kong, Shenzhen; Columbia University; Yale University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2024.0730
• 发表日期: 2025-11-18
• 关键词: Matching markets; dynamic matching; simulation-based policies; Regret Analysis; linear-programming method; factorization; allocation

摘要

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 ohm(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.