<p>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.</p>
<p>The set of stable matchings form a distributive lattice. The following is Figure 2.1 in Roth, A. E., &amp; Sotomayor, M. (1990). Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Each of those numbers denote a stable matching. <span class="math-container">$1$</span> is the men-optimal stable matching (as well as the women-pessimal) while <span class="math-container">$10$</span> is the women-optimal stable matching (and men-pessimal).</p>
<p><a href="https://i.sstatic.net/65gpYKEB.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/65gpYKEB.png" alt="lattice structure" /></a></p>
<p>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 (<span class="math-container">$1$</span>) and one stable matching they collectively prefer the least (<span class="math-container">$10$</span>). 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).</p>

CC BY-SA 4.0
2024-05-15T15:54:12.040Z
2024-05-15T15:54:12.040Z
cottontail
<p>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?</p>

CC BY-SA 4.0
2023-05-29T14:00:14.047Z
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.
Michael Greinecker
<mathematical-economics><mechanism-design><algorithms><matching>
Does the Gale-Shapley algorithm provide just one allocation?
userF
# Does the Gale-Shapley algorithm provide just one allocation?

(Asked by: username_0 on 2023-05-28)

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?

**Tags:** mathematical-economics, mechanism-design, algorithms, matching
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2024-05-15. Score: 0

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](https://i.sstatic.net/65gpYKEB.png)](https://i.sstatic.net/65gpYKEB.png)

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).


---

