<p>An upper bound on the maximum number of stable matchings for a Stable Marriage instance is given in my Master's thesis and it is extended to the Stable Roommates problem as well.The bound is of magnitude $O(n!/2^n)$ and it can be shown that it is actually of magnitude $O\left((n!)^\frac{2}{3}\right)$.</p>

<p>The document is thesis number 97 on page <a href="http://mpla.math.uoa.gr/msc/">http://mpla.math.uoa.gr/msc/</a></p>

CC BY-SA 3.0
2011-12-26T23:07:52.840Z
2012-03-28T19:48:19.030Z
2012-03-28T19:48:19.030Z
gstat
<p>An exponential upper bound has been given in <a href="https://arxiv.org/abs/1711.01032" rel="nofollow noreferrer">Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber: A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings</a>.</p>
<p>Later the base of the constant has been <a href="https://arxiv.org/abs/2011.00915" rel="nofollow noreferrer">improved, so the best upper bound is <span class="math-container">$3.55^n+O(1).$</span></a></p>

CC BY-SA 4.0
2018-01-15T11:33:42.663Z
2022-03-22T06:34:29.127Z
2022-03-22T06:34:29.127Z
domotorp
<p>It is well known that an instance of $n$ men/women can have an exponential number ($O(2^n)$) of stable matchings, but giving a tight upper bound is still open.  See Encyclopedia of algorithms <a href="http://rads.stackoverflow.com/amzn/click/0387307702" rel="nofollow">http://www.amazon.com/dp/0387307702</a></p>

CC BY-SA 2.5
2011-03-26T20:26:58.193Z
The sentence is misleading, but I think it only claims an exponential lower bound:
One of the open problems posed by Knuth in his early
monograph on stable marriage [11] was that of determining
the maximum possible number xn of stable matchings
for any SM instance involving n men and n women. This
problem remains open, although Knuth himself showed
that xn grows exponentially with n. Irving and Leather [8]
conjecture that, when n is a power of 2, this function satisfies
the recurrence
$x_n = 3x^2_{n/2} - 2x^4_{n/4}$
domotorp
CC BY-SA 2.5
2011-03-24T15:17:05.563Z
2011-03-24T15:46:16.927Z
2011-03-24T15:46:16.927Z
Snowie
<p>Interesting results on this issue can be found on pages 24 and 25 of the book: The Stable Marriage Problem by Dan Gusfield and Robert Irving, MIT Press, 1989.</p>

CC BY-SA 2.5
2011-03-26T02:58:00.390Z
2011-03-26T02:58:00.390Z
Joseph Malkevitch
<p>For an instance with $n$ men and $n$ women, the trivial upper bound is $n!$, and nothing better is known. For a lower bound, <a href="http://www-cs-faculty.stanford.edu/~uno/ms.html">Knuth (1976)</a> gives an infinite family of instances with $\Omega(2.28^n)$ stable matchings, and <a href="http://dx.doi.org/10.1016/S0012-365X%2801%2900194-7">Thurber (2002)</a> extends this family to all $n$.</p>

CC BY-SA 3.0
2012-01-11T14:12:37.730Z
Actually, I believe that this family of instances (for powers of two) is due to Irving and Leather and that Knuth has proved that the recurrence relation satisfied by this family is $\Omega(2.28^n)$
gstat
CC BY-SA 3.0
2012-01-11T14:20:01.730Z
R.W. Irving and P. Leather. The complexity of counting stable marriages. SIAM Journal on Computing, 15:655-667,1986
gstat
CC BY-SA 4.0
2021-07-13T06:33:24.593Z
@JohnRed, No, this is a lower bound in the sense that there are instances with this many stable marriages. It is not a smaller upper bound.
Serge Gaspers
CC BY-SA 4.0
2021-01-31T19:10:15.627Z
I was confused by the "For a lower bound" phrase. Shouldn't it rather be, "For a tighter/smaller upper bound"?
John Red
CC BY-SA 2.5
2011-03-24T17:40:54.990Z
2011-03-24T17:40:54.990Z
Serge Gaspers
<p>Stable Marriage Problem: <a href="http://en.wikipedia.org/wiki/Stable_marriage_problem" rel="noreferrer">http://en.wikipedia.org/wiki/Stable_marriage_problem</a></p>

