Von Neumann-Morgenstern stability and internal closedness in matching theory

Yuri Faenza, Clifford Stein, Jia WanMathematical 2025 · DOI

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:

  1. 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).
  2. 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

Abstract

Abstract Gale and Shapley’s stability criterion enjoys a rich mathematical structure, which propelled its application in various settings. Although immensely popular, the approach by Gale and Shapley cannot encompass all the different features that arise in applications, motivating the search for alternative solution concepts. We investigate alternatives that rely on the concept of internal stability, a notion introduced for abstract games by von Neumann and Morgenstern and motivated by the need of finding a set of mutually compatible solutions. The set of stable matchings is internally stable. However, the class of internally stable sets is much richer, for an internally stable set of matchings may also include unstable matchings and/or exclude stable ones. In this paper, we focus on two families of internally stable sets of matchings: von Neumann-Morgenstern stable and internally closed . We study algorithmic questions around those concepts in both the marriage and the roommate models. One of our results implies that, in the marriage model, internally closed sets are an alternative to stable matchings that is as tractable as stable matchings themselves, a fairly rare occurrence in the area. Both our positive and negative results rely on new structural insights and extensions of classical algebraic structures associated with sets of matchings, which we believe to be of independent interest.
BibTeX
@inproceedings{faenza2025von,
  author = {Yuri Faenza and Clifford Stein and Jia Wan},
  title = {{Von Neumann-Morgenstern stability and internal closedness in matching theory}},
  booktitle = {Mathematical},
  year = {2025},
  doi = {10.1007/s10107-025-02292-3},
}
Figure