How Gale-Shapley stable matching works, in plain English

The Gale-Shapley algorithm pairs up two groups of people using each person’s ranked preferences. One side makes offers in order of preference, and the other side holds on to the best offer so far until nobody has anyone left to ask. The result is always stable: no two people would both rather be with each other than with the partner they were given. It doesn’t promise that either person will like their match.

The method was published by David Gale and Lloyd Shapley in 1962, in a paper called “College Admissions and the Stability of Marriage“. Shapley shared the 2012 Nobel Memorial Prize in Economic Sciences with Alvin Roth “for the theory of stable allocations and the practice of market design” (Nobel Prize). In Singapore it’s best known from FirstDate, GovTech’s dating pilot for public officers, which uses it to make one match per cycle (CNA).

Steade uses stable matching too, so we have an interest here. We’ve kept this guide to how the method works and where it falls short, and we say how Steade uses it at the end.

What “stable” means

A set of pairs is stable when there’s no “blocking pair”: two people who aren’t matched to each other but who both prefer each other to the partners they got. If such a pair existed, they’d have every reason to leave their matches for each other.

Stable doesn’t mean everyone gets their first choice. Usually most people don’t. It means nobody is left with an obvious better option who would also choose them back.

How the algorithm works, step by step

Split everyone into two groups. Everyone ranks the people in the other group. Then one group proposes:

1. Everyone in the proposing group asks the person at the top of their list.
2. Everyone who gets one or more offers keeps the one they like best, on hold, and turns the rest down.
3. Anyone who was turned down asks the next person on their list. A person holding an offer swaps it if someone they prefer asks.
4. Repeat until nobody who is turned down has anyone left to ask.

Offers on hold are only final at the end, which is why economists call it “deferred acceptance”. Gale and Shapley proved that it always ends, and always ends with a stable set of pairs.

A worked example

Three people in each group. Each lists the other group from first choice to last.

Group 1	Ranks		Group 2	Ranks
Alex	Dana, Ella, Fay		Dana	Ben, Alex, Chris
Ben	Ella, Dana, Fay		Ella	Alex, Ben, Chris
Chris	Dana, Ella, Fay		Fay	Alex, Ben, Chris

Group 1 proposes.

• Round 1: Alex and Chris both ask Dana; Ben asks Ella. Dana prefers Alex, so she holds Alex and turns Chris down. Ella holds Ben.
• Round 2: Chris asks Ella. Ella prefers Ben, whom she’s already holding, so she turns Chris down.
• Round 3: Chris asks Fay, who holds him. Nobody is left without a match.

Result: Alex and Dana, Ben and Ella, Chris and Fay. Alex and Ben each got their first choice. Dana and Ella each got their second.

Now Group 2 proposes, with the same lists.

• Round 1: Dana asks Ben; Ella and Fay both ask Alex. Alex prefers Ella, so he holds her and turns Fay down. Ben holds Dana.
• Round 2: Fay asks Ben, who prefers Dana and turns her down.
• Round 3: Fay asks Chris, who holds her.

Result: Ben and Dana, Alex and Ella, Chris and Fay. This time Dana and Ella got their first choice, and Alex and Ben got their second.

Both results are stable. Check the first: Alex would rather have nobody but Dana, and has her. Ben has his first choice. Chris would prefer Dana or Ella, but both are with someone they rank above Chris. No blocking pair exists.

Who the algorithm favours

The example shows the catch. With the same preferences, the side that proposes does better. Gale and Shapley showed this holds in general: when one side proposes, each of its members gets the best partner they could have in any stable matching, and the other side gets the worst. The Nobel committee put it this way: the design of the method “may systematically benefit one or the other side of the market” (Nobel Prize).

This matters wherever it’s used. In the US medical residency match, which descends from this work, the National Resident Matching Program says its algorithm is “applicant-proposing”, so it favours applicants over hospitals (NRMP). In a dating service, the question of who proposes decides whether men or women get the better end of every round. When a service says it uses Gale-Shapley, it’s fair to ask which side proposes.

What stable matching can’t tell you

• Whether you’ll get on. A stable match follows from the lists people gave. It knows nothing about chemistry, timing or how a first conversation goes.
• Anything you didn’t say. If a questionnaire misses what matters to you, the matching can’t account for it.
• That you’ll get a match. When people only list partners they’d accept, some people end up unmatched. In every stable set of pairs, it’s the same people who are left out, so a cleverer algorithm can’t fix that; only more people who fit can.
• That everyone is honest. The proposing side can never do better by misstating its preferences. The other side sometimes can, in theory, though it takes detailed knowledge of everyone else’s lists.

How FirstDate uses it

FirstDate says it applies the Gale-Shapley algorithm to questionnaire answers about interests, habits, values and what you want in a partner, and gives each person one match per cycle (FirstDate). Matches come without photos (MS News). It’s open only to unmarried public officers aged 21 to 45. Our guide to FirstDate covers how it works and what you can use if you can’t join.

How Steade uses it

Steade introduces men and women, and builds each person’s list from what they told us. Two people are only on each other’s lists if each meets the other’s age range and dealbreakers, and both fit each other’s preferences well enough. Nothing is ranked on photos or popularity.

Steade doesn’t let one side propose. Each round starts with Gale-Shapley, then looks at every stable set of introductions and picks the one where the pairs fit each other best, judged mostly by the weaker side of each fit, with a small boost for people who have waited longer. Computer scientists Robert Irving, Paul Leather and Dan Gusfield published the method for searching all stable sets this way in 1987 (Journal of the ACM). The result is still stable, but neither men nor women are favoured by design.

Each introduction then shows up to three plain reasons, such as “You both want children”, rather than a score. The help centre has the details.

Frequently asked questions

What is the Gale-Shapley algorithm?

A method for pairing two groups using ranked preferences, published by David Gale and Lloyd Shapley in 1962. One side makes offers in order of preference, the other holds the best offer so far, and the process repeats until nobody has anyone left to ask. The result is always stable.

What does a stable match mean?

That no two people would both rather be with each other than with the partners they were given. It doesn’t mean anyone got their first choice, and it doesn’t predict whether a couple will get on.

Is Gale-Shapley fair to both sides?

Not by default. The side that proposes gets the best partner it could have in any stable matching, and the other side gets the worst. A service can reduce this by choosing a different stable set of pairs, which is what Steade does.

Does FirstDate use Gale-Shapley?

Yes. FirstDate, GovTech’s pilot for public officers aged 21 to 45, says it applies the Gale-Shapley algorithm to questionnaire answers to make one match per cycle.

Did Gale-Shapley win a Nobel Prize?

Lloyd Shapley shared the 2012 Nobel Memorial Prize in Economic Sciences with Alvin Roth for the theory of stable allocations and the practice of market design. David Gale died in 2008, and the prize isn’t awarded after death.

Related guides

• FirstDate Singapore explained, and what to do if you can’t join
• Best dating apps in Singapore (2026): who each one suits
• Dating in Singapore when you want something serious
• Compare: Steade vs FirstDate
• Help centre: How matching works · What the reasons on an introduction mean