Live model · Dating-app matching
How Stable Matching Actually Works
In Gale and Shapley's deferred acceptance, one side proposes in order of preference and the other holds its best offer so far, trading up when a better one comes. Anyone turned down tries their next choice. When no one is free, no two people would both rather be together. Hinge said in 2018 that Most Compatible is built on it.
Deferred acceptance, one round at a time
How to read the stage
Ana, Ben, Cai and Dev propose to Wes, Xia, Yuki and Zoe, and the two tables are everyone's rankings. In round 1, three of them propose to Xia, who holds Dev and turns down the rest. Then Yuki drops Cai for Ana, and Cai bumps Dev from Xia. After 5 rounds and 9 proposals: Ana–Yuki, Ben–Wes, Cai–Xia, Dev–Zoe.
Why the result is stable
A matching is stable when no two people would both rather be together than with their partners. Deferred acceptance always ends stable. A receiver only ever trades up, and a proposer moves down the list only after being turned down, so everyone a proposer prefers is already holding someone they like better. The last frame checks all 12 pairs that didn't match.
Who proposes decides who wins
Of the 24 ways to pair these eight people, 3 are stable. Ana's side proposing finds the best of them for everyone on Ana's side, whose partners average 2.25 on their lists. Let Wes's side propose and it finds the other end: Wes's side averages 1.25, Ana's side 3.25. Gale and Shapley proved the proposing side always gets its best stable matching.
Every possible pairing, checked for stability
- CH1 Ana's side
- CH2 Wes's side
What Hinge actually does
Hinge launched Most Compatible in July 2018, citing Gale and Shapley. It told TechCrunch it adapted the algorithm to one shared pool, the stable roommates problem, learns each person's preferences from their likes and passes, and shows one Most Compatible a day. It hasn't published how the feature works today, so the stage runs the original two-sided algorithm.
What the model leaves out
Real markets are bigger and messier: people rank only a few others, lists have ties, and one side can outnumber the other. The National Resident Matching Program has applicants propose, with Roth and Peranson's version that lets couples match together. A dating app has to guess preferences rather than read rankings. The model has four people a side, each ranking everyone.
Questions
- Does the side that proposes get better matches?
- Yes. Deferred acceptance gives every proposer the best partner they could have in any stable matching, and every receiver the worst. On the stage, letting Wes's side propose moves Wes's side from an average of 2.25 on their lists to 1.25, and Ana's side from 2.25 to 3.25.
- Is Hinge's Most Compatible really the Gale–Shapley algorithm?
- Hinge said so when it launched the feature in 2018, with changes: one pool rather than two sides, and preferences learned from likes and passes rather than ranked lists. Nothing published since shows how it runs today, so treat the stage as the idea Hinge started from, not its code.
- Who won the Nobel Prize for stable matching?
- Lloyd Shapley and Alvin Roth shared the 2012 economics prize “for the theory of stable allocations and the practice of market design.” Shapley's part was the theory, including the 1962 paper with David Gale; Roth's was putting it to work for doctors and schools.
- Where else is stable matching used?
- The National Resident Matching Program has matched U.S. doctors to residencies with Roth and Peranson's applicant-proposing version since 1997. New York City switched high school admissions to an applicant-proposing version in 2003, and the number of students placed at a school they hadn't listed fell by 90 percent.