EUVIMEDOpdag EUVIMED
Crossref

Unsolvability and Beyond in Many-to-Many Non-bipartite Stable Matching

Frederik Glitzner, David Manlove

ACM Transactions on Economics and Computation · 2026-05-02

DOI: 10.1145/3814616 ↗

At a glance

Journal article in ACM Transactions on Economics and Computation, published online on 2026-05-02. Written by Frederik Glitzner and 1 co-authors. Cited 1 times so far (Crossref); 47 references.

AbstractBibliografiske oplysningerCiteRelated studies

Abstract (original language)

We study the Stable Fixtures problem, a many-to-many generalisation of the classical non-bipartite Stable Roommates matching problem. Building on the foundational work of Tan on stable partitions, we extend his results to this significantly more general setting and develop a rich framework for understanding stable structures. Our main contribution, the notion of a generalised stable partition (GSP) , not only characterises the solution space but also serves as a versatile tool for ordinal preference systems with capacity constraints. We show that a GSP can be computed efficiently and can provide an elegant representation of key aspects of a preference system. Leveraging a connection to stable half-matchings, we also establish an analogous Rural Hospitals Theorem for stable half-matchings and GSPs, and connect our results to recent work on near-feasible matchings, providing a simpler algorithm and tighter analysis. Our work also addresses the computational challenges of finding optimal stable half-matchings and GSPs, presenting a flexible integer linear programming model for various objectives. Beyond theoretical insights, we conduct the first empirical analysis of random Stable Fixtures instances. Our work unifies and extends classical and recent perspectives on stability in non-bipartite stable matching and establishes new tools and techniques for stable matchings and their applications.

Cite

APA

Glitzner, F., & Manlove, D. (2026). Unsolvability and Beyond in Many-to-Many Non-bipartite Stable Matching. ACM Transactions on Economics and Computation. https://doi.org/10.1145/3814616

Vancouver

Glitzner F, Manlove D. Unsolvability and Beyond in Many-to-Many Non-bipartite Stable Matching. ACM Transactions on Economics and Computation. 2026. doi:10.1145/3814616

BibTeX
@article{Glitzner2026,
  author = {Glitzner, Frederik and Manlove, David},
  title = {Unsolvability and Beyond in Many-to-Many Non-bipartite Stable Matching},
  journal = {ACM Transactions on Economics and Computation},
  year = {2026},
  doi = {10.1145/3814616}
}
Start for free →