You May Now Kiss the Algorithm

Think of it as mass customization for love. JL

Jo McGinty reports in the Wall Street Journal, photo by Lee Jin-Man for the AP:

A simple set of rules known as the deferred acceptance algorithm leads to stable matching, where no couples will break up to form new matches.The algorithm has several important properties: There is always a solution. The resulting unions are always stable, according to the algorithm’s definition. The logic of the stable marriage solution may seem modest. But in 2012, Drs. Roth and Shapley shared the Nobel Prize in Economics  for using it to find practical solutions to real-world problems.

Sorry, love birds. Sometimes, you have to take what you can get.
That’s the message of the stable marriage problem, whose mathematical solution pairs potential partners in such a way that none will divorce.
That doesn’t mean everyone gets the mate of his or her dreams. But it does mean no two people will prefer each other over the partner they’ve wedded.

In other words, a union is stable if no one else you desire will have you.
That sounds bleak, but according to the problem’s solution, it’s why couples stay together. No one can do any better, so they stick with what they have.

The Stable Marriage Problem

A simple set of rules known as the deferred acceptance algorithm leads to stable matching, where no couples will break up to form new matches. The stable marriage problem and its solution were laid out in a landmark paper in 1962 by David Gale and Lloyd S. Shapley, both American mathematicians and economists. It has since been used to match doctors with hospitals and students with schools.

Here’s how it works:
For the sake of simplicity, let’s assume there is a group of men and women who must be married off. It doesn’t matter how many. The men will propose. (Granted, this scenario is dated, but it’s an algorithm; rules are required.)
Everyone ranks their potential mates. The men propose to their first choices.
Some women may receive multiple proposals. Some may receive none. Each woman who gets one or more offers holds the proposal of the man she prefers most and rejects the rest—but she doesn’t yet accept the offer, because someone better may come along.
Every man who was rejected now proposes to his second choice. Each woman again holds onto the proposal of the man she most prefers, even if it means ditching someone who proposed earlier. This continues until no man wants to make any more proposals and the women accept the offers they are holding. The algorithm has several important properties: There is always a solution. The resulting unions are always stable, according to the algorithm’s definition. The men always end up with their best possible stable match. And the women always end up with their worst.
It’s easy to see why the men end up with the optimal match: They go down their ranked list until they’re paired with the first woman they are attracted to who will not dump them for someone else.
“It might not be his No. 1 woman, but she’s his first preferred stable match because all the women who are not achievable rejected him,” said Alvin E. Roth, a professor of economics at Stanford University.
If women issued the proposals, rather than men, they would end up with the optimal match.
It seems as if the group that receives the proposals would have the upper hand because they can discard an offer when someone better comes along. But in practice, members of that group end up with the last person on their list who would form a stable match.
“What’s really surprising is that if you follow this algorithm, it gives the best possible result to the proposers, and it achieves that by giving the worst possible result to the others.” said Emily Riehl, a mathematician at Johns Hopkins University. “They are diametrically opposed. That’s the way stability works.”
Still, perfect matches are possible. A man and woman may list each other first and end up together. In that case, the “best” and “worst” stable matches are the same—like being an only child who is both the first- and last-born.
When the heart is involved, the solution to the stable marriage problem sounds less than ideal, but there are instances in real life when it produces a truly desirable result. The best-known example is the National Resident Matching Program, which pairs medical school graduates with hospitals.
In the 1940s, hospitals seeking to lock in the best students began courting them earlier and earlier in their medical-school careers, sometimes with little evidence of their qualifications. Meanwhile, the students, forced to make early decisions, couldn’t risk waiting for a better opportunity.
To fix the problem, a matching system was introduced in the early 1950s. Using the principles of the stable marriage problem and its solution, Dr. Roth helped improve the design in the late 1990s to, among other things, give preference to students, rather than hospitals, by making them the proposers.
The algorithm has also been used to redesign school-admissions processes in New York City and elsewhere.
The logic of the stable marriage problem and its solution may seem modest. But in 2012, Drs. Roth and Shapley shared the Nobel Prize in Economics for using it to find practical solutions to real-world problems.
Their work demonstrated that, simple as it may sound, if you’ve managed to establish a stable marriage, you really do deserve a prize.