The ‘Stable Marriage Problem’ Solution Underpins Dating Apps and School Admissions
By Max Springer, Scientific American
Let’s create a reality dating show unlike any other in one key aspect. First, we’ll rent a villa on a tropical island. Then we’ll fly in five men and five women, each with their own (heterosexual) dating preferences. Our goal, though, is the exact opposite of the Love Island franchise: we want absolutely zero drama. Can we ensure that everyone pairs off with a partner and sticks with them, without jealousy rearing its ugly head?
Mathematicians call this dilemma the “stable matching problem” or “stable marriage problem.” And though matters of the heart may be fickle, researchers have proved that by using a simple algorithm, they can always find a stable set of matches between all members of two equally sized groups. The late mathematician Lloyd Shapley shared the 2012 Nobel memorial prize in economic sciences for the discovery of this algorithm—and for good reason: it is still used today to pair medical residents with hospitals and children with schools, and it has even inspired dating-app algorithms.
….
Interestingly, the group that gets to propose first has an advantage—when the women propose first, they will, on average, end up with matches that are more desirable to them than the men will. “The one issue with Gale-Shapley is that it gives you these extreme matches on either side,” explains Vijay Vazirani, a computer scientist at the University of California, Irvine.
Read the full article in Scientific American.