Feature-Based Dynamic Matching
研究按需服务平台中基于高维特征的动态双边匹配问题，提出前瞻性算法SOAR，平衡当前匹配质量与未来供给，证明其接近最优遗憾界。
SOAR ing to Optimality: Smarter Matching Algorithms for On-Demand Platforms In “Feature-Based Dynamic Matching,” Y. Chen, Y. Kanoria, A. Kumar, and W. Zhang study dynamic two-sided matching where both customers and service providers are characterized by high-dimensional feature vectors, motivated by platforms like on-demand home services. A key finding is that myopic greedy policies—which match each customer to the best available provider—can be highly suboptimal. The authors introduce SOAR (simulate-optimize-assign-repeat), a forward-looking algorithm that balances immediate match quality against preserving valuable supply for future arrivals. Through a novel analytical framework connecting dynamic matching to empirical optimal transport, they prove SOAR achieves near-optimal regret scaling under various distributional assumptions, establishing fundamental performance limits for feature-based matching problems and as a by-product resolve an open problem from prior work on dynamic spatial matching.