How a matchmaking algorithm saved lives

Long before dating sites, a pair of economists delved into the question of matchmaking, and hit upon a formula with applications far beyond romance.

Image for post
Image for post

Would you let an economist set you up on a date?

Image for post
Image for post

Economics is often associated with the idea of money. But the field extends beyond what can be (or should be) monetized.

In the 1960s, researchers David Gale and Lloyd Shapley embarked upon research to take up an unlikely subject: matchmaking.

Funded in part by the Office of Naval Research, they were interested in the math behind pairing people up with partners who returned their affections.

Image for post
Image for post

Suppose you had a group of men and a group of women who wanted to get married. Gale and Shapley wanted to see if they could develop a formula to pair everyone off as happily as possible.

Here’s an example inspired by Jane Austen’s “Pride and Prejudice”:

Image for post
Image for post

The goal is to find stable matches between two sets of people who have different preferences and opinions on who is their best match.

The central concept is that the matches should be stable: There should be no two people who prefer each other to the partners they actually got.

Image for post
Image for post

Gale and Shapley developed the deferred acceptance algorithm (also known as the Gale-Shapley algorithm).

It establishes a system by which everyone is able to find the person they most prefer from among those who prefer them.

The men and women each rank their preferences.

Image for post
Image for post

And then they are sorted using the algorithm:

For any number of partners, no matter how they rank each other, it is possible to use the Gale-Shapley algorithm to find at least one stable partnership for each person.

Image for post
Image for post

But life isn’t a Jane Austen novel

You may have noticed that out in the real world, this isn’t exactly how dating or marriage works. For example, the model doesn’t take into account gay couples, bisexuality or people who prefer to be single.

Image for post
Image for post

So what’s the value of this kind of research? A lot, as it turns out.

Gale and Shapley weren’t really trying to crack the code on romance. What they were seeking was an approach to so-called matching markets — where there is supply and demand, but no money changes hands. Marriage was simply a way to illustrate the problem.

When they began, their work was purely theoretical. But as is often the case with basic research, it ended up having applications in practical and important ways.

Assigning new doctors to hospitals

Image for post
Image for post

In the 1980s, a Harvard economist named Alvin Roth (now at Stanford) was interested in approaching economics like an engineering discipline — using theoretical ideas to improve real-world systems.

He wanted to diagnose matching markets that weren’t working and adapt the Gale-Shapley algorithm to help them work more efficiently.

Roth, with backing from the National Science Foundation, began looking at the National Residency Match Program (NRMP), a system that assigns new doctors to hospitals around the country.

In the 1990s, the NRMP was struggling because new doctors and hospitals were often both unsatisfied with its assignments.

Roth used Gale and Shapley’s work to reshape the NRMP matching algorithm so that it produced matches that were more stable.

Pairing students to public schools

The Gale-Shapley algorithm also proved useful in helping large urban school districts assign students to schools.

New York City, like many cities, enables students to select a high school by ranking their preferred choices from among all its schools.

Before Roth and his colleagues redesigned it, the public high school assignment process was a mess. About 30,000 students a year were left unmatched and ended up at schools they hadn’t even listed.

Image for post
Image for post

The process of matching doctors or students is a little more complex than matching romantic partners since hospitals and schools — unlike most couples — accept many proposals.

But the underlying principle of deferred acceptance that Gale and Shapley defined is the same.

Helping transplant patients find a match

The real breakthrough came in 2004. That is when Roth developed the matchmaking principle to help transplant patients find donors.

At the time, less than 20 people each year received kidneys from living donors, even though transplants from living donors produce much better patient outcomes.

The frequency of these life-saving procedures was limited by a simple, heartbreaking problem: Many people are willing to donate a kidney to a loved one but they cannot because blood type and other factors make them incompatible.

Image for post
Image for post

Roth devised an exchange system to help incompatible donor-recipient pairs find others in the same situation. Through complex chains of exchange, all participants had the promise of finding a suitable match.

Image for post
Image for post

The result: thousands of people have been able to receive kidneys who otherwise might not have been able to get them.

It was a leap that earned Shapley and Roth the Nobel Prize in 2012. (David Gale passed away in 2008, so was not eligible for the prize. Shapley passed away in 2016.)

Image for post
Image for post

The formula is now being employed for other uses, such as helping kids in foster care find adoptive parents.

It has even found 21st century applications in romance, influencing approaches to online dating and speed dating.

The journey of discovery

Take any invention or modern innovation and in its history you’ll find decades — or even centuries — of odd and obscure research that led to its creation.

One of the hallmarks of science is that the path to knowledge is often indirect. In addition to rigorous investigation, discovery is often shaped by serendipity and human curiosity.

When Gale and Shapley began, their work was theoretical and abstract. Their research may have seemed obscure or even pointless, but the insights they gleaned built the foundation for breakthroughs that have improved countless people’s lives.

Today, roughly 5,500 transplant patients in the U.S. receive kidneys each year from living donors.

These happy matches wouldn’t be possible without the work of Roth, Gale and Shapley.

Like love, research works in mysterious ways. The results and impacts are sometimes unpredictable and unexpected — and that’s a big part of what makes it so important.

Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch

Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore

Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store