NYT Sunday, January 27, 2013

Numberplay January 21, 2013, 12:00 pm 37 Comments

The Stable Marriage Problem 

[click for text with pictures and a link to a video]

By GARY ANTONICK

This week’s problem was suggested by Ken Fan, founder and director of Girls’ Angle, a Boston-area math club for girls and a supportive community for all girls and women engaged in the study, use and creation of mathematics.

The Stable Marriage Problem was featured in the December issue of Girls’ Angle Bulletin, a bimonthly magazine full of interviews with mathematicians, articles on math, mathematical activities, math problems, and math-inspired art. Check back on Wednesday to download the entire magazine, including the solution to this week’s problem.

The Stable Marriage Problem

Four single men and four single women decide they’d like to pair up into four married couples. They’d like to choose their partners in a way that ensures their marriages are stable: that is, there are no two people who would both rather be married to each other than their current partners.

In order to help make sure they enter into stable marriages, the men and women, when they first start dating, rank members of the opposite sex in order of preference. Charlotte, for example, prefers Bingley most of all, and then Darcy, Collins and finally Wickham.

The rankings of all four women can be summarized as follows.

The men, of course, have preferences as well:

Who should marry whom?

Solution

Mike stepped through the solution as follows:

Bingley and Jane have to be together and since they are each other’s first choice, their marriage is stable. Since neither of them will split for anyone else, we can remove them from the everyone else’s lists. With them gone, Lydia and Wickham are each other’s first choice. Putting them together and taking them off the lists makes Elizabeth and Darcy first for each other, leaving Charlotte and Collins as the final couple.

These lovers from Jane Austen’s Pride and Prejudice were fairly easy to pair up into stable marriages because there were only 8 people involved. But the problem could become much more difficult. Here’s Ken Fan:

With 4 men and 4 women, an ad hoc approach can work. But imagine a scenario with thousands of men and an equal number of women all longing for a stable match-making outcome, that is, one where no man and woman who are not partners actually prefer each other to their respective partner. At such a scale, an ad hoc approach would surely be rocked by drama and a few broken hearts before all were paired up, and chances are, the matching would be far from stable.

But in 1962, David Gale and Lloyd Shapley wondered if there was a way to formulate a procedure that would find a stable outcome and avoid all the drama. They succeeded brilliantly.

The Gale–Shapley algorithm involves a number of iterations. In the first iterations, each unengaged woman proposes to the man she prefers most, and then each man tentatively accepts the proposal he prefers and rejects all others. He is then tentatively engaged to the suitor he prefers so far, and that suitor is likewise tentatively engaged to him.

The iterations then continue, with each unengaged woman proposing to the most-preferred man to whom she has not yet proposed (whether or not the man is already engaged), and each man tentatively accepting the proposal he prefers and rejecting all others. The tentative nature of engagements enables an already-engaged man to break his current engagement and accept the offer from a woman he prefers.

If the algorithm terminates in a complete matching, then by design, no woman, say Jane, would prefer another man, say John, over her husband who also preferred Jane over his wife because Jane would have made an offer to John before making one to her husband and John would have accepted Jane at that time, for had he been with a woman he preferred even over Jane, then John wouldn’t have given this preferred women up for his current wife, whom he presumably prefers less than Jane.

So the critical question is, why does the algorithm terminate with a complete matching?  (The algorithm surely terminates, because there are only finitely many people on each woman’s list.)  If any woman had no partner at the end, there would have to also be an unmatched man at the end.  But a man can be unmatched only if he receives no offers.  Since every man is on every woman’s list, that would never happen.

See the algorithm in action in the beautifully illustrated solution in the December 2012 issue of Girls’ Angle Bulletin.

Harvard University postdoctoral fellow in mathematics Emily Riehl presents the stable marriage problem in a Women in Mathematics video produced by Girls’ Angle and shares the real world application that makes the algorithm her favorite.