基于序区间偏好的一对多双边匹配的相关概念及稳定性分析

下面对基于序区间偏好信息的一对多双边匹配问题中的相关概念进行界定。

在一对多双边匹配问题中，对于∀Ai∈A，∀Bj∈B，若（Ai，Bj）∈A×B满足且，则称（Ai，Bj）为可接受对；否则，称为不可接受对。

在匹配方案中，若某一个匹配主体的匹配对象对该匹配主体而言是不可接受的，则称匹配方案被该匹配主体个体阻塞，并称该匹配方案是非个体理性匹配。下面给出个体阻塞和个体理性匹配的具体定义。

定义4.1（个体阻塞） 在一对多双边匹配μ中，若μ（Ai）={Bk}且n+1，则称匹配μ被Ai个体阻塞；若Ah∈μ（Bj）且，则称匹配μ被Bj个体阻塞。

定义4.2（个体理性匹配） 在一对多双边匹配μ中，若匹配μ不被任意Ai∈A和任意Bj∈B个体阻塞，则称匹配μ为个体理性匹配。

由定义4.1和定义4.2可知，若匹配方案μ是个体理性匹配，则μ中的任意一个匹配对都是可接受对。

下面给出匹配个体之间的α-优于关系的定义。

定义4.3（α-优于关系） 在具有序区间偏好信息的双边匹配问题中，对于Ai，Ak∈A，Bj，Bh∈B，若，则称Ai认为Bjα-优于Bh；若，则称Bj认为Aiα-优于Ak。

在现实的双边匹配中，匹配主体要放弃当前的匹配对象与另外一个匹配主体进行匹配，有时不仅需要另外一个匹配主体优于当前的匹配对象，可能还需要优于的程度满足一定的阈值α（1≤α≤max{m+1，n+1}）。为此，本书引入α-稳定阻塞对的概念，并进一步地给出α-稳定匹配的概念。

下面给出α-稳定阻塞对的数学定义。(www.xing528.com)

定义4.4（α-阻塞对） 设一对多双边匹配μ：A∪B→2A∪B，对任意的Ai，Ak∈A，Bj，Bh∈B，i≠k，h≠j，在是可接受对的情况下，若Ai和Bj满足如下条件之一：

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

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

（iii）|μ（Ai）|=0，|μ（Bj）|=qj，且；

（iv）μ（Ai）|={Bh}，|μ（Bj）|=qj，且，

则称匹配方案μ被可接受对（Ai，Bj）α-阻塞，并称（Ai，Bj）为α-稳定阻塞对。

定义4.5（α-稳定匹配） 在一对多双边匹配μ中，若μ是个体理性匹配并且μ中不存在α-稳定阻塞对，则称匹配方案μ为α-稳定匹配。

由定义4.4和定义4.5可知，若匹配μ是α-稳定匹配，则μ一定是个体理性匹配，并且任意的不可接受对一定不是α-稳定阻塞对。此外，当α=1时的α-稳定匹配通常被称为稳定匹配。

本节要解决的问题是：依据甲方主体Ai给出的序区间形式的偏好向量，i=1，2，…，m，和乙方主体Bj给出的序区间形式的偏好向量，通过某种决策方法，在考虑双边匹配稳定性的情况下获得双边匹配主体的一对多最优匹配方案。