Von Neumann-Morgenstern stability and internal closedness in matching theory
研究了匹配理论中基于内部稳定性的两类解集：冯·诺依曼-摩根斯坦稳定集和内部封闭集，在婚姻和室友模型中探讨其算法问题，发现婚姻模型中内部封闭集与稳定匹配同样易处理。
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.