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$
$\endgroup$
1
-
$\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$– Michael GreineckerCommented May 29, 2023 at 14:00
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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).
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).