algorithm - 稳定匹配的反例

Question

我目前正在阅读一本算法书，遇到了稳定匹配问题。我想到了一个我很好奇的问题，但这本书没有回答。问题是：
对于任何匹配，如果它不稳定，则选择任何阻塞对（w，m），并匹配它们。并且还匹配他们以前的合作伙伴。并重复。这是达到稳定匹配的正确算法吗？
似乎答案是否定的。但我想不出一个反例。有没有人可以帮忙？

Answer 1

我想我已经找到了答案。假设我们有 3 名女性和 3 名男性。他们的偏好列表是：
w1: m3 > m2 > m1
w2: m2 > m3 > m1
w3: don't care

m1：不关心
m2：w1 > w2 > w3
m3：w2 > w1 > w3

初始匹配： (w1,m1) (w2,m2) (w3,m3)
Step 1: w1 and m2 match, then (w1,m2) (w2,m1) (w3,m3)
Step 2: w1 and m3 match , then (w1,m3) (w2,m1) (w3,m2)
Step 3: w2 and m3 match, then (w2,m3) (w1,m1) (w3,m2)
Step 4: w2 and m2 match, then (w1,m1) (w2,m2) (w3,m3)

4 步后，匹配进入初始状态，导致无限循环。

Answer 2

公认的解决方案假设只有一条路径，但在第 1 步，如果 m3 和 w1 匹配并且他们被拒绝的配偶匹配，我们一步达到稳定匹配：(m1, w3), (m2, w2), (m3, w1)，所以它不是一个无限循环。

事实上，在 OP 中解释的过程将导致稳定的匹配。这在论文中得到了证明：Roth 和 Vande Vate。“双边匹配中稳定的随机路径。” 计量经济学：计量经济学会杂志（1990）：1475-1480。

Roth 和 Vande Vate 观察到，许多现实生活中的匹配机制是稳定的，即使没有人将其设计成这样。因此他们推测任何初始匹配都必须有随机路径来稳定。他们证明，从任意匹配开始，允许随机选择的阻塞对匹配的过程将收敛到概率为 1 的稳定匹配。

Answer 3

您所说的算法是随机匹配，没有考虑到他们的偏好。在该算法中，一个合作伙伴可能具有更高的偏好，从而使任何可能的匹配都不稳定。

根据定义的稳定匹配一种解决方案对所有人都公平的匹配。

该算法也没有提到避免以前的匹配使无限循环成为可能。