Let’s create a reality show unlike any other in one key aspect. First, we will rent a villa on a tropical island. Then we fly five men and five women, each with their own (heterosexual) relationship preferences. Our goal, however, is completely the opposite Love Island Franchise: We want absolutely zero drama. Can we ensure everyone is matched with a partner and sticks with them without jealousy rearing its ugly head?
Mathematicians call this dilemma the “stable bond problem” or the “stable marriage problem.” And while matters of the heart can be fickle, researchers have proven this using a simple the algorithmthey can always find a stable set of matches between all members of two groups of equal size. The late mathematician Lloyd Shapley shared the 2012 Nobel Prize in economic sciences for the discovery of this algorithm—and for good reason: it’s still used today to match medical residents with hospitals and children with schools, and it’s inspired it. dating app algorithms.
According to mathematicians, a relationship is stable when neither person has a better option—at least not one they’re interested in. The instability, then, might go something like this: Imagine that Alice is paired with Bob, and Charlie is paired with Darlene. Bob is secretly in love with Darlene, however, and Darlene can’t bear the thought of another day with Charlie. Since Bob and Darlene seem ready to run away together and leave their partners behind, mathematicians call this situation unstable.
About supporting science journalism
If you like this article, please consider supporting our award-winning journalism subscribe. By purchasing a subscription, you’re helping to ensure a future of impactful stories about the discoveries and ideas that shape our world.
The same dilemma appears outside of romantic life as well. Shapley and the mathematician David Gale first described it as a college admissions problem: What kind of application process would ensure that the college and the applicant, each with their own set of preferences, are satisfied with their choice? In 1962 Gale and Shapley showed that for any set of students and colleges (or men and women, in the dating demonstration example), there always exists a set of matches where each match is stable. They also provided a simple process or algorithm that takes everyone’s ranking and produces relatively happy couples.
Here’s how it works. In order for our 10 dating show contestants to find a stable, drama-free partnership, we first have each contestant rank all members of the opposite gender according to their preferences.
Then, on the first day of the villa, each woman makes a relationship proposal to the man of her choice. Some men receive many proposals, while others receive none. Each man then rejects all his preferred suitors, resulting in a temporary match for some of the contestants, while others are left without a partner.
On the second day, each rejected woman proposes her second choice (even if they are already matched). Men consider new proposals, and some may abandon the current match if they prefer. Then some of those newly broken hearts would propose to their next partner.
This process is repeated on the third, fourth and subsequent days, as many times as necessary, until everyone settles on a match. Not everyone will be happy with being matched using this process, it’s mathematically guaranteed that no two people will both prefer to be with each other over what they have today (assuming their preferences haven’t changed since they met each other, that is). Although this will not guarantee ours Love Island spin-off remains a relaxing drama-free watch, which is probably as good as we’re going to get.
Interestingly, the group that proposes first has an advantage: when women propose first, on average, they end up with more desirable matches than men. “The only problem with Gale-Shapley is that it gives you these extreme matches on both sides,” explains Vijay Vazirani, a computer scientist at the University of California, Irvine.
The results may be slightly skewed, but Gale and Shapley’s strategy cannot be beat. And as it turned out, a version of it had been used by a matching organization since the 1950s. medical students to residency programs across the country. In 1984, Alvin Roth, an economist at Stanford University, used the mathematical language of Gale and Shapley to argue that the process used by this organization not only guaranteed stable pairings, but was also “anti-strategy,” meaning there was no way to game the system. This feature, generally referred to as incentive compatibility, is valuable because it means that everyone will end up with their best choice if their preferences are truthfully communicated.
Roth and economist Elliott Peranson also made some changes to the algorithm. They adapted it to work for medical students who want to get married together and do their residency in the same place. They also stated that residents were getting the short end of the stick because the hospitals suggested it first. Roth advocated for residents to propose first to ensure they would get the best outcome. Today, hospitals and incoming residents rate each other, and the math works to ensure a steady state is achieved. Roth and Shapley won the 2012 Nobel Prize in Economics for their work.
Roth and his colleagues also used this mathematical language to address a matching problem: assigning children to public schools in the largest US cities. In 2003 Gale-Shapley was adapted to assign students to competitive public high schools in New York City. In its first year of operation, the number of students matching one of the major options increased from about 50,000 to more than 70,000. Another version of the algorithm is also used to assign students to Boston public schools.
And in the romantic sphere, the Gale-Shapley algorithm has even inspired the inner workings of dating apps like Hinge. While users don’t explicitly rank their potential matches, these apps observe users’ likes and dislikes history, along with their stated dating preferences, to curate the few “high-flyers” they show users first. A like or message sent to a potential match is similar to a “proposal” in the original algorithm.
“The power of models like (Gale-Shapley) is to abstract an idea across multiple settings,” points out Jon Kleinberg, a computer science professor at Cornell University. Problems from different domains “could all have something in common conceptually,” he says, and the Gale-Shapley algorithm “gave us a mathematical language to talk (about them).’
Although the algorithm is simple and reliable, it can also increase existing differences if there is a bias in the ranking. Admissions data obtained by The City, a nonprofit newsroom based in New York City, showed how black and Latino students consistently fare. selected to join at a lower rate metropolitan high schools than white and Asian students, especially at many top schools. The residence match was the program has shown similar gaps in racial and gender equality.
“The real problem is not the algorithms themselves” but the ranking data they use and the environment in which they are deployed, explains Boston College economics professor Utku Ünver. This dynamic has been visible throughout the rise of artificial intelligence. : As complex algorithms learn to reproduce patterns in our data, they often do repeat ours prejudicesalso
“If humans are biased, then our bias is in the data,” says Cornell University computer science professor Éva Tardos. Researchers have proposed a number of ways to deal with data bias. For example, organizations such as hospitals or schools may use larger and more diverse panels to rank candidates. Additional algorithms could also be used to account for known biases by reweighting the rankings before using them for matching.
Of course, no algorithm can guarantee a happy match in marriage or school. But the best choice it remains simple, transparent and encourages honesty; so even 60 years later, it seems the Gale-Shapley algorithm still hasn’t been outdone.
