Gale-Shapley 算法稳定匹配证明：最佳有效伴侣集合 S

在稳定匹配问题中，如果存在包含配对 (M, W) 的稳定匹配，我们可以说女人 W 是男人 M 的'valid' 伴侣。我们会说 W 是 M 的最佳有效伴侣，如果 W 是 M 的有效伴侣，而 M 排名更高的女人，W 是 M 的最佳有效伴侣。我们将使用 best(M) 来表示 M 的最佳有效伙伴。现在，让 S 表示对的集合 { (M, best(M)) : M ∈ M }，证明 following 事实：Gale-Shapley 算法的每次执行都会得到集合 S。

要证明 Gale-Shapley 算法的每次执行都会得到集合 S，我们需要证明两个方面：稳定性和完备性。

1. 稳定性： 首先，让我们假设 Gale-Shapley 算法的每次执行都会得到一个不稳定的配对。也就是说，存在一个男人 M 和一个女人 W，它们不是最佳有效伴侣，但在算法执行后，它们被配对了。这意味着 M 有一个更高排名的女人 W'，而 W 被配对给了 M。根据算法的规则，W 将成为 M 的有效伴侣，并且 M 将排除 W'。但是这与我们的假设相矛盾，因为我们假设 W' 是 M 的最佳有效伴侣。因此，我们得出结论：Gale-Shapley 算法的每次执行都会得到一个稳定的配对。

2. 完备性： 我们需要证明 Gale-Shapley 算法的每次执行都会找到每个男人的最佳有效伴侣。根据算法，男人按照他们的偏好顺序依次提出邀请，而女人则根据她们对当前邀请的偏好选择接受或拒绝。因此，每个男人都会依次提出邀请给他在女人偏好列表中的下一个女人，直到他找到一个女人接受他的邀请或者所有女人都拒绝他的邀请。如果一个男人找到了一个接受他邀请的女人，那么根据算法，这个女人将成为他的有效伴侣，并且他将排除他在女人偏好列表中排名更低的女人。这意味着，当算法结束时，每个男人都有一个有效伴侣，并且根据他们的偏好列表，这些伴侣是最佳的。因此，Gale-Shapley 算法的每次执行都会找到每个男人的最佳有效伴侣。

综上所述，我们可以得出结论：Gale-Shapley 算法的每次执行都会得到集合 S。