Lower Bounds for the Stable Marriage Problem and Its Variants

In an instance of the stable marriage problem of size n, n men and n women, each participant ranks members of the opposite sex in order of preference. A stable marriage is a complete matching M = \ (m₁, w_i₁), (m₂, w_i₂),⋯, (mₙ, w_iₙ)\ such that no unmatched man and woman prefer each other to their partners in M. There exists an efficient algorithm, due to Gale and Shapley, that finds a stable marriage for any given problem instance. A pair (mᵢ wⱼ) is stable if it is contained in some stable marriage. In this paper, the problem of determining whether an arbitrary pair is stable in a given problem instance is studied. It is shown that the problem has a lower bound of Ω (n²) in the worst case. Hence, a previous known algorithm for the problem is asymptotically optimal. As corollaries of these results, the lower bound of Ω (n²) is established for several stable marriage related problems. Knuth, in his treatise on stable marriage, asks if there is an algorithm that finds a stable marriage in less than Θ (n²) time. The results in this paper show that such an algorithm does not exist.