符号说明与问题描述详解

本书提出的考虑单边互惠偏好信息的稳定双边匹配问题描述如下：在研究的双边匹配问题中，一个甲方主体最多与一个乙方主体进行匹配，一个乙方主体最多与一个甲方主体进行匹配。甲方主体给出关于乙方主体的个体偏好序信息，乙方主体根据甲方主体给出的偏好序信息给出关于甲方主体的互惠偏好序信息，双边匹配优化的目标是在考虑双边主体稳定性的情况下，获得双边主体总体满意度最大的匹配方案。上述双边匹配问题的研究目标是：依据甲方主体对乙方主体的个体偏好序信息以及乙方主体的互惠偏好序信息，提出一个有效的双边匹配方法，获得双边主体稳定和满意的匹配方案。

设甲方主体集合为A={A1，A2，…，Am}，其中Ai表示第i个甲方主体，i=1，2，…，m；乙方主体集合为B={B1，B2，…，Bn}，其中Bj表示第j个乙方主体，j=1，2，…，n，且m≤n。本书考虑的是一对一双边匹配问题，即一个甲方主体Ai最多与一个乙方主体进行匹配，而一个乙方主体Bj也最多与一个甲方主体进行匹配。

为便于叙述，本书将甲方主体Ai对乙方主体Bj的偏好称为Ai的个体偏好；将Bj对于自己在Ai偏好列表中的排序位置所产生的偏好称为Bj的互惠偏好。本书要解决的是这样一类双边匹配问题，甲方主体对乙方主体具有严格的个体偏好信息，乙方主体对甲方主体具有无差异偏好信息，即乙方主体无法通过对甲方主体的个体偏好来选择最优的甲方主体，由此，乙方主体需要考虑对甲方主体的互惠偏好信息，如图5.2所示。其中，表示Ai对Bj的个体偏好，表示Bj对Ai的互惠偏好，‘’表示Ai和Bj进行匹配，形成匹配对（Ai，Bj），所有的‘’连接的匹配对（Ai，Bj）构成一个匹配方案。

图5.2　考虑单边互惠偏好信息的一对一双边匹配问题(www.xing528.com)

下面给出考虑单边互惠偏好信息的双边匹配问题的数学描述。

令R=[rij]m×n为甲方主体给出的关于乙方主体的个体偏好排序矩阵，i=1，2，…，m；j=1，2，…，n。其中rij是Ai给出的关于Bj的个体偏好排序值，具体表示在n个乙方主体中，Ai把Bj排在第rij个位置，1≤rij≤n，且rij越小，表示Ai认为Bj越优，反之亦然。不失一般性，rij=1表示Ai认为Bj是所有乙方主体中最优的；rij=n表示Ai认为Bj是所有可接受的乙方主体中最差的。

设T=[tij]m×n为乙方主体的互惠偏好排序矩阵，其中tij表示乙方主体Bj对甲方主体Ai产生的互惠偏好排序值，i=1，2，…，m；j=1，2，…，n。在本书乙方主体Bj考虑互惠偏好的双边匹配问题中，甲方主体Ai给出的Bj的偏好排序值rij越小，即Bj在Ai偏好排序列表中的位置越靠前，Bj认为Ai越优，那么，Bj给出的Ai的偏好排序值越小，反之亦然。不失一般性，若rij=1，则Bj认为Ai是所有甲方主体中最优的；若rij=n，则Bj认为Ai是所有可接受的甲方主体中最差的。

本书要解决的问题是：依据甲方主体给出的个体偏好信息以及在此基础上乙方主体产生的互惠偏好，采用某种双边匹配决策方法，获得双边主体都尽可能满意的稳定匹配方案。