Recently MV18a identified and initiated work on the new problem of understanding structural relationships between the lattices of solutions of two ``nearby'' instances of stable matching. They also gave an application of their work to finding a robust stable matching. However, the types of changes they allowed in going from instance $A$ to $B$ were very restricted, namely, any one agent executes an upward shift. In this paper, we allow any one agent to permute its preference list arbitrarily. Let $M_A$ and $M_B$ be the sets of stable matchings of the resulting pair of instances $A$ and $B$, and let $\mathcal{L}_A$ and $\mathcal{L}_B$ be the corresponding lattices of stable matchings. We prove that the matchings in $M_A \cap M_B$ form a sublattice of both $\mathcal{L}_A$ and $\mathcal{L}_B$ and those in $M_A \setminus M_B$ form a join semi-sublattice of $\mathcal{L}_A$. These properties enable us to obtain a polynomial time algorithm for not only finding a stable matching in $M_A \cap M_B$, but also for obtaining the partial order, as promised by Birkhoff's Representation Theorem, thereby enabling us to generate all matchings in this sublattice. Our algorithm also helps solve a version of the robust stable matching problem. We discuss another potential application, namely obtaining new insights into the incentive compatibility properties of the Gale-Shapley Deferred Acceptance Algorithm.
翻译:最近,MV18a确定并开始研究了稳定匹配的两个“近邻”实例的解的格之间的结构关系问题。他们还将他们的工作应用于寻找鲁棒的稳定匹配。但是,他们在从实例$A$到$B$的变化类型非常有限,即任何一个代理都需要执行向上的位移。在本文中,我们允许任何一个代理将其偏好列表任意置换。让$M_A$和$M_B$分别为得到的实例$A$和$B$的稳定匹配集合,让$\mathcal{L}_A$和$\mathcal{L}_B$为相应的稳定匹配格。我们证明了$M_A\cap M_B$中的匹配形成了$\mathcal{L}_A$和$\mathcal{L}_B$的子格,并且$M_A\setminus M_B$中的匹配形成了$\mathcal{L}_A$的半格。这些属性使我们能够不仅在$M_A\cap M_B$中找到一个稳定的匹配,而且还能够像Birkhoff的表示定理承诺的那样得到偏序,从而使我们能够生成这个子格中的所有匹配。我们的算法还有助于解决鲁棒性稳定匹配问题的一个版本。我们讨论了另一个可能的应用,即对Gale-Shapley延迟接受算法的激励兼容属性获得新的洞见。