在稳定匹配问题中，我试图生成最坏情况的偏好列表。我遇到一篇论文说这是 n=5 的最坏情况
m1: w1 w2 w3 w4 w5
m2: w2 w3 w4 w1 w5
m3: w3 w4 w1 w2 w5
m4: w4 w1 w2 w3 w5
m5: w1 w2 w3 w4 w5
w1: m2 m3 m4 m5 m1
w2: m3 m4 m5 m1 m2
w3: m4 m5 m1 m2 m3
w4: m5 m1 m2 m3 m4
w5: m1 m2 m3 m4 m5
直觉上，这是有道理的。但是任何人都可以正式地争论为什么这是最坏的情况以及为什么我们不能得到比这更糟的情况吗？
Gale-Shapley算法是解决稳定匹配问题的一种方法，既保证了完美匹配，又保证了不不稳定。该算法由重复的报价组成，并在每个人都配对后结束。在这种稳定婚姻问题的情况下，男性会按照自己的喜好顺序向女性求婚。如果女人不是一对，她必须接受这个提议。如果女人是一对，如果提议的男人在她的偏好列表中高于与她配对的当前男人，她可以接受另一个提议。一旦每个女人都被提议（因此每个人都被配对），算法就结束了。
您提到的首选项列表是稳定匹配问题最坏情况的一个示例。要了解它是如何工作的，它有助于将其绘制出来并贯穿每个步骤。首先，m1 会向 w1 求婚，w1 必须接受，因为她目前不在一对中。m2 会向 w2 求婚，m3 会向 w3 求婚，m4 会向 w4 求婚。正如你所看到的，目前每个男人都有他们的第一偏好女人，每个女人都有第五偏好男人（除了 m5 和 w5）。该算法继续进行，因为 w5 未配对。
接下来，m5 会向 w1 提议。w1 能够接受，因为她将 m5 排在 m1 之前。现在，m1无可匹敌，所以他向w2求婚。w2 接受，因为 m1 在她的偏好列表中排名高于 m2。这种情况继续下去，你会注意到每个男人都与他们第二偏好的女人配对，每个女人都在接受第四偏好男人的提议（w5 除外）。该算法继续进行，因为 w5 仍未配对。
完成整个算法后，您会注意到最终配对为 m1-w5、m2-w1、m3-w2、m4-w3 和 m5-w4。每个男性都有第四个偏好的女人（除了 m1 有第五个偏好），每个女人都有他们的第一个偏好男人。
注意每个人如何将 w5 作为他们的第五个偏好。正因为如此，每个人在向 w5 提出要约之前都会检查他们的整个名单。w5 的偏好列表可以按任何顺序排列，但仍然是最坏的情况。您提到的偏好列表只是最坏情况的一个示例，但还有其他变体遵循与此相同的逻辑。
这是证明最坏情况的更正式的方法。没有女人可以收到超过 n 个提案，但是一旦每个女人收到一个提案，算法就会停止。因此，在最坏的情况下，除了一个（n - 1 名女性）之外的每个女性都会收到每个男性（n）的提议。最后一位女性将收到 1 个提案，该提案最终将结束算法。将这些结合在一起，最坏的情况发生在 n(n-1) + 1 个提案被扩展时。在您的示例中，有 4 名男子以他们的第四项偏好（每人 4 个提案）结束，1 名男子以他的第五项偏好（5 个提案）结束。4*4 + 5 = 21 等于将 n = 5 代入 n(n-1) + 1。
我希望这有帮助。