Islands of Stability: Tractable Lattice Structures for No-Regret Learning of Super-Stable Matchings

The stable matching problem has long served as a foundational model for two-sided market design, yet classical solutions assume that complete preference orderings are known in advance. We study an online version of this setting, motivated by the challenges of learning a stable matching in a repeated game—specifically as it relates to super stability and efficient learning under partial information. Our model is designed to operate directly on pairwise comparative feedback, making it practical in settings where agents observe only comparative outcomes. This forms a more natural representation of preference elicitation, obviating the need to assign ordinal scores to outcomes (common in previous work). Operating on direct pairwise feedback, we first present a learning algorithm, $P2ETG$, with provable sublinear regret guarantees with respect to achieving any stable matching. Next, as a crucial extension, we present $\mathsf{PrefLID}$, an algorithm which exploits the lattice structure of stable matchings and the concept of super-stability, connecting common stable matchings among different refinements of a bipartite partial order into connected graphs, called islands. We demonstrate that these islands reveal structural properties of the preference-refinement space that can be exploited for more efficient super-stable matching search over partial orders. This allows $\mathsf{PrefLID}$ to sample more efficiently, making only the pairwise comparisons needed to resolve the problem structure within a single island. We provide a tractable means to construct this island structure, enabling its use in an efficient online setting and demonstrating that it achieves no-regret performance while avoiding full preference resolution. We illustrate the applicability of our approach through a natural application to LLM routing, where agents must be matched to tasks in a streaming setting, and further provide corresponding empirical results to corroborate the theoretical properties.