Paper Dynamic Matching with Post-allocation Service and its Application to Refugee Resettlement

Motivated by a collaboration with a major refugee resettlement agency in the United States, this study addresses a dynamic matching problem in which arriving refugee cases must be assigned immediately and irrevocably to resettlement locations, each subject to a fixed annual capacity. Beyond consuming this static capacity, each case also requires ongoing services, such as translation, from shared service providers whose availability fluctuates over time, referred to here as dynamic resources. Assignments are served on a first-come-first-served basis, meaning that concentrated placements at a single location can generate costly congestion. The central planning problem therefore balances multiple competing objectives: maximizing match quality, measured by employment outcomes specific to each case-location pairing, while managing congestion at dynamic resources and avoiding over-allocation of static capacities. A key practical consideration is that the composition of incoming refugee populations varies substantially across years, making distributional assumptions unreliable. The proposed framework therefore forgoes such assumptions in favor of learning-based algorithms that adapt to observed data. The algorithms are designed to learn the dual variables of the underlying optimization problem online. A primary technical challenge arises from the time-varying nature of the dual variables associated with dynamic resources. The theoretical framework integrates tools from Lyapunov analysis, adversarial online learning, and stochastic optimization to establish asymptotic optimality in relevant regimes. The resulting algorithms are computationally efficient and readily interpretable. Empirical evaluation on real data from the partner agency demonstrates that the proposed approach outperforms existing methods across practically relevant metrics, positioning it as a strong candidate for deployment in operational resettlement practice.

Get the Paper