Stable Matching-稳定匹配问题

问题引入

　　在求职或者约会的情景中，我们经常会面临双向选择的问题，即一个男生十分喜欢一个女生但女生却不喜欢男生等等情况，在多个求职者和多个应聘者中也会存在这样情节。每个求职者会有自己偏好的公司，每个公司也有自己偏好的求职者，如果每个公司在面试完所有求职者之后按照前3名下发应聘书，由于不同公司可能同时相中同一个应聘者以及应聘者对各个公司的偏好不同，很容易造成应聘失败，这样招聘人数不达标的公司又不得不重新发新的应聘书，而新的应聘书可能导致之前已经答应去某个公司的应聘者取消前往计划，这样无疑会造成一系列混乱的发生，而且也浪费了很多时间。那么如果事先知道每个应聘者、每个公司的偏好的情况下，能否提供一种应聘方式让这种情况不再发生呢？稳定匹配的引入很好解决了这个问题。
　　

问题抽象

　　给定两个集合 $M={m_1,m_2,\cdots,m_n}$,$W={w_1,w_2,\cdots,w_n}$
　　对这两个集合：每个M中元素对W中所有元素都有一个排名、优先表(无并列)
　　　　　　　　　每个W中元素对M中所有元素也有一个排名、优先表(无并列)
　　若Ｍ表示n个男生的集合，W表示n个女生的集合，试给出一种分配方式让每个男生和每个女生都能找到合适对象(什么分配是合适的?)

概念定义

　　为了方便解决问题，我们需要定义如下概念以帮助我们理解、界定问题。
　　以下定义中的m,m’表示M中两个不同元素，w,w’表示W中两个不同元素。 　　

1. 有序对：(m,w)
2. M×W：笛卡儿积 表示M中元素与W中元素所有的有序对的集合
3. 匹配：S是M×W的子集(有序对的集合)，满足以下条件则称S为对M,W的一个匹配
   ＋ 每一个M和W中元素至多只出现在S集合的一个有序对中(可能不出现)
4. 完美匹配：S’是M×W的子集，满足以下条件则称S’为对M,W的一个完美匹配
   • S’是一个匹配
   • S’满足M和W中每一个元素恰好只出现在S’的一个有序对中
5. 不稳定因素：对于一个完美匹配，若存在两个有序对(m,w),(m’,w’)满足
   • m相较于w更偏爱w’
   • w’相较于m’更偏爱m
     则称有序对(m,w’)为S的一个不稳定因素
6. 稳定匹配：对于M×W的集合S，当满足以下两个条件的时候则称S是一个稳定匹配
   • S是完美匹配
   • S中没有不稳定因素
7. 有效伴侣：对于一个有序对(m,w)，满足以下条件则称w是m的有效伴侣
   • 存在一个稳定匹配，它包含(m,w)有序对
8. 最佳有效伴侣：对于一个有序对(m,w)，满足以下则成w是m的最佳有效伴侣
   • w是m的有效伴侣
   • 在所有m的有效伴侣中w在m心中排名最高
     记作w=best(m)
9. 最差有效伴侣：对于一个有序对(m,w)，满足以下则成w是m的最差有效伴侣
   • w是m的有效伴侣
   • 在所有m的有效伴侣中w在m心中排名最低
     记作w=worst(m)

G-S算法(Gale-Shapley算法)

1. 基本思想：以不断”求婚”的过程来逼近一个稳定匹配的状态

2. 伪代码：

   初始所有的m∈M和w∈W都是自由的
   While 存在男人m是自由的且没有对每个女人都求过婚
   	选择这样一个男人m
   	令w是m的优先表中m还没有求过婚的排名最高的女人
   	If    w是自由的    then
   		(m,w)变成约会状态
   	Else    w当前正在与m'约会
   		If    w相较于m更爱m'    then
   			m保持自由
   		Else    w相较于m'更爱m
   			(m,w)变成约会状态
   			m'变成自由状态
   		Endif
   	Endif
   Endwhile
   输出已约会的集合S.

3. G-S算法的一些性质或者特点
   I. 对于任一W中元素w从第一次被求婚开始一直保持约会状态，且w正在约会的伴侣变得越来越好(按照w的优先表)
   II. 对于任一M中元素m求过婚的一系列女人会变得越来越差(按照m优先表)
   III. G-S算法在至多n2次While循环的迭代之后会终止
   IV. 若m在算法执行的某个时刻是自由的，那么还存在一个w他还没有对其求过婚
   V. 终止时返回的集合S是一个完美匹配
   VI. 考虑G-S算法的一次执行，它返回一个对的集合S.集合S是一个稳定匹配
   VII. G-S算法的每次执行都会得到同一个结合S*
   VIII. 在稳定匹配S*中每个女人都与他最差的有效伴侣配对

