概念界定与相关理论的分析

（1）个体理性匹配

令αij表示Ai对Bj的总体满意度，βij表示Bj对Ai的总体满意度。本书假设αij＞0表示Ai认为Bj是可接受的，否则，表示Ai认为Bj是不可接受的；βij＞0表示Bj认为Ai是可接受的，否则，表示Bj认为Ai是不可接受的。特别地，当μ（Ai）=Ai时，记Ai的满意度为αi=0；当μ（Bj）=Bj时，记Bj的满意度为βj=0。

下面对基于满意度的可接受对、个体理性匹配概念进行界定。

定义5.1（可接受对） 在一对一双边匹配问题中，对于∀Ai∈A，∀Bj∈B，若（Ai，Bj）∈A×B满足αij＞0且βij＞0，则称（Ai，Bj）为可接受对；否则，称为不可接受对。

在双边匹配方案中，若存在一个匹配主体与其匹配对象形成的匹配对是不可接受对，则称匹配方案被个体阻塞，并称该匹配方案是非个体理性匹配。下面给出个体阻塞和个体理论匹配的具体定义。

定义5.2（个体阻塞） 在一对一双边匹配μ中，若μ（Ai）=Bj且αij≤0，则称匹配方案μ被个体Ai阻塞；若μ（Ai）=Bj且βij≤0，则称匹配方案μ被个体Bj阻塞。

定义5.3（个体理性匹配） 在一对一双边匹配μ中，若匹配方案μ既不被任意的个体Ai∈A阻塞，也不被任意的个体Bj∈B阻塞，则称匹配方案μ为个体理性匹配。

由定义5.1、定义5.2以及定义5.3可知，若匹配方案μ是个体理性匹配，则μ中的任意一个匹配对都是可接受对。

（2）稳定匹配

在双边匹配中，匹配的稳定性是衡量匹配方案优劣的一个重要准则。在双边匹配方案中，没有形成匹配对的两个相互可接受的匹配主体，若双方中的任意一方对对方的满意度要大于对当前匹配对象的满意度，则这两个匹配主体将会放弃当前匹配对象而私下进行匹配，由此造成原有匹配方案的不稳定和匹配失效的现象，并称这两个匹配主体为匹配方案的阻塞对。为防止获得的匹配方案中出现这种现象，本书首先给出了阻塞对的概念，并进一步地给出了稳定匹配的概念。

定义5.4（阻塞对） 设一对一双边匹配μ：A∪B→A∪B，对任意的Ai，Ak∈A，Bj，Bh∈B，i≠k，h≠j，若可接受对（Ai，Bj）满足以下条件之一：（1）μ（Ai）=Ai，μ（Bj）=Bj；（2）μ（Ai）=Ai，μ（Bj）=Ak且βij＞βkj；（3）μ（Ai）=Bh，μ（Bj）=Bj且αij＞αih；（4）μ（Ai）=Bh，μ（Bj）=Ak且αij＞αih，βij＞βik，则称匹配方案μ被可接受对（Ai，Bj）阻塞，并称（Ai，Bj）为匹配方案μ的一个阻塞对。

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

由定义5.4和定义5.5可知，若匹配μ是稳定匹配，则μ一定是个体理性匹配。此外，不可接受对一定不会阻塞匹配方案，即不可接受对一定不是阻塞对。

（3）帕累托有效匹配(www.xing528.com)

在双边匹配问题中，帕累托有效性是衡量匹配方案优劣的另一个重要准则，主要用于度量双边主体匹配的总体效率。若一个匹配方案是非帕累托有效的，则表明在不损害其他匹配主体利益的情况下，匹配方案中的某些匹配主体可以获得更好的匹配结果。在给出帕累托有效匹配的概念之前，下面首先给出帕累托占优的概念。

定义5.6（帕累托占优） 设U为双边匹配方案的集合，μ，ν∈U，

并且至少存在一个Ai满足（1c）或（1d）或至少存在一个Bj满足（2c）或（2d），则称匹配方案μ占优匹配方案ν。

定义5.7（帕累托有效匹配） 设U为双边匹配方案的集合，μ∈U，若在U中不存在匹配方案占优μ，则称匹配方案μ为帕累托有效匹配。

在双边匹配中，若任意一个匹配主体对匹配方案μ中匹配对象的满意度大于对匹配方案ν中匹配对象的满意度，则称匹配方案μ帕累托弱占优匹配方案ν。下面给出帕累托弱占优的具体定义：

定义5.8（帕累托弱占优） 设U为双边匹配方案的集合，μ，ν∈U，若对于∀Ai∈A满足如下条件之一：

（1a）μ（Ai）=Bg，ν（Ai）=Bh且αig＞αih；（1b）μ（Ai）=Bg，ν（Ai）=Ai且αig＞αi=0；

同时，对于∀Bj∈B满足如下条件之一：

（2a）μ（Bj）=Af，ν（Bj）=Ak且βfj＞βkj；（2b）μ（Bj）=Af，ν（Bj）=Bj且βfj＞βj=0；

则称匹配方案μ弱占优匹配方案ν。

定义5.9（帕累托弱有效匹配） 设U为双边匹配方案的集合，μ∈U，若在U中不存在匹配方案弱占优μ，则称匹配方案μ为帕累托弱有效匹配。

由定义5.6—定义5.9可知，若一个匹配方案为帕累托有效匹配，则该匹配方案一定是帕累托弱有效匹配，反之未必成立。