Lower Bounds for the Stable Marriage Problem and Its Variants

Abstract

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_{1}, w_{i_{1}}), (m_{2}, w_{i_{2}}),\cdots, (m_{n}, w_{i_{n}})\}$ 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_{i} w_{j})$ 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 $\Omega (n^{2})$ in the worst case. Hence, a previous known algorithm for the problem is asymptotically optimal. As corollaries of these results, the lower bound of $\Omega (n^{2})$ 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 $\Theta (n^{2})$ time. The results in this paper show that such an algorithm does not exist.