When everyone has preferences, nobody gets first choice.
Medical residents and hospitals both have preferences. So do roommates, space crews, and dating apps. What happens when optimal choices conflict?
You're running a medical residency program. Fifty brilliant students rank their preferred hospitals. Twenty hospitals rank their preferred students. Everyone has a different first choice, and nobody wants to settle. How do you assign students to hospitals so that no student-hospital pair would rather abandon their assignments and pair up with each other instead?
This is the stable matching problem, and it's harder than it looks. If Dr. Martinez prefers General Hospital over her assigned County Medical, and General Hospital prefers Dr. Martinez over their assigned resident, they both have an incentive to break the system. A single 'blocking pair' like this can unravel the entire matching process, leaving everyone worse off.
The Algorithm That Changed How We Allocate Everything
In 1962, mathematicians David Gale and Lloyd Shapley proved something remarkable: stable matchings always exist, and there's a systematic way to find them. Their algorithm works through rounds of proposals and rejections, where one group (the 'proposers') makes offers to their most preferred available options, and the other group (the 'receivers') tentatively accepts their best offer while rejecting the rest.
The genius is in the 'tentative' part. Receivers can always upgrade to a better proposer later, creating a natural filtering process. What emerges isn't necessarily anyone's dream scenario, but it's something better: a matching where no pair of participants would rather defect from the system. The National Resident Matching Program has used this exact algorithm since 1997 to place medical graduates into residency programs across the United States.
Why Your Intuition About Fair Matching Is Wrong
Most people's first instinct is to give everyone their top choice whenever possible, then work down the preference lists. This seems fair, but it creates exactly the blocking pairs that make systems unstable. The counterintuitive truth is that sometimes giving someone their second or third choice creates better outcomes for everyone.
Consider this scenario: Alice's first choice is Bob, Bob's first choice is Charlie, and Charlie's first choice is Alice. If you try to satisfy first preferences, you get a three-way deadlock. But if Alice settles for her second choice (David), Bob can have Charlie, and Charlie can be with someone who actually wants to be with her. Everyone ends up happier than in the deadlock scenario, even though nobody got their absolute first choice.
From Medical School to Kidney Exchanges
The stable matching algorithm shows up everywhere once you know what to look for. New York City uses it for high school admissions, matching students to schools based on test scores and preferences. Kidney exchange networks use variations to match donors with recipients across multiple incompatible pairs. Even some dating apps have experimented with stability-focused matching instead of simple preference maximization.
The common thread is that these systems all deal with two-sided markets where both sides have agency and preferences. Traditional market mechanisms fail because there's no price signal to balance supply and demand. Instead, you need an algorithm that respects everyone's autonomy while preventing the system from collapsing due to defection.
The Game Theory Behind Everyday Choices
Stable matching reveals something profound about how fairness actually works. It's not about giving everyone what they want—it's about creating systems where everyone has an incentive to participate honestly rather than gaming the mechanism. This connects to broader questions in game theory about how individual rationality can lead to collective outcomes.
When you're choosing roommates, planning group projects, or even thinking about career decisions, you're navigating similar trade-offs between individual preferences and systemic stability. The math doesn't solve these problems for you, but it does show you what questions to ask: What happens if everyone follows their self-interest? Are there equilibrium points where no one wants to deviate? How do you design systems that align individual incentives with collective goals?
Get the next one
An occasional note when something genuinely new ships here — essays, free tools, projects. No schedule, no filler, easy out.
Need something like this built?
I design and ship AI tools, full-stack apps, and data pipelines — end to end, to production. Tell me the problem in a sentence; I'll give you an honest read on fit within a day.
Work with me →