A Quadratic Lower Bound for Stable Roommates Solvability

2^nd May 2025, 13:00
Will Rosenbaum

Abstract

The Stable Marriage Problem (SM) considers two disjoint sets of agents where the agents of each set rank the agents of the other set. The goal is to find a matching between the sets that is stable in the sense that no pair of agents prefer one another to their assigned partners. In a seminal work, Gusfield and Irving showed that stable matchings always exist and devised an efficient algorithm for finding one.

We consider a variant of SM known as the Stable Roommates Problem (SR) in which there is only one set of agents and each agent ranks all other agents in the set. Unlike SM, an SR instance may not admit a stable matching. In 1987, Irving devised an algorithm that finds a stable matching or reports that none exists in time $O(n^2)$ for instances with $n$ agents. In this talk, we will show that any algorithm that decides SR solvability---the task of deciding if given preferences admit a stable matching---requires $\Omega(n^2)$ Boolean queries to the agents' preferences. This lower bound implies that Irving's algorithm is optimal for SR solvability (up to a logarithmic factor), and resolves an open question of Irving and Leather from 1989. The main result follows from a simple reduction from the communication complexity of the set disjointness function.