TL;DR
This paper explores "internally closed" sets of matchings as a robust alternative to the classic Gale-Shapley stability criterion. The authors prove that while finding these sets is computationally efficient ($O(n^4)$) in bipartite "marriage" markets, it becomes NP-hard in the more general "roommate" model.
What Problem Does This Paper Address?
Since 1962, the Gale-Shapley stability criterion has dominated matching theory, powering everything from kidney exchanges to residency placements. However, standard stability is sometimes too restrictive; it can't always accommodate goals like maximizing the number of people matched or favoring one side of the market.
Researchers have long sought alternative "solution concepts," but most (like popularity or Pareto-optimality) lack the elegant algebraic structure that makes stable matchings easy to compute. This paper investigates internal stability—a concept introduced by game theory pioneers von Neumann and Morgenstern. Specifically, it looks at:
- vNM Stable Sets: Sets of matchings that are both internally stable (no matching in the set blocks another) and externally stable (any matching outside the set is blocked by one inside).
- Internally Closed Sets: A new, more flexible relaxation that simply requires the set to be an inclusion-wise maximal set of internally stable matchings.
The core challenge is determining whether these sets can be found efficiently or if they are doomed to computational complexity.
Methods
The authors bridge the gap between abstract game theory and algorithmic matching by extending classical algebraic tools:
- From Matchings to Edges: Because a set of matchings can be exponentially large, the authors represent them compactly using subtables of edges.
- Generalized Rotations: In the marriage model, they introduce "generalized rotations" and a process called "dissection." By iteratively "dissecting" or "vertically expanding" the poset (partially ordered set) of rotations, they can grow an internally stable set until it becomes internally closed.
- Stitched Rotations: For the roommate model, they define "stitched rotations"—complex structures that allow for the augmentation of stable matching sets.
- Complexity Analysis: They use reductions from 3-SAT to prove hardness results for the roommate model.
Datasets
Not discussed in the paper. As a theoretical contribution to mathematical programming, the work relies on formal proofs and algorithmic analysis rather than empirical testing on specific datasets.
Key Insights and Ideas
- Tractability of the Bipartite Case: The most significant "aha moment" is that internally closed sets in the marriage model are just as tractable as standard stable matchings. This is a "fairly rare occurrence" in the field, where alternative concepts usually break the nice mathematical properties of the original model.
- The Power of Rotations: The paper shows that the "rotation" structure—a staple of matching theory—is robust enough to describe not just stable matchings, but a much wider family of internally stable sets.
- The Roommate Divide: The paper reinforces the fundamental divide in matching theory: bipartite (marriage) models often yield polynomial-time solutions, while non-bipartite (roommate) models frequently collapse into NP-hardness when moving beyond basic stability.
Key Results
- Marriage Model: The authors provide an algorithm (Internal_Closure) that finds an internally closed set containing any given internally stable set in $O(n^4)$ time.
- Roommate Model Hardness:
- Deciding if a set of matchings is internally closed or vNM stable is co-NP-hard.
- Finding a vNM stable set is NP-hard.
- Existence: They demonstrate that while vNM stable sets might not even exist in some roommate instances (providing a 3-agent counter-example), an internally closed set always exists.
Limitations and Future Work
The authors acknowledge that while internally closed sets are mathematically elegant and tractable in bipartite settings, vNM stable sets remain elusive in the roommate model.
Future research directions suggested by the work include:
- Exploring whether these structural insights (generalized rotations) can be applied to more complex matching settings, such as many-to-one (college admissions) or many-to-many markets.
- Investigating the "price of internal closedness"—quantifying how much global utility is gained or lost when choosing these sets over standard Gale-Shapley stable matchings.
Summary updated