<p>I am aware that for an instance of a SMP, many other stable marriages are possible apart from the one returned by the Gale-Shapley algorithm. However, if we are given only $n$ , the number of men/women, we ask the following question - Can we construct a preference list that gives the maximum number of stable marriages? What is the upper bound on such a number?</p>

<ds.algorithms><co.combinatorics><graph-algorithms><heuristics><matching>
What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?
asc
# What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?

(Asked by: username_0 on 2011-03-24)

Stable Marriage Problem: <http://en.wikipedia.org/wiki/Stable_marriage_problem>

I am aware that for an instance of a SMP, many other stable marriages are possible apart from the one returned by the Gale-Shapley algorithm. However, if we are given only $n$ , the number of men/women, we ask the following question - Can we construct a preference list that gives the maximum number of stable marriages? What is the upper bound on such a number?

**Tags:** ds.algorithms, co.combinatorics, graph-algorithms, heuristics, matching


---

## 5 answers

### Answer by username_5 on 2011-03-24. Score: 26 | Accepted answer

For an instance with $n$ men and $n$ women, the trivial upper bound is $n!$, and nothing better is known. For a lower bound, [Knuth (1976)](http://www-cs-faculty.stanford.edu/~uno/ms.html) gives an infinite family of instances with $\Omega(2.28^n)$ stable matchings, and [Thurber (2002)](http://dx.doi.org/10.1016/S0012-365X%2801%2900194-7) extends this family to all $n$.

> **Comments:**
> **username_1**: Actually, I believe that this family of instances (for powers of two) is due to Irving and Leather and that Knuth has proved that the recurrence relation satisfied by this family is $\Omega(2.28^n)$  
> **username_1**: R.W. Irving and P. Leather. The complexity of counting stable marriages. SIAM Journal on Computing, 15:655-667,1986  
> **username_6**: I was confused by the "For a lower bound" phrase. Shouldn't it rather be, "For a tighter/smaller upper bound"?  
> **username_5**: @JohnRed, No, this is a lower bound in the sense that there are instances with this many stable marriages. It is not a smaller upper bound.  

---

### Answer by username_1 on 2011-12-26. Score: 18

An upper bound on the maximum number of stable matchings for a Stable Marriage instance is given in my Master's thesis and it is extended to the Stable Roommates problem as well.The bound is of magnitude $O(n!/2^n)$ and it can be shown that it is actually of magnitude $O\left((n!)^\frac{2}{3}\right)$.

The document is thesis number 97 on page <http://mpla.math.uoa.gr/msc/>


---

### Answer by username_2 on 2018-01-15. Score: 10

An exponential upper bound has been given in [Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber: A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings](https://arxiv.org/abs/1711.01032).

Later the base of the constant has been [improved, so the best upper bound is $3.55^n+O(1).$](https://arxiv.org/abs/2011.00915)


---

### Answer by username_3 on 2011-03-24. Score: 4

It is well known that an instance of $n$ men/women can have an exponential number ($O(2^n)$) of stable matchings, but giving a tight upper bound is still open. See Encyclopedia of algorithms [http://www.amazon.com/dp/0387307702](http://rads.stackoverflow.com/amzn/click/0387307702)

> **Comments:**
> **username_2**: The sentence is misleading, but I think it only claims an exponential lower bound: One of the open problems posed by Knuth in his early monograph on stable marriage [11] was that of determining the maximum possible number xn of stable matchings for any SM instance involving n men and n women. This problem remains open, although Knuth himself showed that xn grows exponentially with n. Irving and Leather [8] conjecture that, when n is a power of 2, this function satisfies the recurrence $x_n = 3x^2_{n/2} - 2x^4_{n/4}$  

---

### Answer by username_4 on 2011-03-26. Score: 1

Interesting results on this issue can be found on pages 24 and 25 of the book: The Stable Marriage Problem by Dan Gusfield and Robert Irving, MIT Press, 1989.


---

