betaFeedback

WorksComputer Science

A Sub-3n3^n Upper Bound on the Number of Stable Matchings

Abstract

We study the problem of determining the maximum number of stable matchings. This classical counting problem was posed by Knuth and has been studied for five decades. We obtain a new 2.999n2.999^n upper bound on the number of stable matchings with nn men and nn women. This improves the best-known previous result by Palmer and Pálvölgyi. This result gets much closer to the well-known lower bound 2.28npoly(n)\frac{2.28^n}{\text{poly}(n)}. We refine their entropy-based framework by capturing broader structural relationships among stable matchings. To capture these relationships, we introduce new frameworks, including cones and supports. This establishes the 3.332n3.332^n bound. We also exploit relationships among local structures and use a charging argument to improve the bound to 2.999n2.999^n.

Introduction

An instance of the stable matching problem consists of two equally sized sets of individuals, conventionally called men and women, together with each individual’s preference order over the members of the opposite set. A perfect matching pairs men with women so that every man and every woman belongs to exactly one pair. A blocking pair for a perfect matching is a man and a woman who each prefer the other to their current partner. A stable matching is a perfect matching with no blocking pair. Figure 1 shows examples of stable and unstable matchings.

Figure 1. Examples of a stable matching and an unstable matching containing a blocking pair.

In 1962, Gale and Shapley proved that a stable matching always exists and proposed an algorithm to find one [8]. With nn men and nn women, the Gale–Shapley algorithm runs in O(n2)O(n^2) time.

Research Background

The stable matching problem models finding a good matching between two sets according to their members’ preferences. It has many real-world applications, including matching medical residents to hospitals [18]. Shapley and Roth jointly received the 2012 Nobel Prize in Economic Sciences for their contributions to the theory of stable allocations and the practice of market design [20].

However, an instance may admit multiple stable matchings. This leads to the natural combinatorial problem of determining the maximum number of stable matchings in an instance with nn men and nn women. Knuth [16] posed this classical problem, and it is one of the twelve open problems listed in Gusfield and Irving’s book [7].

Maximum Number of Stable Matchings

Let f(n)f(n) denote the maximum number of stable matchings in an instance with nn men and nn women. In principle, f(n)f(n) can be determined by enumerating all preference profiles for nn men and nn women and counting the stable matchings in each instance. However, there are (n!)2n(n!)^{2n} preference profiles to examine, making this approach impractical as nn grows.

Maximum values for small nn. For n=4n = 4, Knuth [16] gave an instance with ten stable matchings [16], and Eilers [6] established f(4)=10f(4) = 10 through an exhaustive computer search [6]. For n=5n = 5, the maximum is 16 [5]. In very recent preprints, Jo claims to have established that

the maximum is 48 and 85 for n=6,7n = 6, 7, respectively [12, 11], and Xiu reports an alternative computational proof for n=6n = 6, together with a formalization of the entire proof in Lean [22]. However, for n≥8n \ge8, the exact value of f(n)f(n) remains unknown.

Asymptotic bounds. In addition to determining the maximum number of stable matchings for individual values of nn, researchers have studied the asymptotic behavior of f(n)f(n).

Several lower bounds on f(n)f(n) have long been known. A simple construction (see Figure 2) gives f(n)≥2⌊n/2⌋f(n) \ge2^{\lfloor n/2 \rfloor}. Irving and Leather [10] constructed instances with many stable matchings when nn is a power of two [10]. An analysis by Knuth, presented in the book by Gusfield and Irving, shows that these instances have at least 2.28n/(1+3)2.28^n/(1+\sqrt{3}) stable matchings [7]. Moreover, Thurber (2002) extends the construction to general nn, obtaining the lower bound 2.28npoly⁡(n)\frac{2.28^n}{\operatorname{poly}(n)} [21]. All of these lower bounds follow from explicit constructions.

Figure 2. An instance with at least 2⌊n/2⌋2^{\lfloor n/2 \rfloor} stable matchings.

