algorithm - 稳定匹配算法

Question

我正在阅读稳定的婚姻问题，偶然发现了这个问题：一个男人1的偏好列表中有没有女人1，女人1的偏好列表中有男人1，但仍然存在稳定的匹配（不一定男人最佳或女人最佳）他们没有配对在一起？

Answer 1

您所描述的情况听起来像一个稳定但不是非常稳定的案例。

来自“无差异的稳定婚姻结构”：如果没有夫妻 (x,y) 使得 x 在 M 中严格偏爱 y 而不是他/她的伴侣，并且 y 要么严格偏爱 x 而不是他/她的搭档……对于给定的 SMP 实例 I，保证存在弱稳定匹配：……另一方面，构造不承认强稳定匹配的 SMT 实例很简单。

所以听起来答案是肯定的……这是可能的。