双边匹配的相关概念及优化方法

令αij表示甲方主体Ai对乙方主体Bj的总体满意度，βij表示乙方主体Bj对甲方主体Ai的总体满意度。在匹配μ中，对于任意的Ai∈A，Bj∈B，有

（1）若μ（Ai）=Ai，则甲方主体Ai的满意度为0；

（2）若μ（Bj）=Bj，则乙方主体Bj的满意度为0；

（3）若μ（Ai）=Bj，μ（Bj）=Ai，则甲方主体Ai的满意度αij＞0，乙方主体Bj的满意度βij＞0。

U={μ1，μ2，…，μt}表示对应于集合A和集合B的所有稳定匹配构成的集合。其中μh是U中的第h个稳定匹配，h=1，2，…，t，不妨设

。

定义3.1 设任意的Ai，Bj，i∈M，j∈N，μ∈U，如果Ai在μAopt∈U中的满意度αij，j∈N与在μ中的满意度αik，k∈N满足αij≥αik，那么稳定匹配μAopt称为甲方主体最优稳定匹配；同理，如果任意的Bj，j∈N在μBopt∈U中的满意度βij，i∈M与任意的μ∈U中的满意度βhj，h∈M满足βij≥βhj，那么稳定匹配μBopt称为乙方主体最优稳定匹配。

对于任意的两个稳定匹配μ，μ′∈U，令Mμ和Wμ分别表示在μ中的满意度大于或等于在μ′的满意度的甲方主体和乙方主体构成的集合；Mμ′和Wμ′表示在μ′中的满意度大于或等于在μ中的满意度的甲方主体和乙方主体构成的集合。σ（Mμ）表示与集合Mu中的甲方主体匹配的乙方主体集合，σ（Wμ′）表示与集合Wμ′中的乙方主体匹配的甲方主体集合。

引理3.1 σ（Mμ）⊂Wμ′与σ（Wμ′）⊂Mμ

证明：对于任意的Ai∈A，Bj，Bh∈B，j≠h，μ，μ′∈U，设μ（Ai）=Bj，μ′（Ai）=Bh且Ai∈Mμ，即αij＞αih。

（1）当μ′（Bj）=Bj时，那么显然这种情况不存在，因为μ′（Ai）=Bh，αij＞αih，因此根据定稳定匹配的定义可知，匹配对（Ai，Bj）在稳定匹配μ′中是一个阻塞匹配对。

（2）当μ′（Bj）=Ak时，假设βij＞βkj成立，由于μ′（Ai）=Bh且αij＞αih，因此根据稳定匹配定义可知，匹配对（Ai，Bj）在稳定匹配μ′中是一个阻塞匹配对。(www.xing528.com)

综上（1）和（2）可知不可能存在βij＞βkj，所以βij≤βkj，即Bj∈Wμ′。因此，对于稳定匹配μ和μ′中的所有匹配对有σ（Mμ）⊂Wμ′。

同理可证，σ（Wμ′）⊂Mμ。

定理3.1 在甲方主体最优稳定匹配μAopt中，与甲方主体匹配的每个乙方主体的满意度是所有稳定匹配中最低的；在乙方主体最优稳定匹配μBopt中，每个甲方主体的满意度也是所有稳定匹配中最低的。

证明：对于任意的μh∈U，Mμh和Wμh分别表示在匹配μh中的满意度大于或等于在匹配μAopt中的所有甲方主体和乙方主体构成的集合；MμAopt和WμAopt分别表示在匹配μAopt中的满意度大于或等于在匹配μh中的满意度的所有甲方主体和乙方主体构成的集合。根据定义3.1中甲方主体最优稳定匹配的定义可知MμAopt=A，由引理3.1可得μAopt（A）⊂Wμh，即在匹配μAopt中与甲方主体匹配的所有乙方主体都认为在μh的满意度大于或等于在匹配的满意度μAopt。因此，在μAopt中与甲方主体匹配的乙方主体的满意度是所有稳定匹配中最低的。

同理可证，在乙方主体最优稳定匹配μBopt中，每个甲方主体的满意度也是所有稳定匹配中最低的。证毕

在稳定匹配μh∈U中，cm（μh）表示所有甲方主体的总体满意度，cw（μh）表示所有乙方主体的总体满意度，c（μh）表示所有甲方主体和所有乙方主体总体满意度的差值。

由定理3.1容易证明如下推论3.1：

推论3.1 对于任意的μh∈U，μh≠μAopt，μh≠μBopt，则有cm（μBopt）＜cm（μh）＜cm（μAopt）和cw（μAopt）＜cw（μh）＜cw（μBopt）。

定义3.2 在双边匹配中，使甲方主体满意度和乙方主体满意度差值的绝对值达到最小的稳定匹配称为双边匹配主体的公平稳定匹配。如果甲乙双方主体的满意度满足|c（μh）|=0，则称稳定匹配μh为绝对公平稳定匹配；如果满足|c（μh）|＞0，则称稳定匹配μh为近似公平稳定匹配。

依据推论3.1和定义3.2可知，甲方主体最优稳定匹配和乙方主体最优稳定匹配是一种不公平的稳定匹配，通过定义3.2获得的稳定匹配是一种使甲乙双方主体都能接受的公平稳定匹配。本章要解决的问题是依据甲方主体对乙方主体的多指标评价信息和乙方主体对甲方主体的多指标评价信息，通过采用有效的决策方法将甲方主体与乙方主体进行匹配，在考虑匹配稳定性的情形下，获得定义3.2中的公平匹配方案。