Progress on upper bounds has accelerated more recently. In 2011, Stathopoulos proves that f(n)=O(n!/cn)f(n)=O(n!/c^n) [19], where c>1c>1 is a constant. This improves upon the trivial upper bound of n!n! by an exponential factor. In 2018, Karlin, Oveis Gharan, and Weber prove that, for all sufficiently large nn, f(n)f(n) is at most 217n2^{17n} [15], the first exponential upper bound. Furthermore, in 2021, Palmer and Pálvölgyi bound the number of stable matchings using the entropy of the uniform distribution on the set of stable matchings, claiming an upper bound of 3.55n+O(1)3.55^n+O(1) on f(n)f(n) [17]. However, at the end of their proof, we identify an error in their numerical evaluation [17 Claim 28]. Our recalculation yields an exponential base of slightly less than 4.01, rather than the reported 3.55; see Appendix § 11 for details1. In summary, the current known bounds for f(n)f(n) are

2.28npoly⁡(n)≤f(n)≤4.01n+O(1),\frac{2.28^n}{\operatorname{poly}(n)} \le f(n) \le4.01^n + O(1),

which still leaves a multiplicative gap (ratio) between the exponential bases of approximately 1.76.

Applications. Studying the maximum number of stable matchings also has algorithmic applications. First, it can be applied to the problem of enumerating all stable matchings. Although counting stable matchings is #P-complete [10], Gusfield gave an O(n2+n∣Ω∣)O(n^2+n|\Omega|)-time algorithm, where Ω\Omega denotes the set of stable matchings. Importantly, the running time depends on the number

of stable matchings. This means that improving the upper bound on f(n)f(n) of stable matchings also improves the time complexity bound for Gusfield’s enumeration algorithm; e.g., f(n)<3nf(n) < 3^n gives a worst-case running-time bound of O(n3n)O(n3^n) for this enumeration algorithm.

Second, this enumeration algorithm can also be used to solve optimization problems over stable matchings, such as Sex-Equal Stable Matching. This problem asks for a stable matching that minimizes the absolute difference between the sum of the ranks of the men’s partners in their preference lists and the corresponding sum for the women. Whether this problem admits a polynomial-time algorithm was also one of the twelve open problems listed in the book by Gusfield and Irving [7], and Kato [13] subsequently proved the NP-hardness. An optimal solution can be found by enumerating all stable matchings and evaluating the objective function for each. Thus, improving the upper bound on the maximum number of stable matchings also improves the worst-case running-time bounds for exact algorithms based on exhaustive enumeration.

Our Contributions

In this paper, we further improve the upper bound to 2.999n2.999^n. Formally, our main result is the following.

Theorem 1.1. Every stable matching instance with nn men and nn women admits fewer than 2.999n2.999^n stable matchings.

This improves the corrected 4.01n+O(1)4.01^n + O(1) upper bound obtained from [17]. The theorem holds for every n≥1n \ge1, rather than only for sufficiently large instances, and requires no additional correction term. Combined with Gusfield’s enumeration algorithm [9], the following corollary immediately holds.

Corollary 1.2. All stable matchings of an instance with nn men and nn women can be enumerated in O(n⋅2.999n)O(n \cdot2.999^n) time in the worst case.

Our result also applies to the Stable Roommates problem, which is a non-bipartite variant of the stable matching problem (i.e., each of nn participants has a preference ranking of n−1n - 1 other people). The construction of Dean and Munshi [4, 15] gives an injection from the stable matchings of a Stable Roommates instance with nn participants to those of a Stable Marriage instance with nn men and nn women. Thus, our result implies the following corollary.

Corollary 1.3. Every instance of the Stable Roommates problem with nn participants admits fewer than 2.999n2.999^n stable matchings.

Furthermore, our result also applies to the Popular Roommate problem, which asks for a matching that does not lose a majority vote against any other matching. This problem is known to be NP-hard even with complete preference lists [2]. Kavitha gave an algorithm that decides whether a Popular Roommates instance with nn vertices admits a solution in O∗((c+2c)n)O^*((c + 2\sqrt{c})^n) time, provided that every Stable Marriage instance with kk men and kk women has at most ckc^k stable matchings for every k≥1k \ge1 [14]. Therefore, since c+2c<6.463c + 2\sqrt{c} < 6.463 at c=2.999c = 2.999, our results imply the following corollary.

