I know that in a marriage problem for example, you may have more than one stable allocation but I think that the Gale-Shapley algorithm just provide only one. Am I right? Does the Gale-Shapley algorithm provide a single matching?

  • $\begingroup$ In the usual setting with strict preferences, there is one for each proposing side. These two allocations coincide if and only if there is a unique stable matching. $\endgroup$ Commented May 29, 2023 at 14:00

1 Answer 1


TL;DR: Each problem may have multiple stable matchings but Gale-Shapley's algorithm produces a unique outcome that is optimal for the proposing side.

The set of stable matchings form a distributive lattice. The following is Figure 2.1 in Roth, A. E., & Sotomayor, M. (1990). Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Each of those numbers denote a stable matching. $1$ is the men-optimal stable matching (as well as the women-pessimal) while $10$ is the women-optimal stable matching (and men-pessimal).

lattice structure

The left lattice is the hierarchy of stable matchings due to men's preferences. Men have a unique stable matching they collectively prefer over all stable matchings ($1$) and one stable matching they collectively prefer the least ($10$). At the same time, women collectively have the exact opposite preference over the set of stable matching (which is shown on the lattice on the right).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.