相关概念的界定和解释

（1）单边互惠稳定匹配

在考虑单边互惠偏好的双边匹配方案中，没有形成匹配对的甲方和乙方两个匹配主体，如果甲方主体认为乙方主体要优于当前的匹配对象，而乙方主体认为与当前匹配对象给出的排序位置相比，甲方主体把自己排在更靠前的排序位置上，由此将造成匹配方案的不稳定性[19-20]。为防止获得的匹配方案中出现这种情况，本节首先给出了单边互惠阻塞对的概念，并进一步地给出了单边互惠稳定匹配的概念。

定义5.10（单边互惠阻塞对） 设一对一双边匹配μ：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且rij＜rkj；（3）μ（Ai）=Bh，μ（Bj）=Bj且rij＜rih；（4）μ（Ai）=Bh，μ（Bj）=Ak且rij＜rih，rij＜rkj则称匹配方案μ被可接受对（Ai，Bj）阻塞，并称（Ai，Bj）为匹配方案μ的一个单边互惠阻塞对。

定义5.11（单边互惠稳定匹配） 设一对一双边匹配μ：A∪B→A∪B，若匹配方案μ中不存在个单边互惠阻塞对，则称μ为单边互惠稳定匹配。

定理5.6（单边互惠稳定匹配的存在性） 具有单边互惠偏好的双边匹配问题的单边互惠稳定匹配集合是非空的。

证明：为了证明考虑单边互惠偏好的双边匹配问题的单边互惠稳定匹配存在性，本书首先给出了一个扩展的G-S算法。扩展G-S算法的具体流程如下：

Step 1：每个甲方主体都向偏好列表中可接受的且排序位置为第1位的乙方主体发出申请。收到申请的每个乙方主体选择把自己排在偏好列表中最靠前的甲方主体，拒绝其他甲方主体。若向乙方主体发出申请的甲方主体中，同时存在多个甲方主体都把乙方主体排在最靠前位置，即存在多个乙方主体最偏好的甲方主体，则乙方主体随机选择一个甲方主体，拒绝其他甲方主体。

Step t＞1：在t-1步中被拒绝的甲方主体，向其偏好列表中下一个可接受的且最偏好的乙方主体发出申请。每个乙方主体从最新收到的申请和t-1步中暂时接受的甲方主体中，选择把自己排在最靠前位置的甲方主体，拒绝其他甲方主体。若把乙方主体排在最靠前位置的甲方主体同时有多个，则乙方主体随机选择一个甲方主体，拒绝其他甲方主体。

Stop：每个甲方主体要么发出的申请被乙方主体接受，要么已经被偏好列表中的所有乙方主体拒绝。

假设通过扩展G-S算法获得的匹配方案为μ，可以证明μ一定是稳定匹配。假设在匹配方案μ中，相互可接受的Ai和Bj没有形成匹配，且Ai认为Bj优于μ（Ai），那说明在算法过程中Ai曾经向Bj发出过申请，但由于μ（Bj）给出的Bj的排序位置比Ai给出的Bj的排序位置更靠前，因而Bj拒绝了Ai，或者Ai和μ（Bj）给出的Bj的排序位置是相同的，但算法随机选择了μ（Bj）而拒绝了Ai。由此可知，对Bj而言μ（Bj）不劣于Ai，那么由定义5.10可知，可接受对（Ai，Bj）不会阻塞μ，因此，μ一定是稳定匹配。(www.xing528.com)

综上可知，具有单边互惠偏好的双边匹配问题的单边互惠稳定匹配集合一定是非空的。证毕

（2）帕累托有效匹配

在双边匹配中，帕累托有效性是另外一个度量双边匹配方案优劣的重要准则。依据帕累托有效性针对的匹配主体不同，可以分为甲方主体帕累托有效性和乙方主体帕累托有效性。下面首先给出甲方主体帕累托占优和甲方主体帕累托有效匹配的概念。

对于某个匹配方案，若不存在一个甲方主体在不损害其他甲方主体利益的情况下，可以获得更好的匹配对象，则称该匹配方案为甲方主体帕累托有效匹配。在给出甲方主体帕累托有效匹配的具体定义之前，下面首先给出甲方主体帕累托占优的定义。

定义5.12（甲方主体帕累托占优） 设U为双边匹配方案的集合，μ，ν∈U，对于∀Ai∈A满足以下条件之一：（a）μ（Ai）=Ai，ν（Ai）=Ai；（b）μ（Ai）=Bg，ν（Ai）=Bh，且rig=rih；（c）μ（Ai）=Bg，ν（Ai）=Bh，且rig＜rih；（d）μ（Ai）=Bg，ν（Ai）=Ai，且1≤rig≤n，并且至少存在一个Ai满足（c）或（d），则称对甲方主体而言，匹配方案μ占优匹配方案ν。

定义5.13（甲方主体帕累托有效匹配） 设U为双边匹配方案的集合，μ∈U，对于甲方主体而言，若在U中不存在匹配方案占优μ，则称匹配方案μ为甲方主体帕累托有效匹配。

类似地，可以给出乙方主体帕累托占优和乙方主体帕累托有效匹配的定义。对于某个匹配方案，若不存在一个乙方主体在不损害其他乙方主体利益的情况下，可以获得更好的匹配对象，则称该匹配方案为乙方主体帕累托有效匹配。

定义5.14（乙方主体帕累托占优） 设U为双边匹配方案的集合，μ，ν∈U，对于∀Bj∈B满足以下条件之一：（a）μ（Bj）=Bj，ν（Bj）=Bj；（b）μ（Bj）=Af，ν（Bj）=Ak，且rfj=rkj；（c）μ（Bj）=Af，ν（Bj）=Ak，且rfj＜rkj；（d）μ（Bj）=Af，ν（Bj）=Bj，且1≤rfj≤n，并且至少存在一个Bj满足（c）或（d），则称对乙方主体而言，匹配方案μ占优匹配方案ν。

定义5.15（乙方主体帕累托有效匹配） 设U为双边匹配方案的集合，μ∈U，对于乙方主体而言，若在U中不存在匹配方案占优μ，则称匹配方案μ为乙方主体帕累托有效匹配。