In search of the perfect match
‘One algorithm had to cope with pairs of romantically attached doctors who wanted two job offers in the same city’
When it comes to finding the perfect match, nobody wants to be left on the shelf but the Arunta — a polygamous aboriginal tribe from the area around Alice Springs — used to take things to extremes. As described by anthropologists in the 1920s, the father of a newborn Arunta boy would get together with the father of a newborn girl to arrange a future marriage. The betrothal was not between the two babies, of course — that would be leaving things far too late. Instead, the engagement was between the baby boy and the first daughter that the baby girl had when she became a mother herself.
This astonishing process is called “market unravelling”, and it is not limited to the Arunta. As described in Alvin Roth’s new book, Who Gets What — and Why, hospitals make early offers to untried junior doctors. Law firms make early offers to law student freshers. Oxford and Cambridge make offers many months before the students in question sit their exams.
This is not a sensible situation because if everybody could agree to wait, then more information would emerge, allowing more compatible matches. Yet there is an incentive to break ranks and make early “exploding” offers. If those time-limited offers are any good, then students will often accept them rather than take the risk of waiting. The logic of the situation pulls these early offers ever earlier, sometimes absurdly so. Everybody loses but no individual can change things.
One response is to agree a rule banning early offers. That is what the US National Association for Law Placement did in the 1980s: it ruled that any job offer made to a first-semester law student had to remain open until the end of that semester. It wasn’t long before the lawyers had found the loophole: mediocre offers paired with massive time-limited signing bonuses.
Another possibility is to use a central clearing house. That is what the Boston school system did. Parents listed at least three schools in order of preference, and the clearing house put every child into their first choice school where possible. Any schools with spare places would then admit students who’d listed the school as second choice, then third choice, and so on. Four out of five students got their first choice, yet parents hated the system. Why?
The problem was that parents had just one shot at a good school. Popular schools filled instantly, making second choices almost irrelevant. Parents who didn’t understand the game might apply for several popular schools and get nothing. Those who understood the problem found themselves second-guessing the clearing house, using their precious first choice on a compromise school rather than the high-risk approach of saying what they truly wanted. The system produced cynical, alienated parents.
The problem is easier to describe than to solve. But there is a way to fix unravelling markets: call Alvin Roth. An engineer by training — albeit one with a Nobel Memorial Prize in economics — Roth designs markets with an engineer’s practical mentality. With his colleagues, Roth has designed stable clearing houses for doctors, fixed the school application systems in Boston and in New York City, and even created kidney donation networks.
At the heart of many well-functioning clearing houses is something called the deferred acceptance algorithm. The algorithm begins with the following input: each student submits a list of their preferred schools, from first choice to last, and each school submits a ranked list of their preferred students. Armed with these rankings, a computer can swiftly handle the rest. First, each school provisionally fills its places with the top students on its list; then each student provisionally accepts the best offer she has received and rejects the others; each school then extends further offers to fill the spaces that these rejections opened up. The process continues (inside the computer) with each student keeping only the best offer received so far, and with each school working down the list of students and making fresh offers as the rejections come in.
There are two important features of the deferred acceptance algorithm. The first is that people can safely tell the truth about their favourite schools — there is no disadvantage to aiming high. The second is that the algorithm’s allocation is stable. There will never be a pair of school and student who wish they were matched to each other but whom the algorithm sent elsewhere. This matters because if such pairs exist, they have an incentive to strike side deals, undermining the whole system.
The deferred acceptance algorithm is just the start of a successful market design, because details matter. In New York City, there are different application procedures for certain specialised schools. When assigning hospital residencies, the US National Resident Matching Program needed to cope with pairs of romantically attached doctors who wanted two job offers in the same city. These complexities sometimes mean there is no perfect matching algorithm, and the challenge is to find a system that is good enough to work.
Economists such as Alvin Roth are like engineers or doctors. They cannot settle for understanding a system in theory; they must solve practical problems too. It’s a hopeful direction for economics — and an essential one, if economists aren’t to be left on the shelf themselves.
Also published at ft.com.