稳定匹配的定义及实例分析

无论在一对一双边匹配问题还是在一对多双边匹配问题中，都存在大量的双边匹配方案。而如何从大量的双边匹配方案中选择最优的匹配方案是一个值得考虑的重要问题。双边匹配的一个基本理论问题是双边主体是否有动机背离决策者给定的匹配方案。在一个匹配方案中，若一个匹配主体与另外一方的一个匹配主体认为他们进行匹配要优于他们当前各自的匹配对象，那么这两个匹配主体通过改变当前的匹配对象会相互受益，因此他们有动机去背离当前匹配而私下进行匹配，由此造成原有匹配方案的不稳定和匹配失效。为防止双边主体有动机背离给定的匹配方案，Gale和Shapley在1962年研究婚姻匹配问题和大学录取问题时提出了稳定匹配的概念。Roth通过对英国医院与实习生匹配市场的实证研究发现，那些采用不稳定机制的匹配市场基本都失败了，而稳定匹配机制都成功了并且一直在使用[43，44]，由此可以看出，稳定性对于双边匹配决策的成功起着非常重要的作用。

依据文献[38]和[52]下面给出稳定匹配的相关定义。

定义1.7（可接受对） 在双边匹配问题中，对于∀Ai∈A，∀Bj∈B，若（Ai，Bj）∈A×B满足1≤rij≤n且1≤sij≤m，则称（Ai，Bj）为可接受对；否则，称为不可接受对。

（1）一对一稳定双边匹配

在一个给定的匹配方案中，对于可接受对中的两个匹配主体，若他们在匹配方案中没有形成匹配对，但是他们相互偏好的程度优于他们在当前匹配方案中的匹配对象，则称这个可接受对为阻塞对。

定义1.8（一对一稳定阻塞对） 设一对一双边匹配μ：A∪B→A∪B，∀Ai，Ak∈A，i≠k，∀Bj，Bh∈B，h≠j，若可接受对（Ai，Bj）满足以下条件之一：

(i)μ(Ai)=Ai,μ(Bj)=Bj;

（ii）μ（Ai）=Ai，μ（Bj）=Ak且sij＜skj；

（iii）μ（Ai）=Bh，μ（Bj）=Bj且rij＜rkj；

（iv）μ（Ai）=Bh，μ（Bj）=Ak且rij＜rih，sij＜skj。

则称一对一双边匹配方案μ被（Ai，Bj）阻塞，并称（Ai，Bj）为匹配方案μ的一个阻塞对。

定义1.9（一对一稳定匹配） 设一对一双边匹配μ：A∪B→A∪B，若匹配方案μ不被任意个体阻塞并且不被任意的一对一稳定阻塞对阻塞，则称匹配方案μ为一对一稳定匹配；否则，称为一对一不稳定匹配。

由定义1.6和定义1.9可以看出，一对一稳定匹配一定是个体理性匹配，由定义1.8和1.9可以看出一对一匹配方案不会被不可接受对阻塞，这可以解释为个体理性匹配中不可接受对不可能实现匹配，因此即使满足定义1.8中的四个条件之一也不会阻塞匹配方案。下面通过一个例子来详细说明一对一稳定匹配的含义。

例1.2 设甲方主体集合为A={A1，A2，A3}，乙方主体集合为B={B1，B2，B3}，甲乙双边主体的偏好序值信息构成的矩阵分别为(www.xing528.com)

3个一对一双边匹配μ1={（A1，B3），（A2，B2），（A3，B1）}、μ2={（A1，B2），（A2，B3），（A3，B1）}和μ3={（A1，B1），（A2，B3），（A3，B2）}。根据定义1.4和1.5可知，μ1和μ2是个体理性匹配，但是在μ3中，对A3而言他的匹配对象B2是不可接受的，因此，μ3不是个体理性匹配，所以μ3也就一定不是稳定匹配。在μ1中，对于可接受对（A1，B1）而言，由于r11=1，r13=3，所以A1认为B1要优于B3；s31=3，s11=1，所以B1认为A1要优于A3，那么由定义1.7可知，（A1，B1）是匹配方案μ1的阻塞对，因此μ1是不稳定匹配。经过检验只有匹配方案μ2是一对一稳定匹配。

（2）一对多稳定双边匹配

定义1.10（一对多稳定阻塞对） 设一对多双边匹配μ：A∪B→2A∪B，∀Ai，Ak∈A，i≠k，∀Bj，Bh∈B，h≠j，若可接受对（Ai，Bj）满足以下条件之一：

(i)|μ(Ai)|=0,|μ(Bj)|＜qj;

（ii）μ（Ai）={Bh}，|μ（Bj）|＜qj且rij＜rjh；

（iii）|μ（Ai）|=0，∃Ak∈μ（Bj）且sij＜sik；

（iv）μ（Ai）={Bh}，∃Ak∈μ（Bj）且rij＜rih，sij＜skj。

则称一对多双边匹配方案μ被（Ai，Bj）阻塞，并称（Ai，Bj）为匹配方案μ的一个阻塞对。

在定义1.10中，条件（i）表示的是Ai没有匹配对象，并且Bj的匹配对象不超过期望匹配数量的情形；条件（ii）表示的是Bj期望匹配的数量还没满额，并且Ai认为Bj要优于当前的匹配对象Bh的情形；条件（iii）表示的是Ai没有匹配对象，不管Bj的匹配对象是否满额，Bj的匹配对象中存在一个比Ai差的情形；条件（iv）表示的是Ai认为Bj要优于当前的匹配对象Bh，Bj的匹配对象中存在一个比Ai差的情形，显然在以上四种情形下，可接受对（Ai，Bj）都具有放弃当前匹配对象而私下进行匹配的动机。

定义1.11（一对多稳定匹配） 设一对多双边匹配μ：A∪B→2A∪B，若匹配方案μ不被任意个体阻塞并且不被任意的一对多稳定阻塞对阻塞，则称匹配方案μ为一对多稳定匹配；否则，称为一对多不稳定匹配。

通过定义1.10和1.11可以看出，一对多双边匹配也只能被可接受对阻塞，并且一对多稳定匹配也一定是个体理性匹配。

例1.3 设甲方主体集合为A={A1，A2，A3，A4，A5}，乙方主体集合为B={B1，B2}，q1=1，q2=3，q3=1，甲乙双边主体的偏好序值信息构成的矩阵分别为

2个一对多双边匹配方案μ1={（A1，B2），（A2，B1），（A3，B3），（A4，B2），（A5，B2）}和μ2={（A1，B2），（A2，B2），（A3，B1），（A5，B2）}。在μ1中，对A4而言B2是不可接受的，因此μ1不是一个个体理性匹配。在μ2中所有匹配主体的匹配对象都是可接受的，即μ2是个体理性匹配，但是在μ2中，A1认为B1要优于当前匹配对象B2，r11=1＜r12=2，B1也认为A1要优于当前匹配对象A3，s11=2＜s31=5，因此（A1，B1）是匹配方案μ2的一个阻塞对，所以μ2不是一对多稳定匹配。此外，由于A4没有匹配对象，|μ（B3）|=0＜q3=1，因此，（A4，B3）也是匹配方案μ2的一个阻塞对，由此可见一个匹配方案的阻塞对可能有多个。