稳定匹配(stable Matching)问题

在学 UCB CS70时，有一个note专门讲了这问题————稳定匹配问题，用了两天时间稍微理解了一些些。

稳定匹配问题

提议与拒绝算法(The Propose-and-Reject Algorithm)

Note 上就是这么命名的，也称盖尔-沙普利算法(Gale–Shapley algorithm)。

  1. 每个职位（男士）向自己优先列表中尚未拒绝的最优先候选人提出邀请。
  2. 每位候选人（女士）收集所有在这一次收到的邀请，对于她最喜欢的邀请，他回应“可以”，对于其他排名的邀请，她直接拒绝这些提议。
  3. 每个被拒绝的职位将拒绝的候选人从其列表中划掉

上述循环每天重复，直到没有邀请被拒绝。

提议与拒绝算法的性质

  • 这个算法总是会停止。

证明：论证很简单：在算法未停止的每一天，至少有一个职位必须从其列表中删除一些候选人（否则算法的停止条件将会被触发）。由于每个列表有 \(n\) 个元素，而总共有 \(n\) 个列表，这意味着算法最多在 \(n^2\) 次迭代（天）后终止。

稳定性

一个好的匹配应该具有什么性质？或许我们希望最大化首选的数量？或者，我们可以最小化最后选择的数量。或者理想情况下，我们可以最小化选择排名的总和，这可以被视为最大化平均幸福感。

在本讲中，我们将专注于一个更基本的标准，这个标准根植于自主性的理念，即稳定性。如果存在一个职位（男士）和一个候选人（女士），他们都希望与对方合作，而不是与他们当前的匹配对象合作，那么这个匹配就是不稳定的。我们将这样的配对称为不和谐对。因此，n 个职位与 n 个候选人的匹配是稳定的，如果它没有不和谐对。

在讨论如何找到一个稳定的匹配之前，让我们先问一个更基本的问题：稳定的匹配总是存在吗？答案显然是肯定的。对于任何不稳定的匹配，从上面的不稳定的定义来看，总可以找到一个其他的人，来拆散当前的匹配对象。

分析稳定性

  • 引理1： 如果职位 \(J\) 在第 \(k\) 天向候选人 \(C\) 提出提议，那么在随后的每一天 \(C\) 都会收到一个她至少和 \(J\) 一样喜欢的职位提议（即“在手中的”职位）。

证明不证了，看了大概，只能看懂，开了一个坑，等后面这个课结束了在来填。

  • 引理2： 提议与拒绝算法总是终止于一个匹配。

  • 定理1： 该算法生成的匹配总是稳定的。

证明：这次我们从职位的角度来证明稳定性，我们直接证明在算法生成的匹配中，没有职位会涉及不和谐对。考虑最终匹配中的任何一对 \((J, C)\)，假设 \(J\) 更喜欢某个候选人 \(C_{*}\) 而不是\(C\)。我们将论证 \(C_{*}\) 更喜欢她的职位而不是 \(J\)，因此 \((J, C_*)\)不能构成不和谐对。由于 \(C_*\) 在 \(J\) 的列表中比 \(C\) 靠前，\(J\) 必然在向C提出提议之前先向 \(C_*\) 提出了提议。因此，根据改善引理，\(C_*\) 至少和 \(J\) 一样喜欢她最终获得的职位，因此更喜欢她的职位而不是 \(J\) 。因此，没有职位会涉及不和谐对，匹配是稳定的。

xxxxxxxxxx17 1# Distant-Skys2# To make a picture smaller or bigger.3​4import cv2 as cv5import numpy as np6​7image = cv.imread('1.jpg')8​9res = cv.resize(image,None,fx=0.7,fy=0.7,interpolation=cv.INTER_CUBIC)10# if want to make picture bigger ,let ((fx and fy) > 1).11​12# print the result picture.13# cv.imshow('result image',res)14# cv.waitKey(0)15# cv.destroyAllWindows()16​17cv.imwrite('1_result.jpg',res)python

上面我们证明了这个算法总会存在稳定的匹配。但是在现实生活中不会仅仅追求这个，还要追求最好，那么最优性应运而生。

  • 定义1 （职位的最佳候选人） 对于给定职位J，J的最佳候选人是所有稳定匹配中J可以配对的最高排名候选人（注意候选人是双方都看得上的）。
  • 定义4.3 （候选人的最佳职位） 对于给定候选人C，C的最佳职位是所有稳定匹配中C可以配对的最高排名的职位。

定理2： 提议与拒绝算法输出的匹配总是对于一方最优的。

假设不是对于一方最优的，我们先举个栗子，可能不是对雇主最优的。那么，在某一天(第 k 天)，J 被他的最佳候选人 C 拒绝，C 选择了 K 的位置，那么根据最佳候选人的定义，必然存在一个稳定匹配，其中 J 与 T 配对，那么这个稳定匹配为 \(\{\dotsc \{J,T \},\{C,K\} \dotsc\}\)。

下面来证明(T,K) 是不和谐对。按照上面的逻辑，T更喜欢K而不是J。由于第 k 天是某个职位第一次被其最佳候选人拒绝的日子，在第k天之前，职位 T 没有被其最佳候选人拒绝过。由于 T 在第 k 天向 K 提出了提议，这表明 T 至少和它的最佳候选人一样喜欢C*，因此至少和它在稳定匹配T中的配对 K 一样喜欢 T。因此，(T,K)在匹配中形成了一个不和谐对，所以匹配中不是稳定的。

相关代码

就是很经典的题目，男士与女士结婚配对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void Stable_Marriage()
{
    // 初始话女士与男士的对象
	memset(man,0,sizeof(man));
	memset(woman,0,sizeof(woman));
	for(int i=1;i<=n;i++)	rank[i] = 1;
    // 开始匹配
	while(1){
		int sign = 0;
		for(int i=1;i<=n;i++){
			if(!man[i]){    // 如果男士不是单身狗
				int g = men[i][rank[i] ++];     // 向没有被拒绝的女士发出邀请
				if(!woman[g]){ 
                    // 如果女士也没有对象
					woman[g] = i;man[i] = g;
				}
                // 如果有了，判断现在的男士提出的申请是否比原来的对象，如果好。就换一个
				else if(sc_woman[g][i] < sc_woman[g][woman[g]]){
					man[woman[g]] = 0;  
                    // 把原来的甩了
					woman[g] = i;man[i] = g;
				}
				sign = 1;
			}
		}
        // 如果所有的男士都有对象，那么这个匹配已经OK了
		if(!sign)	break;
	}
	 for(int i=1;i<=n;i++)
	 	printf("%d %d\n",woman[man[i]],man[i]);
}