Corollary 1.4. There exists an O∗(6.463n)O^{*}(6.463^{n})-time algorithm to decide whether a Popular Roommates instance with nn vertices admits a popular matching.

Our proof for Theorem 1.1 builds on the framework of Palmer and Pálvölgyi [17] for bounding the number of stable matchings via entropy, incorporating additional combinatorial constraints arising from the rotation structure of stable matchings. In addition to bounding the number of candidates for each man separately, we obtain a stronger entropy bound by exploiting the frequencies of local structures that yield small entropy savings, as well as structural relationships among men and across different stable matchings.

Technical Overview

In this subsection, we present a technical overview of the proof of the upper bound 2.999n2.999^{n}. The proof proceeds through three successive upper bounds: 3.332n3.332^{n}, 3.060n3.060^{n}, and 2.999n2.999^{n}.

The Random-Reveal Model by PP22

We begin by introducing the random reveal model, which is a technique used in [17]. We let {m1,…,mn}\{m_1,\ldots,m_n\} be a set of men and {w1,…,wn}\{w_1,\ldots,w_n\} be a set of women.

Basic idea. Consider revealing the partner of each man mm, say μm\mu_m, in random order (see Figure 3). When revealing the first man’s partner, μmi1\mu_{m_{i_1}}, at most nn women are candidates. However, the number of candidates decreases significantly as the reveal progresses. For example, for the second man mi2m_{i_2}, there are at most n−1n-1 remaining candidates for the partner μmi2\mu_{m_{i_2}}, but many of them can be inconsistent with the matching already revealed, because a stable matching should not have any blocking pair. Therefore, for a fixed man mm, there are fewer candidates in expectation. If the expected logarithm of the number of candidates is less than δ\delta, an entropy argument yields an upper bound of (eδ)n(e^{\delta})^n on the number of stable matchings, e.g., 7.39n7.39^n when δ=2\delta=2. However, it is difficult to derive a useful upper bound on δ\delta directly, so they used the rotation of stable matching, which is well known and already introduced in [7].

Figure 3. The sketch of the random reveal model. With each partner reveal, the number of remaining candidates decreases dramatically.

Rotations in stable matchings. A rotation is a local operation that changes the local structure of stable matchings; see Figure 4 (a) for the sketch, and Definition 2.3–Definition 2.6 for a formal definition. Performing a rotation strictly worsens the partners of the men involved in the rotation,

Figure 4. (a) The sketch of a rotation, where rr is the rotation operation that changes (m1,w1)(m_1,w_1), (m2,w2)(m_2,w_2) to (m1,w2)(m_1,w_2), (m2,w1)(m_2,w_1). (b) The sketch of the rotation poset. (c) The sketch of the mm-chain.

while leaving the other men’s partners unchanged. The set of rotations forms a partially ordered set (poset) where each relation implies “a rotation r2r_2 can be performed only after a rotation r1r_1” (Figure 4 (b)). In addition, it is known that for each downset2 of rotation DD, performing its rotations from the man-optimal stable matching μm-opt\mu_{\mathrm{m\text{-}opt}} in any legal order yields the same stable matching. Furthermore, the downsets and stable matchings form a bijection.

A more useful property holds in rotations. For each fixed man mm, it is known that rotations involving mm form a chain, that is, for any two distinct rotations involving mm, one must be performed before the other (Figure 4 (c)). We call this mm-chain, and each chain contains less than nn rotations because each rotation strictly worsens the partner of mm.

