How to use the stable matching calculator
- Enter the first group with one line per member: a name, a colon and the names of the other group from most to least preferred.
- Enter the second group the same way, ranking every member of the first group.
- Both groups must have the same number of members, from 1 to 12, and each must rank everyone exactly once.
- Read the matching, the check for blocking pairs, the number of proposals, and the result when the other group proposes.
Formula
Each free member of the proposing group proposes to the best partner on the list who has not rejected them
A receiver holds the best proposal so far and rejects the others
The process ends when nobody is free, and the held proposals form the matching
A blocking pair is two members who prefer each other to their partners. A stable matching has none.
This is the Gale-Shapley method. It always finishes, never needs more than n squared proposals, and gives the best stable partner for every member of the proposing group.
Three pairs with cyclic preferences
A, B and C rank x, y and z in rotation so that each has a different first choice, and x, y and z rank them in a way that does not agree. When the first group proposes, A gets x, B gets y and C gets z, so every proposer has a first choice and the average rank is 1.00, after 3 proposals.
When the second group proposes instead, A gets z, B gets x and C gets y, a different matching, so more than one stable matching exists. A brute force check of all arrangements finds three stable matchings for this example. With two pairs and agreeing preferences the answer is the same either way.
Who proposes matters
The method favors the side that proposes. Every member of the proposing group gets the best partner they can have in any stable matching, and every member of the receiving group gets the worst. This is why the page shows the result for both sides. If the two results are the same, there is only one stable matching.
The method is used to place students in schools and residents in hospitals. For fair sharing of shifts, see the schedule fairness score calculator.
Checking your own work
The page lists the average rank each group gets, where 1 means first choice. Use it to compare outcomes of different preference lists. If you are working a homework problem, step through the proposals by hand and compare with the matching and the number of proposals.
For other algorithms to study, see the CPU scheduling simulator and the sorting algorithm operation counter.
Assumptions and limits
- Both groups have the same size, and each member ranks every member of the other group exactly once.
- Preferences are strict, with no ties, and are fixed in advance.
- The page handles up to 12 members in each group.
- The matching is stable by the rules of the method, which may not match fairness goals of a real placement.
Frequently asked questions
What is a stable matching?
It is a pairing in which no two members would both rather be with each other than with their current partners.
Is the matching unique?
Not always. The page shows what happens when each group proposes, and if the results differ, more than one stable matching exists.
What does the Gale-Shapley method guarantee?
It always finds a stable matching in a limited number of steps, and it is the best possible for the proposing side.
How do I write the preferences?
Write one member per line, like A: x y z, which means A prefers x, then y, then z. Use names without spaces.