the singularity of being and nothingness
The Stable Marriage Problem
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!
Print article | This entry was posted by existdissolve on September 8, 2014 at 10:52 pm, and is filed under ColdFusion. Follow any responses to this post through RSS 2.0. You can leave a response or trackback from your own site. |
about 10 years ago
“both marriages are considered unstable since both Ron and Stacy prefer each”
you mean Ron and Marian, right?
about 10 years ago
Yes, thanks for catching that. Typo has been corrected. Thanks!