While I was on the road this last week, I watched a video on one my favorite YouTube channels: Numberphile. This video discusses the Gale/Shapley algorithm for solving the Stable Marriage Problem.

If you’re unfamiliar with the Stable Marriage Problem, consider this:

You are the ruler of an island kingdom on which you have an even number of males and females, all of whom are of marriageable age. What you want to do as ruler is to create a series of perfectly “stable” marriages which will provide a good cement for the durability of your society.

In this scenario, a stable marriage is defined fairly simply as a union in which the man does not prefer another woman over the one to which he is married, while the other women also does not prefer the man over the one to which she is married.

For simplicity’s sake, consider two marriages:

  • Ron & Stacy
  • Doug & Marian

Scenario #1

Let’s say that Ron prefers Marian over Stacy, even though he’s married to Stacy. If Marian prefers Doug to Ron, she has no reason to leave Doug for Ron, and so her marriage is considered “stable”. Likewise, since Marian has no reason to leave Doug for Ron, Ron also has no legitimate reason to leave Stacy, even though he might secretly (or openly!) prefer Marian. In other words, his leaving Stacy will not help his cause with Marian, since Marian still prefers Doug to Ron. While Ron might be unhappy that he cannot be with Marian, his marriage is considered “stable” since he has no realistic reason to leave Stacy, given that his preference (Marian) does not also prefer him to her spouse.

Scenario #2

Now let’s flip it. Let’s imagine that Ron prefers Marian to Stacy (as before) AND Marian prefers Ron to Doug. In this case, both marriages are considered unstable since both Ron and Marian prefer each other over the spouses to which they are currently married.

The challenge of the Stable Marriage Problem, then, is to answer a simple question: Given an equal number males and females, is it possible to construct a complete set of stable marriages, marriages in which each partner has maximized their preferences in relation to their eventual spouses’ preferences? In other words, can we create 100% successful, stable marriages which are immune to the mutual preferences outlined in Scenario #2?

The Gale/Shapley Algorithm

According to an algorithm produced in 1962 by Gale-Shapley, the answer is yes. This algorithm, interestingly enough, has a lot less to do with pure mathematics and more to do with “iterations” and the logic executed within each iteration.

When I saw this explained, this sounded a lot like code to me, so I headed over to RosettaCode. Sure enough, this task has already been created and a number of solutions for different languages have already been submitted. ColdFusion, however, was absent from the list, so I decided to submit a crack at it.

Conclusion

The code itself isn’t that complex, so I’m not going to bother going through it here. If you’re interested, check it out on GitHub. Or better yet, become more acquainted with the Stable Marriage Problem and take a swipe at it yourself!