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 in many-to-many contexts. Our main contribution, the notion of a generalised stable partition (GSP), not only characterises the solution space of this problem, but also serves as a versatile tool for reasoning about 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 a non-bipartite analogue of the 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 for this problem. Beyond structural insights, we conduct the first empirical analysis of random Stable Fixtures instances, uncovering surprising results, such as the impact of capacity functions on the solvability likelihood.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Frederik Glitzner,
  • David Manlove

摘要

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 in many-to-many contexts. Our main contribution, the notion of a generalised stable partition (GSP), not only characterises the solution space of this problem, but also serves as a versatile tool for reasoning about 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 a non-bipartite analogue of the 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 for this problem. Beyond structural insights, we conduct the first empirical analysis of random Stable Fixtures instances, uncovering surprising results, such as the impact of capacity functions on the solvability likelihood.