{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T10:36:32Z","timestamp":1774002992929,"version":"3.50.1"},"reference-count":62,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Operations Research"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:p>SOAR ing to Optimality: Smarter Matching Algorithms for On-Demand Platforms<\/jats:p>\n                  <jats:p>In \u201cFeature-Based Dynamic Matching,\u201d 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\u2014which match each customer to the best available provider\u2014can 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.<\/jats:p>","DOI":"10.1287\/opre.2024.0730","type":"journal-article","created":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T17:24:31Z","timestamp":1763486671000},"page":"788-803","source":"Crossref","is-referenced-by-count":0,"title":["Feature-Based Dynamic Matching"],"prefix":"10.1287","volume":"74","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9638-2100","authenticated-orcid":false,"given":"Yilun","family":"Chen","sequence":"first","affiliation":[{"name":"School of Data Science, School of Management and Economics, The Chinese University of Hong Kong, Shenzhen, Shenzhen, Guangdong 518172, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7221-357X","authenticated-orcid":false,"given":"Yash","family":"Kanoria","sequence":"additional","affiliation":[{"name":"Graduate School of Business, Columbia University, New York, New York 10027"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3418-2514","authenticated-orcid":false,"given":"Akshit","family":"Kumar","sequence":"additional","affiliation":[{"name":"School of Management, Yale University, New Haven, Connecticut 06511"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-1965-4335","authenticated-orcid":false,"given":"Wenxin","family":"Zhang","sequence":"additional","affiliation":[{"name":"Graduate School of Business, Columbia University, New York, New York 10027"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29659-3"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2021.0534"},{"key":"B3","unstructured":"Akbarpour M, Alimohammadi Y, Li S, Saberi A (2021) The value of excess supply in spatial matching markets. Preprint, submitted April 7, https:\/\/arxiv.org\/abs\/2104.03219."},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.19.1.46"},{"key":"B5","unstructured":"Aouad A, Ma W (2022) A nonparametric framework for online stochastic matching with correlated arrivals. Preprint, submitted August 3, https:\/\/arxiv.org\/abs\/2208.02229."},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2022.4464"},{"key":"B7","doi-asserted-by":"crossref","unstructured":"Aouad A, Sarita\u00e7 \u00d6 (2022) Dynamic stochastic matching under limited time.\n                      Oper. Res.\n                      70(4):2349\u20132383.","DOI":"10.1287\/opre.2022.2293"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2022.2327"},{"key":"B9","doi-asserted-by":"crossref","unstructured":"Ashlagi I, Burq M, Dutta C, Jaillet P, Saberi A, Sholley C (2022b) Edge weighted online windowed matching.\n                      Math. Oper. Res.\n                      48(2):999\u20131016.","DOI":"10.1287\/moor.2022.1289"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2023.4769"},{"key":"B11","unstructured":"Balkanksi E, Faenza Y, Perivier N (2022) The power of greedy for online minimum cost matching on the line. Preprint, submitted October 6, https:\/\/arxiv.org\/abs\/2210.03166."},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2023.2441"},{"key":"B13","doi-asserted-by":"crossref","unstructured":"Balseiro S, Kroer C, Kumar R (2023b) Online resource allocation under horizon uncertainty.\n                      Abstr.\n                      Proc. ACM SIGMETRICS Internat. Conf. Measurement Modeling Comput. Systems\n                      (Association for Computing Machinery, New York), 63\u201364.","DOI":"10.1145\/3578338.3593559"},{"key":"B33","doi-asserted-by":"crossref","unstructured":"Banerjee S, Freund D (2024) Good prophets know when the end is near.\n                      Management Sci.\n                      71(6):4877\u20134894.","DOI":"10.1287\/mnsc.2023.04307"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2021.2165"},{"key":"B15","volume-title":"Dynamic Programming and Optimal Control: Volume I","volume":"4","author":"Bertsekas D","year":"2012"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1287\/msom.2014.0489"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2021.2112"},{"key":"B18","doi-asserted-by":"crossref","unstructured":"Besbes O, Kanoria Y, Kumar A (2024) Dynamic resource allocation: Algorithmic design principles and spectrum of achievable performances.\n                      Oper. Res.\n                      73(3):1273\u20131288.","DOI":"10.1287\/opre.2022.0504"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1287\/msom.5.3.203.16031"},{"key":"B20","doi-asserted-by":"crossref","unstructured":"Braverman M, Derakhshan M, Lovett AM (2022) Max-weight online stochastic matching: Improved approximations against the online benchmark. Preprint, submitted June 2, https:\/\/arxiv.org\/abs\/2206.01270.","DOI":"10.1145\/3490486.3538315"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160440402"},{"key":"B22","unstructured":"Brubach B, Sankararaman KA, Srinivasan A, Xu P (2016) New algorithms, better bounds, and a novel model for online stochastic matching.\n                      Proc. 24th Annual Eur. Sympos. Algorithms\n                      , Leibniz International Proceedings in Informatics (LIPIcs), vol. 57 (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern, Germany), 24:1\u201324:16."},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2019.3365"},{"key":"B24","volume-title":"Model Predictive Control","author":"Camacho EF","year":"2013"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.90.012118"},{"key":"B26","doi-asserted-by":"crossref","unstructured":"Chen L, Kyng R, Liu YP, Peng R, Gutenberg MP, Sachdeva S (2022) Maximum flow and minimum-cost flow in almost-linear time. Preprint, submitted March 1, https:\/\/arxiv.org\/abs\/2203.00671.","DOI":"10.1109\/FOCS54457.2022.00064"},{"key":"B27","doi-asserted-by":"crossref","unstructured":"Delong S, Farhadi A, Niazadeh R, Sivan B (2023) Online bipartite matching with reusable resources.\n                      Math. Oper. Res.\n                      49(3):1825\u20131854.","DOI":"10.1287\/moor.2022.0242"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2021.4044"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.7.349"},{"key":"B30","doi-asserted-by":"crossref","unstructured":"Ezra T, Feldman M, Gravin N, Tang ZG (2020) Online stochastic max-weight matching: Prophet inequality for vertex and edge arrival models.\n                      Proc. 21st ACM Conf. Econom. Comput\n                      .\n                      (EC '20)\n                      (Association for Computing Machinery, New York), 769\u2013787.","DOI":"10.1145\/3391403.3399513"},{"key":"B31","doi-asserted-by":"crossref","unstructured":"Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1\/e.\n                      Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci\n                      . (IEEE Computer Society, Washington, DC), 117\u2013126.","DOI":"10.1109\/FOCS.2009.72"},{"key":"B32","doi-asserted-by":"crossref","unstructured":"Feng Y, Niazadeh R (2024) Batching and optimal multi-stage bipartite allocations.\n                      Management Sci.\n                      71(5):4108\u20134130.","DOI":"10.1287\/mnsc.2022.03698"},{"key":"B34","unstructured":"Gupta A, Guruganesh G, Peng B, Wajc D (2019) Stochastic online metric matching. Preprint, submitted April 19, https:\/\/arxiv.org\/abs\/1904.09284."},{"key":"B35","doi-asserted-by":"crossref","unstructured":"Haeupler B, Mirrokni VS, Zadimoghaddam M (2011) Online stochastic weighted matching: Improved approximation algorithms. Chen N, Elkind E, Koutsoupias E, eds.\n                      Proc. 7th Internat. Workshop Internet Network Econom\n                      ., Lecture Notes in Computer Science, vol. 7090 (Springer, Berlin, Heidelberg), 170\u2013181.","DOI":"10.1007\/978-3-642-25510-6_15"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1214\/20-AOP1452"},{"key":"B37","doi-asserted-by":"crossref","unstructured":"Immorlica N, Lucier B, Manshadi V, Wei A (2022) Designing approximately optimal search on matching platforms.\n                      Management Sci.\n                      69(8):4609\u20134626.","DOI":"10.1287\/mnsc.2022.4601"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0621"},{"key":"B39","doi-asserted-by":"crossref","unstructured":"Kanoria Y (2025) Dynamic spatial matching.\n                      Ann. Appl. Probab.\n                      35(5):3086\u20133118.","DOI":"10.1214\/25-AAP2154"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2009.263"},{"key":"B41","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1110.0386"},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1007\/s10958-019-04253-6"},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2019.1957"},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.1007\/s00205-005-0362-9"},{"key":"B45","doi-asserted-by":"crossref","unstructured":"Manole T, Niles-Weed J (2024) Sharp convergence rates for empirical optimal transport with smooth costs.\n                      Ann. Appl. Probab.\n                      34(1B):1108\u20131135.","DOI":"10.1214\/23-AAP1986"},{"key":"B46","unstructured":"Manole T, Balakrishnan S, Niles-Weed J, Wasserman L (2021) Plugin estimation of smooth optimal transport maps. Preprint, submitted July 26, https:\/\/arxiv.org\/abs\/2107.12364."},{"key":"B47","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1120.0551"},{"key":"B48","doi-asserted-by":"crossref","unstructured":"Manshadi V, Rodilitz S, Saban D, Suresh A (2025) Online algorithms for matching platforms with multi-channel traffic.\n                      Management Sci.\n                      71(9):7674\u20137691.","DOI":"10.1287\/mnsc.2022.00910"},{"key":"B49","volume-title":"Probabilistic Machine Learning: An Introduction","author":"Murphy KP","year":"2022"},{"key":"B50","doi-asserted-by":"crossref","unstructured":"Niles-Weed J, Rigollet P (2022) Estimation of Wasserstein distances in the spiked transport model.\n                      Bernoulli\n                      28(4):2663\u20132688.","DOI":"10.3150\/21-BEJ1433"},{"key":"B51","doi-asserted-by":"crossref","unstructured":"Papadimitriou C, Pollner T, Saberi A, Wajc D (2023) Online stochastic max-weight bipartite matching: Beyond prophet inequalities.\n                      Math. Oper. Res.\n                      49(3):1607\u20131628.","DOI":"10.1287\/moor.2023.1389"},{"key":"B52","unstructured":"Saberi A, Yang M, Yu SH (2024) Stochastic online metric matching: Adversarial is no harder than stochastic. Preprint, submitted July 20, https:\/\/arxiv.org\/abs\/2407.14785."},{"key":"B53","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2022.4444"},{"key":"B54","unstructured":"Sinclair SR, Frujeri FV, Cheng CA, Marshall L, Barbalho HDO, Li J, Neville J, et al. (2023) Hindsight learning for MDPs with exogenous inputs. Krause A, Brunskill E, Cho K, Engelhardt B, Sabato S, Scarlett J, eds.\n                      Proc. Internat. Conf. Machine Learn.\n                      (PMLR, New York), 31877\u201331914."},{"key":"B55","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1040.0180"},{"key":"B56","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.33.2.207"},{"key":"B57","doi-asserted-by":"publisher","DOI":"10.1007\/b139000"},{"key":"B58","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-022-01856-x"},{"key":"B59","unstructured":"Udwani R (2021) Periodic reranking for online matching of reusable resources. Preprint, submitted October 5, https:\/\/arxiv.org\/abs\/2110.02400."},{"key":"B60","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2020.3624"},{"key":"B61","volume-title":"Optimal Transport: Old and New","volume":"338","author":"Villani C","year":"2008"},{"key":"B62","doi-asserted-by":"publisher","DOI":"10.3150\/18-BEJ1065"}],"container-title":["Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/opre.2024.0730","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T08:11:38Z","timestamp":1773994298000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/opre.2024.0730"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3]]},"references-count":62,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["10.1287\/opre.2024.0730"],"URL":"https:\/\/doi.org\/10.1287\/opre.2024.0730","relation":{},"ISSN":["0030-364X","1526-5463"],"issn-type":[{"value":"0030-364X","type":"print"},{"value":"1526-5463","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3]]}}}