什么是稳定匹配？

Question

所以我的问题是指什么是“稳定匹配”？我意识到稳定婚姻问题，并且所有解决方案似乎都表明您完成了“稳定匹配”。但我不确定这实际上是什么意思。

Answer 1

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

在稳定的匹配，我们保证在两盘（男&女人，孩子&玩具，人&度假目的地，等等）都放在一对与一个元件与另一组，并且对是“最好的所有元素可用匹配“

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

请记住，这需要几个步骤（或轮次）才能实现。在婚姻的例子中，要记住的另一件事是每一方只能做一件事。所以在我们的例子中，女性接受，男性提出。此外，该提案不具约束力。这意味着，如果在第一轮中，女人从她最喜欢的2号球员那里得到一个提议，并且在下一轮她从她的＃1男子那里得到一个提议，她可以拒绝＃2并且拿到＃1。维基百科表示，它比我更好...

算法完成后，爱丽丝和鲍勃都不可能在他们当前的合作伙伴上互相优先。如果鲍勃偏爱爱丽丝到现在的伴侣，他必须在向爱丽丝提出现在的伴侣之前提出建议。如果爱丽丝接受了他的提议，但最终还没有与他结婚，她肯定会把他抛弃给她喜欢的人，因此她不喜欢鲍勃而不是她现在的伴侣。如果爱丽丝拒绝了他的提议，她已经和她比她更喜欢的人在一起了。

基本上，没有人得到在婚姻shadge，因为这对是有限的选择对另一个最高的偏好。