Dynamic Matching with Postallocation Service and Its Application to Refugee Resettlement

• 成果类型: Article; Early Access
• 署名作者: Bansak, Kirk; Lee, Soonbong; Manshadi, Vahideh; Niazadeh, Rad; Paulson, Elisabeth
• 署名单位: University of California System; University of California Berkeley; Yale University; University of Chicago; Harvard University
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2024.07817
• 发表日期: 2026
• 关键词: refugee matching; postallocation service; balanced matching; distribution-free algorithms; online learning; Online allocation

摘要

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.