Algorithm 1: Stable Matching
(aka Let’s Pair People Up Without Drama)
The algorithm was actually invented in 1962 by David Gale and Lloyd Shapley (who, fun fact, later won a Nobel Prize for it!). Now, a heads-up: the original problem is framed in pretty old-school gender roles, so don’t judge—it’s just easier to explain that way in stable matching algorithm.
So, what is stable matching? In a nutshell, it’s a way to match two equal-sized groups so that no two people would rather be with each other than their current partners.
Table of Contents
If You Like Graph Theory, You’ll Love This
For all my fellow graph nerds out there, this problem is also known as a bipartite matching problem. The idea is simple: you have two groups, say A and B, and every member of group A needs to be paired with someone from group B. But the trick is to do this in a way that no one gets jealous or decides to “run off” with someone else. Easy, right? 😂
Real-World Example: Matching Doctors to Hospitals
A super practical example of where this algorithm is used is in matching doctors (or med students) to hospitals. It’s used in the real world to make sure, for example, that a med student gets matched to a hospital in a way that keeps both the student and the hospital happy (well, as happy as they can be).
Both sides make their rankings: hospitals rank the students they want, and students rank the hospitals they want to work for. The goal is to pair everyone up in a way where no one’s tempted to break up with their assigned partner for someone else. It’s like a dating app, but for hospitals!
What Exactly is a Stable Matching?
Alright, let’s break it down. A stable match happens when no two people would prefer to be with each other over their current match. If there’s a pair that feels that way, we’ve got an unstable match on our hands, and that’s a problem. Imagine the drama if, halfway through, people start running off with each other because they’d rather be with someone else—no thanks!
Example Time! Here’s How It Works
Let’s look at a simple example with preferences written in order:
Women’s Preferences:
- A: [E, F, G, H]
- B: [E, F, G, H]
- C: [F, G, E, H]
- D: [G, E, F, H]
This means person A prefers person E to F , prefers F to G and so on.
Men’s Preferences:
- E: [C, D, A, B]
- F: [D, A, B, C]
- G: [A, B, C, D]
- H: [D, C, A, B]
Example Match: Is it Stable?
Here’s a possible match-up:
- E – C (1st choice for E, 3rd for C)
- F – D (1st for F, 3rd for D)
- G – A (1st for G, 3rd for A)
- H – B (4th for both)
So, is this match stable? Yes! Here’s why: if B or H try to propose to anyone else, they’ll get rejected, because they’re at the bottom of everyone’s list. Meanwhile, the rest of the group has their top choices, so they have no reason to switch.
The Drawbacks: Not So Great for the Women
Here’s where things get interesting: while this match is stable, the women definitely didn’t get their top choices. So it’s not “optimal” for everyone.
When Things Go Wrong: An Unstable Match Example
Let’s look at a bad match:
- E – A (3rd for E, 1st for A)
- F – C (4th for F, 1st for C)
- G – D (4th for G, 1st for D)
- H – B (4th for both)
This match is unstable because B would rather be with someone else than H, and F would also prefer anyone else over C. So B and F might end up pairing off, leaving their current partners behind. The same thing could happen with G and B—this could easily fall apart.
This leads to some important questions:
- Can we always find a stable match?
- How do we find the best stable match?
- Are there multiple stable matches? What does an optimal match even look like?
Example: Roommate Problem
Now, let’s explore something a little different: the Roommate Problem. Instead of pairing up two groups (like men and women), we’re looking at a group of roommates. The setup is similar, but it leads to a different kind of challenge.
Here are the preferences:
Roommates: {A, B, C, D}
- A: [B, C, D]
- B: [C, A, D]
- C: [A, B, D]
- D: [A, B, C]
We can exhaust all possible pairings and check if they’re stable. If we think of this as a graph, each match gets two edges (one for each pair), and we’re looking at three possible pairings:
- (A, B) & (C, D)
- (A, D) & (B, C)
- (A, C) & (B, D)
Now, let’s check the stability of each of these pairings.
Are These Matches Stable?
1. (A, B) & (C, D)
A prefers B (1st choice), but B prefers C over A (2nd over 1st choice). Therefore, B and C could pair off, making this match unstable.
2. (A, D) & (B, C)
D prefers A (3rd choice) while A prefers C over D. On the other side, B prefers A over C, so B and A could switch, making this match unstable.
3. (A, C) & (B, D)
C prefers B over A (2nd over 1st choice), and A prefers B over C, so A and B could switch partners, making this match unstable.
Conclusion
As you can see, none of these matches are stable. This brings us to an important point: in the Roommate Problem, it’s possible that no stable matches exist. While there might be other preference combinations that lead to stability, this specific example shows how a situation can exist where no stable match is possible.
Stable Marriage vs. Roommate Problem
Though the Roommate Problem and the Stable Marriage Problem seem similar on the surface, they are actually quite different once you dig deeper. One key difference is that, in the Stable Marriage Problem, there is always a stable matching. This is a critical property that the roommate problem doesn’t share, as we just saw.
Algorithm for the Stable Marriage Problem
The algorithm to solve the Stable Marriage Problem is pretty straightforward. Here’s how it works:
- Step 0: Each person creates a ranked preference list of all the people in the opposite group.
- Step 1: Each woman proposes to the top man on her list. The men then reject everyone who proposes to them, except for the woman at the top of their list.
- Step 2: Every woman who wasn’t matched proposes to the next man on her list. If the man is unmatched, he accepts the proposal. If he’s already matched, he has the option to stay with his current match or switch to the new proposal.
- The algorithm continues until everyone is matched.
Note that this algorithm would work whether men propose, or women propose.
Share this article: