Stable Match 稳定匹配（GS算法）

1. 什么是稳定匹配

以男女婚姻为例，给定两组A和B，假设A组为男孩，B组为女孩，A组中每一个男孩对B组中每一个女孩都有一个喜欢程度的评级（例如A中的Jack最喜欢B中的Lisa，其次是Mary，再次是Alice）。那么怎么处理这些男女匹配关系，使得在经过匹配之后对任意a，b满足以下条件之一（假设A中的a和B中的b没有被配对）：

1. 相对于b，a一定更喜欢当前跟他配对的女孩
2. 相对于a，b一定更喜欢当前跟她配对的男孩

这种匹配的方式，则称为稳定匹配。

2. 为什么叫做稳定匹配

这是因为相对于不稳定匹配，稳定匹配的结果不存在不稳定的因素。

假设上述的两个条件没有被满足，即a更喜欢b，b也更喜欢a，那么这在婚姻中就有可能产生婚外情，我们称之为不稳定的因素，因此这也是一种不稳定的匹配，反之如果对任意a，b上述两个因素都被满足，则不存在不稳定因素，即为稳定匹配。

3. 稳定匹配的基本思想

现在我们定义一种新的状态——姑且称之为约会，即男孩和女孩没有正式的结婚，但在一个更完美的对象出现之前，两者比较心仪对方，但注意这种状态是不稳定的，男女双方都有可能选择更加心仪的对象约会。

首先假设每个男孩和女孩都有一个喜欢程度的列表：

女孩对男孩们的喜欢程度列表：

	Lisa	Mary	Alice
Tom	3	1	1
Jack	1	2	3
Jone	2	3	2

这张表中的数字表示喜欢程度的排名，例如Lisa最喜欢Jack，其次是Jone，而不太喜欢Tom。

相似地，我们还有一张男孩对女孩喜欢程度的表格：

	Tom	Jack	Jone
Lisa	1	3	2
Mary	2	1	3
Alice	3	2	1

这张表诠释了男孩们对女孩的喜欢程度，例如Tom最喜欢Lisa，其次是Mary，而不太喜欢Alice。

---

接下来我们就开始匹配这组男孩和女孩，我们假设让男孩向女孩求婚。

让每个男孩M向自己最喜欢的女孩求婚，如果此时这个女孩不在约会状态，则安排他们两约会，如果此时这个女孩已经在跟其他男孩N约会了，那我们把选择权交给女孩，女孩可以根据对这两个男孩M，N的喜欢程度，选择一个更喜欢的男孩进行约会，重复这个过程，直至男孩M找到约会对象为止。

最后，当所有男孩都找到约会对象，那么没有一个人是空闲的（大家都在约会），此时的结果就是一个稳定匹配的结果。

4. 算法的伪代码

---

初始让所有男孩女孩处于空闲状态

While 存在任意男孩m是空闲的，且没有对每个女孩求过婚

​ 选择这个男孩m

​ 假设w是男孩m还没求过婚中的最喜欢的女孩

​ if w也是空闲的

​ 让w和m约会

​ else if w已经在跟m’约会了

​ if w更喜欢m’而不是m

​ 让w和m’继续约会，m保持空闲状态

​ else w发现自己更喜欢m而不是当前约会对象m’

​ 让m和w约会，m’变成空闲状态

---

5. 为什么这个算法可以产生一个稳定的匹配？

前提条件：在我们的假设中，男孩和女孩的数量是一致的，均为n

我们必须承认以下事实

• 对于任意女孩w来说，在她进行第一次约会之后，她的每次重新选择，都会使得她的约会对象更合她意
• 对于任意男孩m来说，他的每次求婚，都会使得他的求婚对象越来越不合他意

1. 算法什么时候终止？

以上的事实很容易从算法的流程得出，接下来我们看看算法什么时候会终止，通过伪代码我们可以很轻松的之后算法的终止条件是不存在一个男孩m：是空闲的且还没有对每个女孩求过婚（While后的条件）,我们其实可以简化这个条件：

因为如果存在一个空闲的男孩m，则他必定没有对每个女孩都求过婚：

Proof：我们使用反证法来证明这个事实，如果这个男孩m已经对每个女孩都求过婚，但还是没有被接受去约会，至少可以说明每个女孩都已经在约会了，如果每个女孩都去约会了，那么由前提条件，男孩女孩数量一致可知，该男孩m必定也在约会，这与该男孩空闲相悖。故如果存在一个空闲的男孩m，则他必定没有对每个女孩都求过婚。

由此，算法的终止条件被简化为：不存在空闲的男孩m，那么也很自然的得到不存在空闲的女孩w，即算法终止时，所有的男孩和女孩都已经被匹配。

2. 算法会终止吗？

我们必须证明这个算法是会终止的，

并且这个算法最多会被执行n²次

Proof：这个算法迭代由一次男孩向女孩的求婚构成，由于每个男孩不会重复向一个女孩求婚，又因为总共只有n²个男女对，所以这个算法最多会被执行n²次。

