Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

4 Answers

up vote 19 down vote accepted

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

share|improve this answer
2  
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
    
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
add comment

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/

share|improve this answer
add comment

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

share|improve this answer
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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