4. 一些想法
   1. 在看完G-S算法伪代码之后我们必须要解开几个疑惑
      a. G-S算法会不会无限进行下去，因为每次循环可能使两个人变成约会状态，但是也会使两个人从约会状态中解除，会不会陷入死循环。
      b. G-S算法得到的集合S是不是一个稳定匹配
      c. G-S算法每次执行得到的S是不是会不一样
      d. 如果G-S算法得到的S是一个特定的稳定匹配，那S和众多可能的其他稳定匹配相比有什么特征
   2. 由1的一个疑惑我们可以看出之前的一些G-S特征或者定理的来由
      a. 如果G-S算法不会无限进行下去，那么肯定存在一个逐渐逼近的过程
      1) 所以我们可以分析得到在G-S算法执行的过程中的一些特点即性质1、
      2) 我们会发现由于性质1、2的存在，G-S算法的执行不会永远进行下去得到性质3
      b. 稳定匹配的条件是完美匹配以及不存在不稳定因素
      1) 首先证明完美匹配，完美匹配的特点概括来讲就是”不重不漏”
      首先说说证明的必要性，因为while循环退出的条件是不存在男人m是自由的且还没对每个女人都求过婚，那么存在几种情况

      i) 所有男人都是不自由的
      ii) 存在有男人m是不自由的但是已经对于每个女人都求过婚
      

      我们首先要做的就是证明S包含了所有男人女人即不漏(即排除第2种情况)，然后讨论不重的问题

      a) 证明"不漏"：
      我们要排除第2种情况即需要说明男人只要是不自由的那么就还有女人没有被他求过婚即性质4
      假设存在2中情况，那么由性质1可知所有女人都是约会状态，那么正在约会的人就是2n个人，但一共就只有2n个人，说明所有人都在约会，没有人是自由的，说明第2种情况不存在，性质4成立
      b) 证明"不重"
      由与约会都是两两进行，每个人总是同时与一个人约会，所以不会存在有重复现象
      

      综合以上，我们发现得到的集合S做到了”不重不漏”,所以它是一个完美匹配即性质5
      2) 接下来证明不存在不稳定因素
      假设存在一对不稳定因素(m,w’)，即S中存在两对有序对(m,w) (m’,w’)，但是m相比于w更爱w’，w’相比于m’更爱m
      考虑G-S的执行过程，对于m的求婚旅程，由于w’优先级更高，所以会先求婚w’，这个时候w’有两种状态，已经约会成功或者处于自由状态
      a) 对于已经约会成功：假设其在m向w’求婚的时候w’正与m’’约会
      此时m向w’求婚会出现两种情况，成功或失败

      i) 成功：说明m比m''在w'心中地位高，所以之后不论其他男生怎么向w'求婚，其排位都只会比m在w'心中高，但最终m'在w'心中排位比m低，矛盾。
      ii) 失败：说明m''比m在w'心中地位高，所以之后不论其他男生怎么向w'求婚，其排位都只会比m''在w'心中高，但最终排位却是m'<m<m''，矛盾。
      

      b) 对于处于自由状态：m直接”牵手成功”，所以之后不论其他男生怎么向w’求婚，其排位都只会比m在w’心中高，但最终m’在w’心中排位比m低，矛盾。
      综上，我们可以得出是不可能存在这么一对不稳定因素。
      S既是完美匹配又没有不稳定因素，所以S为一稳定匹配所以我们可以得到性质6
   3. 在知道G-S算法得到的是一个稳定匹配之后，我们需要考虑的就是是否每次执行都会得到同一个稳定匹配，
      为什么要思考这样一个问题呢？因为G-S算法其实可以异步实现，现实生活中不就是存在多个男生向多个女生同时求婚的情况吗？那么如果异步实现必定由于每个线程执行情况的不同带来求婚的先后次序不是固定的，所以这样会不会导致最终结果的不同呢？
      这里不得不佩服前人敏锐的思考了，有效伴侣的提出很好的解决了这样一个问题。
      考虑证明最终得到的都是S* = {(m,best(m)):m∈M} (这个考虑十分难想得到)
      有两点值得注意：
      1. S*可能不是一个完美匹配，因为有效伴侣是只要有一个稳定匹配存在该有序对就是有效伴侣
         但是对于多个男生来说最佳有效伴侣可能是同一个人，所以可能做不到”不重不漏”
      2. 如果这是一个完美匹配，该匹配是十分偏心的，是偏向于男生的
         证明过程：假设得不到这样一个集合S*而得到一个集合S，即存在一个男生他最终的伴侣不是最佳有效伴侣，也就是说在G-S算法执行过程中，存在至少一次被最佳有效伴侣拒绝的过程，将所有拒绝中第一次拒绝的男生即为m，其最佳有效伴侣为w=best(m)。(由于先后次序关系，男生如果被有效伴侣拒绝会最先被最佳有效伴侣拒绝，所以此次拒绝也是男生被女生所有拒绝中第一次被有效伴侣拒绝),由于最佳有效伴侣在所有有效伴侣中的排名最高，所以m在向有效伴侣求婚时会第一个向w求婚，然而他被拒绝了(不论是约会之后不久还是求婚当时)，即存在一个男生m’比m在w心中排名更高，那么在包含(m,w)有效伴侣的稳定匹配S’中，假设m’与w’≠w配对，回到G-S算法得到的稳定匹配S中。由于w拒绝m是所有对最佳有效伴侣拒绝的第一个，之前还没人被有效伴侣拒绝，m’肯定也没有被有效伴侣拒绝，也就是说w拒绝m可能是因为w正在和m’约会或者m’向w求婚，不管什么情况m’肯定都是先向w求婚然后可能再向w’求婚，不可能先向w’求婚然后拒绝w’再向w求婚，因为(m’,w’)是有效伴侣而之前没有有效伴侣被拒绝。所以在m心中w的排名比w’高，综上可知(m’,w)为稳定匹配S’中一个不稳定因素，矛盾，说明假设不成立，得到性质5。
         简单来说就是：
         假设G-S没有得到S*得到了S → 存在一个男生伴侣不是最佳有效 → 存在第一次对最佳有效伴侣的拒绝(w拒绝m选择m’) → 存在稳定匹配S’这次m’选择了w’≠w → 这次拒绝之前没有任何对最佳有效伴侣以及有效伴侣的拒绝 → m’没有被拒绝 → m’不可能先选w’然后被拒绝了选w → m’先选w → m’更爱w w更改m’ → 稳定匹配S存在不稳定因素 → 矛盾 → G-S得到了S*
         这也间接解决了第一点注意，即S*为一个完美匹配因为S*为G-S算法得到结果，该结果为稳定匹配，S*当然为完美匹配。
   4. S*既然是G-S算法得到的唯一稳定匹配，从可能存在的若干个稳定匹配中脱颖而出肯定具备一定特点。在之前讨论中已经发现S*是偏向于男生的，因为每个配对的女生都是其最优匹配，那么对于女生来说这个配对意味什么呢？
      根据性质8我们已经知道结论：在稳定匹配S*中每个女生都与他最差的有效伴侣配对
      证明过程：假设S*中存在有序对(m,w)使得m不是w的最差有效伴侣，那么肯定存在一个稳定匹配S’，w在这个稳定匹配中和更不喜欢的男生m’配对，w更喜欢m，而m与另一个女生w’=w配对，而w为m的最佳有效伴侣，w’为m的有效伴侣，所以m更喜欢w，那么在稳定匹配S’中(m,w)即为不稳定因素与S’为稳定匹配矛盾。
      故得到性质8