3. 算法终止时的配对时稳定匹配吗？

由上述所知，当算法结束时，所有的男孩都已经和女孩配对，但我们仍需证明：

这是一个稳定的匹配。

Proof：我们通过证明这个匹配产生的结果没有不稳定因素来证明这是一个稳定的匹配。

假设存在一个不稳定因素：m和w被匹配在一起，m’和w’被匹配在一起，但是m更喜欢w’，w’也更喜欢m

这里存在一个问题：m既然更喜欢w’，那么在我们的算法中，m是否向w’求过婚呢？我们分成两种情况考虑

---

3.1 m向w’求过婚

如果是这样的话，那么他一定被w’拒绝了，因为他们两没有被匹配在一起，那么说明此时，w’正在跟某个更喜欢的男孩x约会。但最后w’跟m’在一起了，这说明w’更喜欢m’而不是x，或者说m’就是x。从这个角度上看，m’>=x>m，这与假设w’更喜欢m而不是m’冲突。

3.2 m没有向w’求过婚

由于最后m和w在一起了，所以w一定是m最后一个求婚对象，由于m是按喜欢程度来求婚的，说明m更喜欢w而不是w’，这也与假设m更喜欢w’冲突。

---

通过上述反证，可以说明不存在这样一个不稳定因素，即我们得到的匹配是一个稳定匹配！

6*. 算法的所有执行都会得到同一个结果吗

注意我们在第五点的证明中提到的：“我们得到的匹配是一个稳定匹配”，但是是否在算法的所有可能的执行情况下，我们都会得到同一种结果呢？答案是非常肯定的：

在该算法的每次执行下，我们都会得到同一个结果S

Proof：为了证明这一点，我们引入一个“最佳伴侣”和“有效伴侣”的概念

有效伴侣 指的是如果男孩m和女孩w出现在了某个稳定匹配S中，那么w是m的有效伴侣

最佳伴侣 指得是如果w是在m的偏爱列表上排名最高的有效伴侣，则w是m的最佳伴侣

那么假如说每个男孩都得到了自己的最佳伴侣，又因为最佳伴侣对于每个男孩来说是唯一的，所以是不是可以说明这个算法的每次执行都只会产生一种情况呢？接下来我们通过反证法证明这个事实：

---

首先，我们假设这个算法的某次执行产生了一个匹配S，这个匹配S包含某个男孩m没有获得自己的最佳伴侣w

然后我们定义一个时刻t，在算法执行中，存在事件：“某个男孩m第一次被某个有效伴侣拒绝”，t即表示这个事件第一次发生的时刻

那么在这个时刻t，拒绝这个男孩的女孩一定就是男孩m的最佳伴侣w。那么根据算法，此时女孩w肯定更倾心于另一个男孩m’

根据我们的假设可知，w是m的有效伴侣，根据有效伴侣的定义，我们可以假设存在另一个匹配S*，在这个匹配中，w成功的和m被匹配在了一起。那么很自然地产生了一个疑问，就是在S*中，m’会和谁匹配在一起呢？姑且假设为女孩w’。

考虑时刻t，根据t的定义，此时m’肯定还没有被有效伴侣拒绝过，而且此时m’正跟w在一起约会，由于m’是根据自己的喜好程度来进行求婚的，所以m’更喜欢w而不是w’。继续考虑时刻t，我们知道在这时，m被w拒绝，这说明w更喜欢m’而不是m。

有趣的事情发生了，在稳定匹配S*中，我们假设了w’和m’被匹配在了一起，然而m’更喜欢w而不是w’，w更喜欢m’而不是m，这即产生了一个不稳定因素：w可能和m’发生婚外情！这与我们声称的S*是稳定匹配相悖。

至此，反证结束，假设被推翻，即不存在某个匹配包含某个男孩m没有获得自己的最佳伴侣w。

---

7. 这个算法是不公平的

这里我们观察到一个事实

男孩都获得了自己的最佳有效伴侣

但是对于女孩而言呢？这是不公平的：

女孩都获得了自己的最差有效伴侣

为了证明这一点，我们依然使用反证法（与上述证明相似）：

---

Proof：假设在匹配S中存在一对情侣m，w，其中m不是w的最差有效伴侣，假设m’才是w的最差有效伴侣

那么存在S*使得在S*中，w和一个她更不喜欢的男孩m’匹配在了一起——w更喜欢m而不是m’

此时m和谁匹配在一起了呢？我们继续假设和某个女孩w’匹配在了一起

由第六点的证明可知，因为在S中m，w被匹配在了一起，所以w是m的最佳有效伴侣——m更喜欢w而不是w’

这又在S*中产生了一个不稳定因素——w可能和m发生婚外情。

因此和假设相悖，反证结束。

---

（tip：这件事情也许在告诉我们，在男女恋情中，先表白的一方才能占据主动权！）

8. 典型例题

8.1 时段竞争问题

首先，不是所有类似的问题都有稳定匹配的解，举个例子，比如：时段竞争问题。

