Feature-Based Dynamic Matching
Yilun Chen, Yash Kanoria, Akshit Kumar, Wenxin Zhang · Operations Research · 2025
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.