Dynamic Matching with Postallocation Service and Its Application to Refugee Resettlement

Motivated by our collaboration with a major refugee resettlement agency in the United States, we study a dynamic matching problem where each new arrival (a refugee case) must be matched immediately and irrevocably to one of the static resources (a location with a fixed annual quota). In addition to consuming the static resource, each case requires postallocation service from a server, such as a translator. Given the time-consuming nature of service, a server may not be available at a given time, thus we refer to it as a dynamic resource. Upon matching, the case will wait to avail service in a first-come-first-serve manner. Bursty matching to a location may result in undesirable congestion at its corresponding server. Consequently, the central planner (the agency) faces a dynamic matching problem with an objective that combines the matching reward (captured by pair-specific employment outcomes) with the cost for congestion for dynamic resources and overallocation for the static ones. Motivated by the observed fluctuations in the composition of refugee pools across the years, we design algorithms that do not rely on distributional knowledge constructed based on past years’ data. To that end, we develop learning-based algorithms that are asymptotically optimal in certain regimes, easy to interpret, and computationally fast. Our design is based on learning the dual variables of the underlying optimization problem; however, the main challenge lies in the time-varying nature of the dual variables associated with dynamic resources. To overcome this challenge, our theoretical development brings together techniques from Lyapunov analysis, adversarial online learning, and stochastic optimization. On the application side, when tested on real data from our partner agency and incorporating practical considerations, our method outperforms existing ones, making it a viable candidate for replacing the current practice upon experimentation.

This paper was accepted by Martin Bichler, market design, platform, and demand analytics.

Funding: This work was supported by the Stanford Impact Lab [Stage 2 Grant], Google.org [AI for Social Good Grant TF2111-103726], the Charles Koch Foundation, and the Stanford Institute for Human-Centered Artificial Intelligence [Hoffman-Yee Research Grant].

Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2024.07817.