matchmaking - 强稳定、弱稳定和超稳定匹配有什么区别？

Question

我冷漠地阅读稳定婚姻问题（SMP，https://en.wikipedia.org/wiki/Stable_marriage_problem），我遇到了强稳定、弱稳定和超稳定匹配这些术语。它们之间有什么区别？

Answer 1

在我看来，它们是三种稳定的匹配状态，在偏好列表上与关系匹配的要求不同。

其中超级稳定是最严格的，然后是强稳定，弱稳定最后限制最少。

假设有一对流氓夫妇（m，w）在匹配中不匹配，他们会在以下情况下破坏匹配的属性：

• 如果 m严格偏爱 (>) w 而不是他当前的合作伙伴，并且 w严格偏爱 m 而不是她当前的合作伙伴，则匹配甚至不是 弱稳定匹配。
• 如果 m比他当前的伙伴更喜欢 (>) w 并且 w 认为 m不比(>=) 她当前的伙伴差，则匹配不可能是强稳定匹配。
• 如果 m 认为 w不比(>=) 他当前的伙伴差，并且 w严格地偏爱 (>) m 而不是她当前的伙伴，则匹配也不能是强稳定匹配。
• 如果 m 认为 w不比(>=) 他当前的伙伴差，并且 w 认为 m不比(>=) 她当前的伙伴差，则匹配将不再是超稳定匹配。