It’s important as a programmer (and a human) to understand the impact of our work and try to see how the applications we create may have adverse affects on our world. (This proof was too simplified to warrant a QED, but believe me, this algorithm works.) Additionally, once the algorithm is complete, each man has married his most preferred woman who was never proposed to by a man she prefers more, so there cannot be a rogue couple. #(as a result, the old husband is now unmarried)Ī very basic proof for this algorithm is as follows: If there is an unmarried man, then there must be an unmarried woman to whom he has not yet proposed since there are both n men and women. W breaks up with her current husband and marries m W = most preferred woman of m whom he has not yet proposed Their algorithm follows the following steps, which I’ve implemented in pseudocode (for the purpose of illustration, because an actual implementation wouldn’t be as readable). In 1962, David Gale and Lloyd Shapley devised an algorithm to programatically solve this problem. While this specific instance of the problem can easily be solved through trial and error, as the number of partipants gets larger, it becomes very difficult to obtain a stable matching.

So how can we decide on which couples should pair up and guarantee no rogue couples?

Example: Woman 2 prefers Man 4, then Man 2, then Man 1, then Man 3. Okay, so each man and woman has an ordered list of the women and men they prefer, respectively. Let’s look at some notation which might make this setup a little clearer: To measure each person’s preference for each potential partner, let’s assume that each man and woman has a ranked preference list of all people of the opposite gender. However, these marriages need to be ‘stable’ – that is, there is no man and woman who are not in a marriage that would rather be with each other than their current spouses (these pairs of men and women are called “rogue couples”). Suppose you have n men and n women and you need to create n couples to marry them all off so that each man and woman has exactly one opposite sex spouse. One of the first algorithms we studied in the beginning of the course was the Gale-Shapley algorithm to solve the Stable Marriage problem. We looked at greedy algorithms, dynamic programming, recursion, network flow algorithms, and many more. In college, I took a Computer Science course on Algorithms, where we explored ways that programmers and computer scientists approach complex problem solving. This post originally appeared on Jake Faris’s blog.

Gale shapley java program