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 More >