论文标题
匹配理论中的内部封闭性和von Neumann-Morgenstern稳定性：结构和复杂性
Internal Closedness and von Neumann-Morgenstern Stability in Matching Theory: Structures and Complexity
论文作者
论文摘要
令$ g $为图形，假设我们得到了$ v（g）$中的每个$ v \，这是$ v $的邻居的严格订购。 $ g $的一组匹配$ {\ cal m} $如果没有匹配$ m，m'\ in {\ cal m} $，则称为内部稳定，这样$ m $ m $ blocks $ m'$。一组稳定的比赛（La Gale和Shapley）的比赛以及von Neumann-Morgenstern稳定匹配是内部稳定匹配的示例。在本文中，我们在婚姻和室友案中研究了内部稳定的比赛集合。我们将这些套装称为内部关闭。通过建立与一组匹配集相关的已知和新开发的代数结构，我们研究了确定一组匹配项是内部封闭还是von Neumann-Morgenstern稳定的复杂性，以及与这些属性的发现集。
Let $G$ be a graph and suppose we are given, for each $v \in V(G)$, a strict ordering of the neighbors of $v$. A set of matchings ${\cal M}$ of $G$ is called internally stable if there are no matchings $M,M' \in {\cal M}$ such that an edge of $M$ blocks $M'$. The sets of stable (à la Gale and Shapley) matchings and of von Neumann-Morgenstern stable matchings are examples of internally stable sets of matching. In this paper, we study, in both the marriage and the roommate case, inclusionwise maximal internally stable sets of matchings. We call those sets internally closed. By building on known and newly developed algebraic structures associated to sets of matchings, we investigate the complexity of deciding if a set of matchings is internally closed or von Neumann-Morgenstern stable, and of finding sets with those properties.
