Computational Limits of Stable Matching with Constraints

This direction is merged into another direction: constrained matching complexity. Its last version stays readable and citable here.

Version 1 of 110 papers18 conceptsfrozen 2026-10-04

In the classic Stable Marriage problem, we seek a matching where no two people would rather be with each other than their assigned partners. When the market is bipartite (two distinct groups like "men" and "women" or "residents" and "hospitals"), the Gale-Shapley algorithm finds a stable solution efficiently. However, real-world markets are rarely this tidy. They involve roommates who don't fit into two camps, couples who insist on being matched together, and hospitals that must fill a minimum number of slots.

Recent research has shown that these "messy" real-world features often push the problem past a computational tipping point, making it not just difficult to solve exactly, but often impossible even to approximate.

The Roommate Problem and the Cost of Optimization

The Stable Roommates problem is the non-bipartite sibling of Stable Marriage. Here, any person can be matched with any other person. While finding any stable matching in this setting is computationally easy, the problem becomes difficult the moment we try to find the best one.

In Profile-based optimal stable matchings in the Roommates problem, Sofia Simola and David F. Manlove demonstrate that finding a stable matching that maximizes social welfare—such as rank-maximality (giving as many people their first choice as possible)—is NP-hard.

Crucially, this hardness persists even when agents have extremely short preference lists. One might assume that if everyone only lists three acceptable roommates, the search space would shrink enough to make the problem easy. However, Simola and Manlove show that even with a limit of three choices, the optimization remains intractable.

Why Couples Break the System

The most significant disruption to matching markets comes from couples. In medical residency matches, couples often submit joint preference lists, wanting to be in the same city or hospital. This creates a "linkage" that breaks the fundamental logic of standard matching algorithms.

In Couples can be tractable: New algorithms and hardness results for the Hospitals / Residents problem with Couples, authors including Gergely Csáji, Iain McBride, and James Trimble explore why this is so difficult. In a standard match, an agent’s rejection only affects their own status. With couples, one person being rejected from a hospital can "pull" their partner out of a different hospital, potentially displacing a third person and triggering a chain reaction that never settles into a stable state.

The research shows that determining if a stable matching even exists in the presence of couples is NP-hard. Furthermore, the authors find that it is NP-hard to even approximate a solution that minimizes the number of "blocking pairs" (dissatisfied pairs who would rather deviate). This suggests that in large-scale labor markets, simple heuristics are likely to fail to provide even nearly stable solutions.

The Search for Near-Stability

When a perfect stable matching is impossible to find or doesn't exist, the next logical step is to find an "almost" stable matching. This usually means minimizing the number of blocking pairs.

However, the computational boundaries here are strict:

  1. Roommates: Jiehua Chen, Manuel Sorge, and Danny Hermelin show in How Hard Is It to Satisfy (Almost) All Roommates? that minimizing blocking pairs in non-bipartite matching remains difficult even with short preference lists.
  2. Covering Constraints: Sometimes, we must ensure certain positions are filled (covering constraints). Ildikó Schlotter and Matthias Mnich established a trichotomy in Stable Marriage with Covering Constraints, categorizing these problems into those that are easy, those that are manageable for small parameters (FPT), and those that are fundamentally intractable. They highlight a major gap: we currently lack efficient algorithms to find matchings that satisfy these constraints while staying "close" to stable.

Frontiers of Tractability

Despite these hardness results, there are narrow paths to efficiency. Gergely Csáji and colleagues identified that if we allow for "near-feasible" matchings—for instance, by allowing hospital capacities to flex by just $\pm 1$—the problem of matching couples can sometimes become tractable. They also found that specific market structures, like "Dual Markets," allow for exact solutions where general markets do not.

The overarching lesson from this body of work is that stability is a fragile property. Adding even a small amount of real-world complexity—whether it's the non-bipartite nature of roommates or the joint preferences of couples—transforms a solvable puzzle into a landscape of computational intractability.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_computational_limits_of_stable_matching__b0c6a1a4,
  title = {Computational Limits of Stable Matching with Constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-limits-of-stable-matching-with-constraints/rdr_b0c6a1a4c86948ff84cc9db724b78f00},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_computational_limits_of_stable_matching__b0c6a1a4_v1,
  title = {Computational Limits of Stable Matching with Constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-limits-of-stable-matching-with-constraints/rdr_b0c6a1a4c86948ff84cc9db724b78f00/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}