In the classic Stable Marriage problem, the goal is simple: match two sets of agents such that no pair would rather be with each other than their current partners. The Gale-Shapley algorithm famously solves this in polynomial time. However, real-world markets—ranging from hospital residencies to summer internships and crowdsourcing platforms—rarely operate in a vacuum. They are governed by social networks, regional quotas, budget limits, and mandatory placements.
Recent research reveals a recurring theme: while basic stability is computationally "easy," adding even a single layer of real-world constraints often pushes the problem into the realm of NP-hardness. This body of work maps the boundary between what we can efficiently coordinate and what remains fundamentally intractable.
Stability Requires Communication
In traditional models, a matching is "unstable" if any man and woman prefer each other over their assigned partners. But this assumes every agent can communicate with every other agent to coordinate a "breakout." Georgios Askalidis and Emmanouil Pountourakis introduced the concept of Socially Stable Matchings to address this. They argue that a pair only "blocks" a matching if they are connected in a social network.
This relaxation is intuitive: if you don't know a better candidate exists, or have no way to reach them, you won't subvert your current assignment. While this allows for larger, more flexible matchings, Askalidis and David F. Manlove demonstrate that finding the maximum cardinality matching under these social constraints is NP-hard. The social network adds a layer of combinatorial complexity that prevents simple greedy or deferred-acceptance solutions from reaching the global optimum.
The Friction of Distributional Constraints
Beyond who knows whom, matching markets are often restricted by "distributional constraints"—external rules like diversity goals or regional quotas. Haris Aziz, Péter Biró, and Makoto Yokoo highlight a critical structural insight: the feasibility of these markets depends on how constraints overlap.
If constraints are nested (e.g., a quota for a specific hospital within a quota for a whole city), stable matchings are guaranteed to exist and can be found efficiently. However, if constraints are disjoint or overlapping (e.g., a budget that spans multiple independent projects), the search problem becomes NP-hard. This is further explored by Aziz and Anton Baychkov in the context of summer internships, where supervisor budgets—rather than just seat counts—limit placements. They show that while "strongly stable" matchings are computationally intractable in these settings, we can still find "weakly stable" ones by carefully allocating funds.
Mandatory Placements and Forbidden Pairs
Sometimes, the constraint isn't a global quota but a specific requirement for an individual edge. In many labor markets, certain interns must be placed (covering constraints), or certain pairings are strictly forbidden due to conflicts of interest.
Ildikó Schlotter and Matthias Mnich established a "computational trichotomy" for these covering constraints. They found that while some variations are solvable, minimizing the number of "blocking pairs" while satisfying mandatory matches is generally NP-hard. Similarly, Vladlena Powers and Yuri Faenza proved that even for "popular matchings"—a more relaxed fairness notion than stability—adding forced or forbidden edges makes finding the maximum weight matching NP-complete.
The Cost of Optimization
Even when we move away from discrete assignments to fractional matchings (where agents can share time or partners), complexity persists. Jiehua Chen and Manuel Sorge found that if we use "cardinal utilities" (numerical scores) instead of simple rankings, maximizing social welfare becomes NP-hard.
This suggests that the difficulty in modern matching theory isn't just about the "all-or-nothing" nature of assignments. Rather, it's the tension between stability (keeping individuals happy so they don't leave) and optimality (maximizing the total value of the system). As Andreas Darmann and Jérôme Lang show in the Group Activity Selection Problem, when preferences depend on the behavior of others—like "the more, the merrier"—the search for a perfect assignment that satisfies everyone is almost always a computational bottleneck.
Why It Works: The Geometry of Constraints
The reason these problems become hard is that constraints break the "lattice structure" of stable matchings. In a standard Gale-Shapley world, there is a clear mathematical structure that allows us to move from a man-optimal to a woman-optimal solution. Constraints act like obstacles in this landscape, turning a smooth path into a jagged maze where finding the "best" valid point requires checking an exponential number of possibilities.
By identifying which specific constraints (like nested hierarchies) preserve this structure and which (like disjoint budgets) destroy it, researchers are providing the blueprint for designing markets that are not only fair but actually solvable.