The Stable Marriage Problem
Let’s do a little thought experiment.
Six friends are going rock climbing. Nia, Ira, and Jo want to climb and Bela, Misha, and Ali want to belay (manage the ropes). They each have the following ranking for who they partner up with:
Your job is to pair each climber with a belayer. You want to avoid the situation where two people who weren’t paired together would both rather be with each other than their assigned partner. These are called unstable pairs. As long as you pair everyone up with no unstable pairs, then you have a stable matching between the climbers and the belayers. I invite you to play with this a bit and see if you can find a stable matching for our friends above.
Scenarios like this one are examples of the stable marriage problem. In broad terms, the stable marriage problem asks if it’s always possible to find a stable matching between two equal sized groups of elements (people, places, etc.) given that each element has an ordering of preferences. Numberphile teamed up with Emily Riehl to create a fantastic video describing this problem (and another one explaining the math behind it).
In 1962, David Gale posed the stable marriage problem to Lloyd Shapley, and together they found a method that will always generate a stable matching. No real surprise, it’s called the Gale-Shapley algorithm. By algorithm, we mean a step-by-step process to follow. Let’s look at their algorithm in the context of our climbers and belayers:
- Each unmatched rock climber asks their first choice belayer to be their climbing partner.
2. Each belayer considers the rock climber(s) that asked them (there may be multiple!), and says ‘maybe’ to their most preferred and ‘no’ to the rest.
3. Each unmatched (rejected) rock climber goes to their next choice and asks that belayer to be their climbing partner.
4. Each belayer says ‘maybe’ to the offer from their most preferred climber and ‘no’ to the rest.
5. Repeat steps 3 and 4 until every climber is matched with a belayer.
We end up with Jo + Bela, Nia + Misha, and Ira + Ali. I challenge you to check if this is truly a stable matching. Remember, for it to be stable, no two unmatched people would rather be with each other than with their assigned partners.
There are a couple interesting things to notice about this algorithm. First, it will always provide you with a stable matching. Why? Imagine for a minute that we found a belayer and climber who would rather be with each other than their given pairs. The way the algorithm works, this means that the climber would have already chosen this belayer at some point in the process and the belayer turned them down for someone they liked better. Which means the belayer is happier with their current match than with this other climber they weren’t paired with.
This leads to the second big observation about this algorithm: it favors the climbers. Or more generally, it favors the group asking rather than the ones responding. To visualize this, let’s look at the preferences lists again, this time highlighting just the matches that the algorithm assigned.
You can see that more of the climbers were matched with their first and second choices and (as a whole) it was a little rougher for the belayers. This is a rather simple example, so we would actually get the same result if we had the belayers ask and the climbers respond. However, as these scenarios get more and more complex, there can be multiple stable matchings and changing the role of each group can give you significantly different results.
Why is the stable marriage problem important to think about (aside from minimizing disputes at your next group climb)? It turns out that the Gale-Shapley algorithm is being used in all sorts of really big ways. In the US, Canada, and Scotland, a variation of this process is used to match recent med school grads with hospital residency positions. The students rank the hospitals they want to work at, and the hospitals rank the students they want to take on. Then the algorithm does it’s work to create the most amenable assignments of students to positions.
The stable roommate problem is a variation used to assign roommates in college dorms and similar situations where the pairs are all coming out of a single group (students), rather than two distinct groups (climbers + belayers).
The stable marriage problem is even being used to assign internet users to servers. What’s crazy here is that content delivery networks (you can thank these networks of servers for your virtually buffer free Netflix binges), are solving the stable marriage problem for billions of users every tens of seconds.