现在有A和B两个电视节目公司要竞争某个电视台的黄金播出时段。

假设总共有n个时间段，A和B也各有n个节目需要安排。且假设A和B的所有节目都有着不同的收视率。

而A或B的目的就是尽可能获得更多的时间段。

那么怎么给A和B安排这个播出时间段让其达到稳定？——什么是稳定：即A或B任何一个公司不能通过单方面改变自己的节目安排来获得更多的时间段。

反例：A公司有收视率为10和30的两个节目，B公司有收视率为20和40的两个节目。（其实很容易观察到这个问题和这篇文章讲述的稳定匹配问题有一些不同）

8.2 医生分配问题

本问题考察的是不同男女数量的稳定匹配问题

假设：有m所医院，n个医生，要把n个医生分配到m所医院中去，每个医院对每个医生有一个期望排名，每个医生对每所医院也有一个期望排名，并且医生数量肯定比医院数量多的多。同时，分配结束后，医院的岗位没有空余，但是医生有可能没有被安排工作。

稳定条件：不存在下列条件之一：

• 学生s和s’，医院h和h’：s被分配到h，s’被分配到h’，h更喜欢s’，s’也更喜欢h（即s’可能会从h’跳槽到h）
• 学生s和s’，医院h和h’：s被分配到h，s’没有被分配，h更喜欢s’而不是s（h有可能开除s而要s’）

首先面临的问题就是，究竟是医院去要人，还是医生去求职？

我们可能很自然的想到，当然是以医生去求职的方式来安排职位，但实际上我们以医院收人的方式进行算法，因为注意到算法的终止条件应该医院没有空闲岗位了而不是所有医生都得到职位安排了（因为有可能某些医生没有得到职位）

相似地，我们给医院定义两个状态：avilible——有空闲岗位，full无空闲岗位。同时也给医生定义两个状态free——待职，committed——就职。

接下来的算法过程就和我们前面讲到的相似了：

---

while 存在某所医院h有空闲岗位avilible

​ h给它的期望清单上当前排名最高的医生s提供offer

​ if 这个医生s处于free

​ 让这个医生任职

​ else if 这个医生s已经在别处h’任职committed

​ if s更喜欢h’而不是h

​ 就让s继续在h’任职

​ else if s更喜欢h而不是h’

​ 让s转到h任职

---

总结：这个问题和前面讲到的男女婚姻匹配问题的不同点就是医生和医院的树木不对等，且一所医院可以有多个医生，但一个医生只能去一个医院任职，而且有可能存在医生没有得到工作。在这种情况下，应该让作为算法终止条件的医院获得选择权，去选择医生。（在男女婚姻匹配问题中，由于数量相等，可以让男孩求婚，也可以让女孩求婚）

相似地，算法的复杂度是O（mn）

8.3 船只停泊问题

本问题考察的是善于将其他问题转换成稳定匹配问题

假设某家公司有n个港口和n条船，且存在一个表标明了m天中，每一天每条船的状态（出海或者正停在某个港口），在这m天中，每条船访问每个港口恰好一天。

但是船可能需要维修或者保养，公司现在对每条船，当它到达某个港口时，公司可能会让它停留在这个港口维护，直到m天过去。

那么是否总是存在某种方案使得不会有两条船停在同一个港口（一个港口只能停一条船）？

思路：我们可以把这个问题转换成我们所熟知的稳定匹配问题

先排出港口和船只的喜好排名表，

• 让船只访问各个港口的时间次序作为船只对港口的喜好程度排名表
• 让港口被各个船只访问时间次序的逆序作为港口对船只的喜好程度排名表

然后按照这两张排名表，对港口和船只进行稳定匹配即可

证明：为了证明以上方法时可行的，我们采用反证法

假设我们已经经过了一次稳定匹配，并且出现了当船只S已经停在了港口P检修，但是出现了另一艘船S’又来到了港口P。

那么这意味着：

• S’更喜欢P而不是他应该检修的港口P’（因为S’先来到P而不是P’)

• P更喜欢S’而不是S（因为对于P，S’后到达）

那么S’和P之间就存在不稳定因素，这与我们宣称的这是一次稳定匹配相矛盾

8.4 存在并列喜欢程度的婚姻匹配问题

本问题考察的是存在比如男孩m对女孩w和w’的喜欢程度相同的情况

这里我们的不稳定因素也许要发生一些变化了，为了区分，我们定义如下：

• 强不稳定因素：对于某个男孩m和女孩w，m更喜欢w而不是当前的对象，w也更喜欢m而不是当前的对象
• 弱不稳定因素：对于某个男孩m和女孩w，m更喜欢w而不是当前的对象，w或是更喜欢m而不是当前的对象，又或是w对这两个选择无所谓

那么是否总是存在能满足不存在强不稳定因素的匹配呢？又是否总是存在能满足不存在弱不稳定因素的匹配呢？

这个问题笔者暂时不做答，由大家自己思考。