符号说明与问题描述的优化策略

本书提出的基于偏好序信息的大规模一对多双边匹配问题的描述如下：在研究的双边匹配问题中，一个甲方主体最多与一个乙方主体进行匹配，一个乙方主体最多可以与多个甲方主体进行匹配。双边主体采用偏好序信息表达对对方的偏好，甲方主体给出关于乙方主体的偏好序信息，乙方主体给出关于甲方主体的偏好序信息。双边匹配优化的目标是在考虑一对多稳定匹配的基础上，获得双边主体尽可能满意的匹配方案。上述双边匹配问题的研究目标是：依据甲方主体给出的关于乙方主体的偏好序信息，乙方主体给出的关于甲方主体的偏好序信息，如何降低匹配主体的规模，提高匹配的效率，并获得双边主体稳定和满意的匹配方案。

在本章研究的具有偏好序信息的一对多双边匹配问题中，设M={1，2，…，m}，N={1，2，…，n}，甲方主体集合为A={A1，A2，…，Am}，其中Ai表示第i个甲方主体，i∈M；乙方主体集合B={B1，B2，…，Bn}，其中Bj表示第j个乙方主体，j∈N。在本章考虑的一对多双边匹配问题中，每个甲方主体Ai最多只能与一个乙方主体进行匹配，而一个乙方主体Bj最多可以与qj个甲方主体进行匹配，qi∈N+，其中N+为正整数集。下面给出具有偏好序信息的一对多双边匹配问题的数学描述。

假设双边主体均给出严格偏好序信息。每个甲方主体Ai∈A针对乙方主体集合B的一个子集给出偏好列表P（Ai）=Bb，Bg，Bh，…，Bp，{Bb，Bg，Bh，…，Bp}⊆B，b≠g≠h≠…≠p∈N，其中P（Ai）=Bb，Bg，Bh，…，Bp表示甲方主体Ai认为乙方主体Bi优于Bg，Bg优于Bh，以此类推，即Bj在Ai偏好列表P（Ai）中的位置越靠前，则Ai认为Bj越优；否则，Ai认为Bj越差。此外，若Bj在Ai的偏好列表P（Ai）中，则表示Ai愿意与Bj进行匹配，即Ai认为Bj是可接受的；否则，Ai宁愿没有匹配对象也不愿意与Bj进行匹配，即Ai认为Bj是不可接受的。

每个乙方主体Bj∈B针对甲方主体集合A的一个子集给出偏好列表P（Bj）=Ad，As，At，…，Aq，d≠s≠t≠…≠q∈M，其中P（Bj）=Ad，As，At，…，Aq表示乙方主体Bj认为甲方主体Ad优于As，As优于At，以此类推，即Ai在Bj偏好列表P（Bj）中的位置越靠前，则Bj认为Ai越优；否则，Bj认为Ai越差。此外，若Ai在Bj的偏好列表P（Bj）中，则表示Bj愿意与Ai进行匹配，即Bj认为Ai是可接受的；否则，Bj宁愿没有匹配对象也不愿意与Ai进行匹配，即Bj认为Ai是不可接受的。P={P（A1），…，P（Am），P（B1），…，P（Bn）}表示所有匹配主体给出的偏好列表构成的集合。在双边匹配中，集合A和集合B以及偏好列表集合P构成的三元组（A，B；P）称为一个偏好结构（preference structure）。

为便于对双边主体的偏好关系进行表述，下面对以下符号进行说明。

Bj≻AiBg表示Ai认为乙方主体Bj优于Bg；类似地，Ai≻BjAk表示Bj认为甲方主体Ai优于Ak。(https://www.xing528.com)

Bj■AiBg表示Ai认为乙方主体Bj不劣于Bg；类似地，Ai■BjAk表示Bj表示认为甲方主体Ai不劣于Ak。

Bj≻AiAi表示Ai认为与乙方主体Bj匹配要优于没有匹配对象，即Bj是可接受的；类似地，Ai≻BjBj表示Bj认为与甲方主体Ai匹配要优于没有匹配对象，即Ai是可接受的。

Ai≻AiBj表示Ai认为宁愿没有匹配对象也优于与Bj匹配，即Ai认为Bj是不可接受的；类似地，Bj≻BjAi表示Bj认为宁愿没有匹配对象也优于与Ai匹配，即Bj认为Ai是不可接受的。

在本章研究的一对多双边匹配问题中，若Bj在Ai的偏好列表P（Ai）中，则令rA（i，j）表示Bj在Ai的偏好列表P（Ai）中的排序位置（简称序值），rA（i，j）∈N，i∈M，j∈N；若Ai在Bj的偏好列表P（Bj）中，则令rB（i，j）表示Ai在Bj的偏好列表P（Bj）中的排序位置（简称序值），rB（i，j）∈M，i∈M，j∈N。显然，rA（i，j）和rB（i，j）越小，则Ai对Bj和Bj对Ai的满意度越高，反之亦然。