Using mm-chain to derive upper bounds. We show how to use the mm-chain for the upper bound. Choose a stable matching μ\mu uniformly at random, independently of the reveal order, and let DD be the corresponding downset (as written above, downsets and stable matchings form a bijection). Let XmX_m be the number of rotations involving mm that are included in DD. Then, the stable matching μ\mu can be uniquely determined by Xm1,…,XmnX_{m_1},\ldots,X_{m_n}. This implies that the number of stable matchings is bounded by the maximum number of possible sequences (Xm1,…,Xmn)(X_{m_1},\ldots,X_{m_n}).

Now, let us use the random reveal property. Consider revealing Xm1,…,XmnX_{m_1},\ldots,X_{m_n} in a random order. For each man mm, if the expected logarithm of the number of candidates for XmX_m can be bounded by δ\delta, we obtain an (eδ)n(e^\delta)^n upper bound for the number of stable matchings.

Limitations. However, bounding the number of candidates for XmX_m is difficult. Therefore, [17] uses both the men’s mm-chains and the women’s ww-chains, where the ww-chain consists of the rotations involving woman ww. Our recalculation of the estimate in [17] bounds the expected logarithm by 0.6940.694 for sufficiently large nn, yielding the bound (e0.694)2n≈4.01n(e^{0.694})^{2n} \approx4.01^n because they used 2n2n chains. Palmer and Pálvölgyi [17 Section V] noted that reducing the number of components from 2n2n to nn is one possible route to improving the bound, although they considered a straightforward reduction unlikely.

New Techniques for the 3.332n3.332^n Bound (§ 3)

Next, we introduce our idea to reduce the number of chains to nn (i.e., using only the mm-chains) and achieve the 3.332n3.332^n bound. The core is to introduce the cone and the support as follows.

Cones and supports. Fix a downset DD and a man mm. For each k≥1k \ge1, let ρk\rho_k be the kk-th next rotation involving mm, not included in DD. Then, for each k≥1k \ge1, we define the kk-th principal cone KkK_k as “the set of rotations outside DD that must be performed to perform ρk\rho_k” (Figure 5 (a)). Note that KkK_k includes ρk\rho_k. In addition, define the support of a cone as the set of men involved in at least one rotation in a cone, and let s(k)s(k) be the size of the support of the principal cone KkK_k. Very importantly, s(k)≥k+1s(k) \ge k + 1 always holds; see Lemma 3.8 for the proof.

Figure 5. (a) An example of the first principal cone K1K_1, along with ρ1\rho_1 and ρ2\rho_2. (b) The sketch of our proof strategy.

How cones help. Next, we explain how to bound the number of candidates for XmX_m using cones. Let Tm(D)T_m(D) denote the actual value of XmX_m for a downset DD. Suppose that at least one man other than mm in the support of KkK_k has already been revealed. Then, just before revealing XmX_m, we can rule out any candidate values at least Tm(D)+kT_m(D) + k, only by the previously revealed information. Assign each man vv an independent priority Uv∼Unif⁡[0,1]U_v \sim\operatorname{Unif}[0,1], independently of DD, and reveal the values in increasing priority order. Conditional on DD and Um=xU_m = x, each other man has independently been revealed with probability xx, so

P[Tm(D)+k remains a candidate for Xm∣D,Um=x]≤(1−x)s(k)−1≤(1−x)k\mathbb{P}[T_m(D) + k \text{ remains a candidate for } X_m \mid D, U_m = x] \le(1-x)^{s(k)-1} \le(1-x)^k

