25
$\begingroup$

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?

Improve this question
$\endgroup$
0

5 Answers 5

Reset to default
25
$\begingroup$

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) gives an infinite family of instances with $\Omega(2.28^n)$ stable matchings, and Thurber (2002) extends this family to all $n$.

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ 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)$ $\endgroup$
    – gstat
    Jan 11, 2012 at 14:12
  • 1
    $\begingroup$ R.W. Irving and P. Leather. The complexity of counting stable marriages. SIAM Journal on Computing, 15:655-667,1986 $\endgroup$
    – gstat
    Jan 11, 2012 at 14:20
  • $\begingroup$ I was confused by the "For a lower bound" phrase. Shouldn't it rather be, "For a tighter/smaller upper bound"? $\endgroup$
    – John Red
    Jan 31, 2021 at 19:10
  • $\begingroup$ @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. $\endgroup$
    – Serge Gaspers
    Jul 13, 2021 at 6:33
18
$\begingroup$

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/

Improve this answer
$\endgroup$
9
$\begingroup$

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.

Later the base of the constant has been improved, so the best upper bound is $3.55^n+O(1).$

Improve this answer
$\endgroup$
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ 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}$ $\endgroup$
    – domotorp
    Mar 26, 2011 at 20:26
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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