Stable matchings under relaxed random preferences

In a stable matching problem, n agents on one side have individual preferences for n agents on another side as a potential match. A matching is called stable if no two unmatched agents prefer each other to their matches. Knuth demonstrated existence of preferences with exponentially many stable matchings, posing a question on expected number of stable matchings for a uniformly random problem instance. Using Knuth’s integral formula, the first author showed that this expectation is quite moderate, asymptotic to e⁻¹nlog n , n being the number of agents on each side. In this paper, relaxing stability notion, we declare matching stable if no unmatched pair of agents strongly prefer each other to their partners, with “strength” measured by a parameter ε >0 , ε =0 corresponding to classic stability. The expected number of ε -stable matchings is proved to be polynomially large if ε of order n⁻¹log n , but it explodes to become super-polynomially large once ε n⁻¹log n .