Unsolvability and Beyond in Many-to-Many Non-bipartite Stable Matching
ACM Transactions on Economics and Computation · 02.05.2026
DOI: 10.1145/3814616 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Economics and Computation, online erschienen am 02.05.2026. Verfasst von Frederik Glitzner und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 47 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
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}
}
EUVIMED