stable-marriage - 什么是稳定匹配？

Question

所以我的问题是指什么是“稳定匹配”？我知道稳定婚姻问题，所有解决方案似乎都表明您以“稳定匹配”结束。但我不确定这实际上意味着什么。

Answer 1

我会盯着 wiki 中的.gif 文件，因为它实际上是对机制的一个很好的解释。

在稳定匹配中，我们保证将两组（男人和女人、儿童和玩具、人和度假胜地等）中的所有元素与另一组中的元素放在一对中，并且该对是“最佳可用匹配”

我们确定什么是“最佳可用匹配”的方式是假设集合中的每个元素都对他们对相反集合元素的偏好进行了排名。目标是满足每个人的喜好。坚持婚姻问题，想象每个男人都有一个女性排名，每个女人都有一个男性排名。目标是将它们匹配在一起，以确保每个人都尽可能获得名单上最高的人。

请记住，这需要几个步骤（或回合）才能自行解决。在婚姻的例子中要记住的另一件事是每一方只能做一件事。所以在我们的例子中，女性接受，男性提议。此外，该提案不具有约束力。这意味着如果在第一轮中，一个女人从她最想要的第二个男人那里得到一个提议，而在下一轮她从她的第一名男人那里得到一个提议，她可以拒绝第二个并接受第一个。wiki说得比我好...

算法完成后，Alice 和 Bob 不可能比他们当前的合作伙伴更喜欢对方。如果 Bob 更喜欢 Alice 而不是他现在的搭档，那么他一定是在向现在的搭档求婚之前向 Alice 求婚的。如果爱丽丝接受了他的求婚，但最终没有嫁给他，那么她一定是为了一个她更喜欢的人抛弃了他，因此她并不喜欢鲍勃而不是她现在的伴侣。如果爱丽丝拒绝了他的提议，那么她已经和比鲍勃更喜欢的人在一起了。

基本上，没有人会在婚姻中受到影响，因为在有限的选择范围内，这对是对彼此的最高偏好。