References

  1. [1]Manuel Aprile, Alfonso Cevallos, and Yuri Faenza. “On 2-level polytopes arising in combinatorial settings”. In: SIAM Journal on Discrete Mathematics 32.3 (2018), pp. 1857–1886.
  2. [2]Ágnes Cseh and Telikepalli Kavitha. “Popular matchings in complete graphs”. In: Algorithmica 83.5 (2021), pp. 1493–1523.
  3. [3]Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Second. https://doi.org/10.1002/047174882X. Wiley, 2006. doi: 10.1002/047174882X.
  4. [4]Brian C Dean and Siddharth Munshi. “Faster algorithms for stable allocation problems”. In: Algorithmica 58.1 (2010), pp. 59–81.DOI
  5. [5]Dan Eilers. Sequence A357269: Maximum Number of Stable Matchings in the Stable Marriage Problem of Order n. The On-Line Encyclopedia of Integer Sequences. https://oeis.org/A357269. Accessed 27 October 2026. 2022.
  6. [6]Dan R. Eilers. Irvine Compiler Corporation Technical Report. Tech. rep. ICC TR1999-2. Irvine Compiler Corporation, 1999.
  7. [7]Dan Gusfield and Robert W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989. ISBN: 9780262071185.
  8. [8]David Gale and Lloyd S Shapley. “College admissions and the stability of marriage”. In: The American mathematical monthly 69.1 (1962), pp. 9–15.
  9. [9]Dan Gusfield. “Three fast algorithms for four problems in stable marriage”. In: SIAM Journal on Computing 16.1 (1987), pp. 111–128.
  10. [10]Robert W Irving and Paul Leather. “The complexity of counting stable marriages”. In: SIAM Journal on Computing 15.3 (1986), pp. 655–667.DOI
  11. [11]Myunglae Jo. A Computer-Assisted Proof That the Maximum Number of Stable Matchings of Order Seven Is 85. Zenodo preprint, version R2. 13 October 2026. https://doi.org/10.5281/zenodo.23329599. 2026. doi: 10.5281/zenodo.23329599.
  12. [12]Myunglae Jo. Small Rotation Blocks and the Order-Six Stable Marriage Problem. Zenodo preprint, version v09. 23 September 2026. https://doi.org/10.5281/zenodo.22909380. 2026. doi: 10.5281/zenodo.22909380.
  13. [13]Akiko Kato. “Complexity of the Sex-Equal Stable Marriage Problem”. In: Japan Journal of Industrial and Applied Mathematics 10.1 (1993). https://doi.org/10.1007/BF03167200, pp. 1–19. doi: 10.1007/BF03167200.
  14. [14]Telikepalli Kavitha. “Popular roommates in simply exponential time”. In: Algorithmica 87.2 (2025), pp. 292–320.DOI
  15. [15]Anna R Karlin, Shayan Oveis Gharan, and Robbie Weber. “A simply exponential upper bound on the maximum number of stable matchings”. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. 2018, pp. 920–925.arxiv.org/abs/1711.01032
  16. [16]Donald E. Knuth. Mariages stables et leurs relations avec d’autres problèmes combinatoires: Introduction à l’analyse mathématique des algorithmes. Les Presses de l’Université de Montréal, 1976.
  17. [17]Cory Palmer and Dömötör Pálvölgyi. “At most 3.55 n stable matchings”. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2022, pp. 217–227.
  18. [18]Alvin E. Roth. “The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory”. In: Journal of Political Economy 92.6 (1984). https://stanford.edu/~alroth/papers/evolut.pdf, pp. 991–1016.DOI
  19. [19]Georgios K. Stathopoulos. “Variants of Stable Marriage: Algorithms, Complexity and Structural Properties”. https://mpla.math.uoa.gr/media/theses/msc/Stathopoulos_G.pdf. MA thesis. University of Athens, Department of Mathematics, 2011.
  20. [20]The Royal Swedish Academy of Sciences. The Prize in Economic Sciences 2012: Press Release. NobelPrize.org. 15 October 2012. https://www.nobelprize.org/prizes/economic-sciences/2012/press-release/. 2012.
  21. [21]Edward G Thurber. “Concerning the maximum number of stable matchings in the stable marriage problem”. In: Discrete Mathematics 248.1-3 (2002), pp. 195–219.DOI
  22. [22]Yuran Xiu. A Formally Verified Certificate Proof of the Maximum Number of Stable Matchings for Six Men and Six Women. Hexagon preprint 2610.00262v2. 19 October 2026. https://hexagonmath.org/2610.00262v2. 2026.

Paper details

vlnc:W_f5xqayaq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-6 Astra, GPT-5.6 Sol (bare), GPT-6 Sol

View statement
Looking for related papers…
Contents