How it works, precisely
Everyone ranks ALL the other participants. There is only one group, so no asymmetry between proposers and receivers.
First phase: everyone proposes to the highest-ranked person who has not yet rejected them; improving proposals are provisionally accepted, worse ones rejected. This yields a reduced table.
Second phase: rotations — chains of cyclic preferences that block stability — are found and removed, until everyone has exactly one partner, or the table empties, which proves no solution exists.
The resulting matching is stable: no two people not paired together prefer each other to their current partner.
A worked example
Four people to pair up, each having ranked the other three.
| Person | 1st | 2nd | 3rd |
|---|---|---|---|
| Chloé | Ali | Bruno | Dana |
| Ali | Chloé | Dana | Bruno |
| Bruno | Dana | Chloé | Ali |
| Dana | Bruno | Ali | Chloé |
- Chloé and Ali put each other first: that pair is settled.
- Bruno and Dana do the same: second pair.
- No outside pair prefers each other: the matching is stable.
Here the preferences dovetail perfectly. Change a single ranking and the stable matching can disappear entirely — the fragility specific to this problem.
Where it comes from
The problem was posed in 1962 by David Gale and Lloyd Shapley, at the very end of their founding paper on stable marriage: what if, instead of two distinct groups, everyone belonged to the same set? They noted their algorithm does not apply, and left the question open.
They also proved that a stable matching may simply NOT EXIST — the essential difference from stable marriage, where one always does.
Robert Irving published the first polynomial-time algorithm in 1985: it determines whether a stable solution exists and constructs it if so, in two phases, the second of which methodically eliminates « rotations ».
Where it is used
- Forming pairs for work, review or pair programming.
- Allocating flatmates or roommates.
- Pairing training or tournament partners.
- Organising peer mentoring, with no hierarchy between the two roles.
Limits and pitfalls
- No pair wants to "run off" together
- Based on both sides' preferences
- Honestly detects impossible cases
- A stable pairing doesn't always exist
- Requires an even count
- Ranking everyone can take a while
Frequently asked questions
What happens if no stable solution exists?
The tool says so plainly. That is real information about the group: preferences form an irreducible cycle. It is then up to you — pair by declared affinity, or accept a known instability.
How does this differ from two-sided Gale-Shapley?
Gale-Shapley assumes two distinct sets ranking each other (candidates and programmes) and always guarantees a solution. Here everyone is in the same set, so no side is favoured — but the existence guarantee is gone.
What exactly does « stable » mean?
That no two people who are not paired together would both prefer each other to their current partner. Such a pair would leave the arrangement: stability is precisely what prevents that.