25

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?

QuietThud
  • 149
  • 5
asc
  • 353
  • 1
  • 3
  • 4

5 Answers5

25

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

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

gstat
  • 343
  • 2
  • 7
9

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

domotorp
  • 13,931
  • 37
  • 93
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

Snowie
  • 1,200
  • 7
  • 10
  • 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}$ – domotorp Mar 26 '11 at 20:26
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.

Joseph Malkevitch
  • 1,319
  • 6
  • 7