Technical Perspective: Improving Refugees’ Integration with Online Resource Allocation

Trade-offs between consuming resources now and waiting for a potentially greater reward later are common in both life and algorithm design. Do we accept an exploding job offer now, or hold out hope for a better one? Should we buy the next house we see or keep looking? Making decisions like these in the face of uncertainty has given rise to a wide range of problems in algorithm design.

In computer science and operations research, this trade-off appears in a class of algorithmic problems sometimes referred to as online resource allocation problems. These often involve a decision-maker who controls a set of resources and observes sequential requests. Each request includes a set of compatible resources that can be used to fulfill the request, and a reward that depends on how the request is served. The decision-maker’s goal is to maximize rewards from served requests without exceeding the available resources. This is difficult when future requests are unknown.

Naively, one might want to serve each request in a way that maximizes each request’s rewards as it arrives. The problem with such a greedy approach is that one quickly exhausts valuable resources, just like accepting every job offer may quickly exhaust one’s professional network. This causes later requests to be poorly served, and often results in a poor outcome overall. Thus, different algorithmic approaches have been proposed, over decades of research, to make more efficient decisions about serving requests without depleting resources too quickly.

In the following paper, the authors apply one such approach to a new and important area: refugee resettlement. Refugee resettlement agencies, such as the Hebrew Immigrant Aid Society (HIAS), assign refugees arriving in a host country to local affiliates that have limited annual capacities. In making these decisions, they aim for refugees to start participating in local communities. A key metric for success, carefully monitored by the U.S. Refugee Admissions Program, is a refugee’s ability to find employment within the first 90 days of arrival. By introducing concepts from online resource allocation, the authors can improve this metric for HIAS by around 10%, a significant improvement for a vulnerable population.

Previous work by Bansak et al.¹ developed machine learning (ML) models, based on known characteristics such as age, education, and country of origin, to predict a refugee’s employability score at a given affiliate, that is, a refugee’s probability of employment if assigned to the affiliate. The authors also showed there is potential value in such ML models: if one optimally assigned all refugees simultaneously to affiliates, with the objective of maximizing their combined employability scores, one would vastly improve upon the status quo. But refugees do not arrive simultaneously; instead, they arrive in stages, with significant uncertainty about future arrivals. This leaves it open how to operationalize such a ML model. For example, if HIAS just “greedily” assigned each refugee to the local affiliate where they are most likely to find employment, there would not be much improvement over a non-quantitative approach. Instead, to achieve significant improvements in refugee employability, one needs to carefully balance resource use today against maintaining capacity for future refugees.

The accompanying paper does just that: it introduces concepts from online resource allocation to realize the benefits of the ML models to predict refugee employability. As part of their work, the authors developed a decision-aid that allows HIAS staff to see both the predicted employability score for a given refugee at a given affiliate, and an adjusted score that considers the opportunity cost of lost capacity at the affiliate (the final resettlement decision remains with HIAS staff that may have information outside the purview of the ML model and the optimization).

The societal impact of this work makes it an exciting new development in algorithm design. This excitement is particularly evident for two reasons: First, the application addresses a critical societal issue where there is a clear need for improved outcomes. Second, the results demonstrate the potential for applying algorithms to improve real-world outcomes for vulnerable populations.

The excitement around this work has also been reflected in recent related studies aimed at improving the refugee resettlement process. Bansak and Paulson² developed a similar algorithm that incorporates temporal load balancing among affiliates to prevent overwhelming them with too many refugees at once. In a more recent study, Paulson and colleagues,³ including myself, introduced group-fairness to the optimization to ensure subgroups of refugees are not disproportionately disadvantaged for the benefits of the overall refugee population. But this paper does not only encourage further research in refugee resettlement. More importantly, it serves as an inspiration for algorithm designers to collaborate with practitioners on problems of societal importance.