问题解决

G-S算法实现代码如下：

#include<iostream>
using namespace std;
const int N = 10005;
int W[N]={0},M[N]={0};
int M_pri[N][N]={0},W_pri[N][N]={0};

void getPri(int );
void G_S(int );
void output(int );
bool lovemore(int ,int ,int);

int main()
{
	int n;
	cin>>n;
	getPri(n);
	G_S(n);
	output(n);
	return 0;
}

void getPri(int n)
{

	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			cin>>M_pri[i][j];

	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			cin>>W_pri[i][j];
}

bool lovemore(int m,int w,int num)
{
	for (int i=1;i<=num;i++)
		if (W_pri[w][i] == W[w])
			return false;
		else if (W_pri[w][i] == m)
			return true;
}

void G_S(int num)
{
	int m,w;
	while (M[0]!=num)
	{
		w=m=0;
		while (M[++m]!=0) ;
		w = M_pri[m][++M_pri[m][0]];
		if (W[w])	//如果女生已经在约会了
		{
			if (lovemore(m,w,num))
			{
				M[W[w]] = 0;
				M[m] = w;
				W[w] = m;	
			}
			else 
				continue;
		}
		else //如果女生没有约会还是自由状态
		{
			M[m]=w;M[0]++;
			W[w]=m;W[0]++;
		}
	}
}

void output(int num)
{
	for (int i = 1;i<=num;i++)
		cout<<"("<<i<<", "<<M[i]<<")"<<endl;
}

样例测试

样例输入

10

2 5 4 7 3 6 9 8 10 1  
3 2 1 4 5 9 6 10 8 7 
5 4 9 10 1 3 2 8 7 6 
3 8 7 2 5 4 9 1 10 6 
6 4 9 5 3 1 8 7 2 10 
6 1 2 8 3 9 10 5 7 4 
7 3 10 9 1 8 6 2 5 4  
10 8 2 9 1 3 6 7 4 5  
9 1 6 10 7 8 2 3 5 4  
8 10 2 7 3 1 6 9 5 4 

4 6 1 7 10 5 9 8 3 2  
1 2 4 3 8 9 6 10 5 7 
2 1 8 10 4 3 6 9 7 5 
3 1 7 4 5 2 6 8 10 9 
6 7 9 4 3 1 10 5 2 8 
4 1 2 8 10 9 3 5 7 6 
7 3 8 9 1 10 5 2 6 4  
10 4 2 3 1 8 6 7 9 5  
5 2 6 10 7 8 1 3 9 4  
7 1 2 8 3 10 6 9 5 4

样例输出

(1,2)
(2,3)
(3,4)
(4,5)
(5,6)
(6,1)
(7,7)
(8,10)
(9,9)
(10,8)