Dear Deeply Readers,

Welcome to the archives of Refugees Deeply. While we paused regular publication of the site on April 1, 2019, we are happy to serve as an ongoing public resource on refugees and migration. We hope you’ll enjoy the reporting and analysis that was produced by our dedicated community of editors and contributors.

We continue to produce events and special projects while we explore where the on-site journalism goes next. If you’d like to reach us with feedback or ideas for collaboration you can do so at [email protected].

An Algorithm to Alleviate the Refugee Crisis

Matching theory can drastically improve refugee resettlement, argue Will Jones and Alex Teytelboym, who have adapted algorithms used for school choice.

Written by Will Jones and Alex Teytelboym Published on Read time Approx. 5 minutes
About 57,000 refugees and migrants remain stranded in Greece, most in army-built camps on the mainland. Many are awaiting resettlement in other European countries under a delayed program. AP/Thanassis Stavrakis

The authors of the United Nations 1951 Refugee Convention envisioned refugee status as something temporary. Postwar Europe would eventually settle down, they reasoned, and refugees would either go home or integrate in their host countries.

The reality has been more complicated. Around the world millions of refugees are spending decades in this temporary status. Most of them are in very poor countries. The U.N.’s refugee agency, the UNHCR, manages to convince rich countries to accept only one in every 100 of these refugees for permanent resettlement.

This amounts to some 100,000 people each year, mainly going to the U.S., Canada and Australia. These big headline numbers are what the public notices. What is hidden from the public view is whether these resettled refugees end up thriving in the communities where they are resettled.

The job of making the best match typically falls to a well-meaning and committed bureaucrat in the resettlement agency of their respective country. They grapple with the task using the information they receive from their government and the UNHCR, and, in a minority of cases, direct interviews with the refugee themselves. But ample research shows that where refugees end up initially really matters for their lifetime outcomes. And often refugees themselves do not gravitate towards the best communities for them.

This is why some of us think it is time for us to turn to “matching theory” and the work of economists like Al Roth, who shared the 2012 Nobel Prize in economics . If an algorithm can be used to optimize how resident medical interns get their positions at hospitals and how kidneys can be safely exchanged between pairs of compatible patients, then algorithms can also do a better job for refugees and host countries than our stoic bureaucrat.

Imagine if the government allocated children to schools in the way that it does refugees to communities. It would have the near impossible bureaucratic task of trying to make decisions for families and schools. Alternately, they could simply allocate children at random (which is what Sweden tried unsuccessfully to do with refugees). This would cause havoc. No sensible government works in this way. Instead, they elicit preferences about schools from parents and children and try to match them to schools nearby. We argue that in principle, the refugee resettlement problem is no different to school choice.

They are both examples of two-sided matching markets. For the match to happen on both sides – refugees/children and local areas/schools – need to pick each other. Economists like Roth have been thinking about designing these kinds of matching markets for decades and have created algorithms to make them work.

The obvious place to look for a stunning algorithm is in San Francisco. The city’s school choice system is a great illustration of ingenuity in the design of matching markets. Parents rank the schools, and the schools have priorities for different children. For example, a child who lives nearby and has a sibling gets a higher priority than a child without a sibling. Once all the information is uploaded into the central clearinghouse, the algorithm gets to work.

San Francisco uses a “top trading cyclesalgorithm to determine which child gets what school place. The algorithm runs in the following way: Every child points at their favorite school, and every school points at the child with the highest priority.

If we follow the arrows, there will have to be at least one cycle, for example, child 1➔school A➔child 2➔school B➔child 3➔school 3➔child 1.

In any such cycle, we allocate the children to the school they chose. By doing this, we know that we are giving a seat in the favorite school to children who are highest priority in some school. At the same time, we need to make sure we keep track of how many school places there are, so every time a school accepts a child, its capacity is reduced by one seat. In subsequent rounds, children continue to point at their favorite schools that still have capacity.

The algorithm ends when there are no further such cycles: Children can no longer point at any school because they are full, or schools could be pointing at children who definitely do not want to be in that school. The “top trading cycles” algorithm has amazing properties. First, unlike a school choice algorithm used until recently in Boston, parents have no way of manipulating it. The best strategy is to be honest about your preference. Second, once a kid is allocated to a school, a seat cannot be given to a child in a preferred school without making another child worse off. This ease of use and efficiency has made “top trading cycles” a popular algorithm for allocation of school places.

Refugee resettlement is trickier than other matching problems economists are used to dealing with. In school choice, a child takes up one slot at a school. But a refugee family may require more than one slot, i.e. they may need a number of services in a local area apart from a house. They may need hospital beds, school places, language classes or professional training. Local areas have different capacities to offer these services: Some may have many available school places but be short on hospital beds.

Computer scientists are accustomed to figuring out reasonably fast ways of solving these issues and refer to them as “knapsack problems.” Take an example problem such as how many weirdly-shaped boxes can you pack in the boots of your car and your friend’s much bigger car. The boxes are like the demands for services from refugees. And the two car boots are like different local areas. We now have a model for determining the maximum number of refugees that can be resettled.

Simply “filling the knapsacks” does not take the preferences of refugees into account. This is why in our work with economists Scott Kominers from Harvard University and David Delacrétaz from the University of Melbourne, we have shown, among other things, how top trading cycles algorithms can also be adapted for the knapsack case, in which refugees can safely express preferences for local areas, and those same areas can set their own priorities over certain groups of refugees.

Matching is not a panacea for the refugee crisis because there are still over a million people who are in urgent need of resettlement. But matching can drastically improve refugee resettlement by ensuring that the best matches can be found. The cost of poor refugee placement in extra government spending on welfare can be enormous. The cost of developing robust matching systems are miniscule in comparison.

Countries like Britain and Canada, which have control over refugee flows, developed centralized allocation procedures and have taken on substantial resettlement commitments, are perfectly placed to take advantage of our insights to pioneer world-leading refugee resettlement matching systems.

What we have today is in effect a cruel and expensive lottery. It is played with the lives of  refugees and the morale of host communities. It gives neither side a meaningful say. Taking refugees preferences into account and matching them to communities using smart algorithms is a small but necessary step towards a more successful and humane resettlement process.

The views expressed in this article belong to the author and do not necessarily reflect the editorial policy of Refugees Deeply.

Suggest your story or issue.


Share Your Story.

Have a story idea? Interested in adding your voice to our growing community?

Learn more
× Dismiss
We have updated our Privacy Policy with a few important changes specific to General Data Protection Regulations (GDPR) and our use of cookies. If you continue to use this site, you consent to our use of cookies. Read our full Privacy Policy here.