Algorithmic Boundaries of Constrained Stable Matching

297 concepts136 papers1 proposal

In its classical formulation, matching theory is a triumph of algorithmic efficiency. The seminal Gale-Shapley deferred acceptance algorithm proves that we can find a stable matching—an allocation where no two agents prefer each other over their assigned partners—in polynomial time. This tractability relies on a beautiful mathematical structure: the set of stable matchings forms a distributive lattice, allowing local, monotonic choices to converge cleanly to a stable equilibrium.

However, real-world matching markets are rarely so unconstrained. Public housing allocation requires diversity quotas; hospital residency programs must accommodate couples; and school choice systems must balance budgets and financial aid.

When we inject these real-world constraints or attempt to optimize secondary global objectives, the underlying lattice structure shatters. This research direction maps the algorithmic boundaries of matching markets, revealing why seemingly minor modifications transform a computationally simple problem into an intractable one.

How Constraints Introduce Combinatorial Hardness

To understand why constraints break stable matching, consider how a standard matching algorithm operates. It processes ordinal preference lists independently, treating slots as interchangeable units. The moment we introduce constraints that span across multiple agents or slots, this independence vanishes.

Distributional and Capacity Quotas

In public housing or school choice, administrators often impose diversity quotas or group capacity limits. Nawal Benabbou et al. demonstrated in Diversity Constraints in Public Housing Allocation that enforcing hard capacity limits on specific agent subgroups transforms a polynomial-time task into an NP-complete one.

The intuition is structural: hard quotas force the algorithm to coordinate assignments globally rather than locally. An assignment that is perfectly stable for an individual pair might violate a group quota, requiring a cascade of reassignments. This global interdependence turns a simple selection process into a complex subset-sum or multi-dimensional knapsack problem.

Budgetary Constraints

A similar complexity explosion occurs when shifting from rigid seat quotas to financial budgets. In Approximately Stable Matchings With Budget Constraints, Yasushi Kawase shows that determining whether a stable matching even exists under budget constraints is NP-hard.

When institutions have financial budgets rather than physical seat capacities, individual agents carry different "costs" (e.g., varying salaries or financial aid requirements). The problem inherits the combinatorial hardness of the knapsack problem: the market designer is no longer just matching preferences, but trying to pack items of varying weights and values into a fixed space.

Interdependent Preferences

When agents' preferences are linked, the deferred acceptance mechanism fails completely. The most prominent example is the hospital-residents problem with couples, where two doctors submit joint preference lists over pairs of hospitals.

As Andrew Perrault et al. explore in SAT Is an Effective and Complete Method for Solving Stable Matching Problems with Couples, couples introduce dynamic cycles. If one member of a couple is rejected, the other member's preference instantly changes, potentially undoing dozens of previously stable allocations. This feedback loop eliminates the monotonicity that guarantees convergence, rendering the search for a stable solution NP-complete.

The Friction Between Local Stability and Global Optimization

In a standard matching market, stability is a local property determined entirely by individual pairs. However, market designers often want to optimize global properties, such as maximizing total social welfare, minimizing overall student dissatisfaction, or ensuring fairness between groups.

The fundamental conflict is that the objective functions for global optimality do not align with the iterative structures of local stability.

Local Stability (Individual Rationality)  <--->  Global Optimization (Social Welfare / Fairness)
       [No blocking pairs allowed]                      [Maximizing aggregate utility]

Optimizing Within the Stable Set

When preference lists include ties or financial terms, the set of stable outcomes can become large and diverse, as shown by Assaf Romm et al. in The Large Core of College Admission Markets: Theory and Evidence. While finding any stable matching remains easy, finding the largest or most optimal stable matching becomes NP-hard.

For instance, Jiehua Chen et al. proved in Fractional Matchings under Preferences: Stability and Optimality that maximizing social welfare under cardinal stability constraints is NP-hard, even in simple bipartite graphs without preference ties. The numerical utilities introduce a continuous optimization layer over a discrete combinatorial problem, forcing algorithms to navigate an exponential search space to find the welfare-maximizing frontier.

The Cost of Fairness

A similar barrier arises when trying to balance satisfaction between two sides of a market. The standard Gale-Shapley algorithm is notoriously biased, heavily favoring the proposing side while giving the receiving side their worst possible stable outcomes.

To remedy this, market designers look for "balanced" or "equitable" stable matchings. However, Nikolaos Tziavelis et al. show in Fair Procedures for Fair Stable Marriage Outcomes that minimizing the difference in average satisfaction between two groups is strongly NP-hard. Because the fairness objective function does not change monotonically as you move through the lattice of stable matchings, you cannot use simple greedy or iterative improvements; you are forced to evaluate an exponential number of stable configurations.

Given that exact, constrained stable matchings are frequently impossible to compute efficiently, researchers have shifted toward understanding what happens when we relax our definitions of stability or certainty.

Minimizing Instability

When an exact stable matching cannot be found due to conflicting constraints, a natural fallback is to find a matching that minimizes the number of "blocking pairs" (instabilities).

Unfortunately, this relaxation offers little computational relief. Gergely Csáji et al. demonstrated in Couples Can Be Tractable: New Algorithms and Hardness Results for the Hospitals/Residents Problem with Couples that minimizing or even approximating the minimum number of blocking pairs is computationally hard. Instability is highly non-local: changing a single edge to resolve one blocking pair can inadvertently create multiple new blocking pairs elsewhere in the network, making the optimization landscape treacherous and resistant to approximation.

The Weight of Uncertainty

In many real-world scenarios, preferences are not deterministic; they must be learned or are subject to noise. Haris Aziz et al. analyzed this in Stable Matching with Uncertain Linear Preferences, proving that calculating the exact probability that a matching remains stable under independent preference uncertainty is a #P-complete problem.

When preferences are probabilistic, verifying stability requires evaluating an exponential number of possible preference realizations. Consequently, finding the matching that maximizes the probability of stability becomes fundamentally intractable, forcing a reliance on stochastic sampling and heuristic approximations.

Summary of Intuition

The computational complexity of constrained matching boils down to a single core principle: structural alignment.

The classic stable matching problem is solvable in polynomial time because individual incentives align into a predictable, monotonic lattice structure. Introducing external constraints (like quotas or budgets), global objectives (like fairness or welfare maximization), or preference interdependencies (like couples or peer effects) breaks this alignment.

Once the lattice structure is destroyed, local choices no longer guarantee global stability, and the problem transforms into a combinatorial search over an exponential space of possibilities.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_constrained_matching_complexity_5c20ee81,
  title = {constrained matching complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constrained-matching-complexity/rdr_5c20ee8168d24cd9841cdd37a1691088},
  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_constrained_matching_complexity_5c20ee81_v1,
  title = {constrained matching complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constrained-matching-complexity/rdr_5c20ee8168d24cd9841cdd37a1691088/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake