一对一双边匹配的优化方案

在现实生活中存在这样一类决策问题：存在两个不同的双边主体集合，双边主体中的每个主体向中介提交对对方主体的偏好信息，并期望与对方主体中的一个主体进行匹配，中介依据双边主体提交的偏好信息，通过某种决策分析方法获得双边主体都满意的匹配结果，这类决策问题通常被称为一对一双边匹配问题。在双边匹配中，中介不仅为双边主体提供信息交流沟通的平台，同时还扮演着决策者的角色，负责撮合双边主体达成合理的匹配。需要指出的是，这里的中介是负责双边匹配的个人、机构或决策支持系统。在现实中存在许多典型的一对一双边匹配问题，如婚姻匹配问题、家政服务人员与雇主的匹配问题等。为便于对一对一双边匹配的定义进行描述，首先给出相关符号说明。

设甲方主体集合为A={A1，A2，…，Am}，其中Ai表示第i个甲方主体，i=1，2，…，m；乙方主体集合为B={B1，B2，…，Bn}，其中Bj表示第j个乙方主体，j=1，2，…，n。每个甲方主体Ai最多与一个乙方主体进行匹配，每个乙方主体Bj也最多与一个甲方主体进行匹配。令Ri=（ri1，ri2，…，rin）为甲方主体Ai给出的关于乙方主体的序值向量，其中rij表示在n个乙方主体中，甲方主体Ai把乙方主体Bj排在第rij个位置，1≤rij≤n+1；令Sj=（s1j，s2j，…，smj）表示乙方主体Bj给出的关于甲方主体的序值向量，其中sij表示在m个甲方主体中，乙方主体Bj把甲方主体Ai排在第sij个位置，1≤sij≤m+1。需要指出的是，在双边主体给出的偏好序值信息中，若1≤rij≤n，则表示甲方主体Ai认为乙方主体Bj是可接受的；若rij=n+1，则表示是不可接受的。类似地，若1≤sij≤m，则表示乙方主体Bj认为甲方主体Ai是可接受的；若sij=m+1，则表示是不可接受的。此外，若甲方主体Ai对Bj和Bh有相同的偏好，即存在无差异偏好，则rij=rih，j≠h；同样的，若乙方主体Bj对Ai和Ak有相同的偏好，则sij=skj，i≠k。

中介依据上述双边主体给出的偏好序值信息，通过某种决策方法，获得甲方双边主体最优的一对一双边匹配。

下面给出一对一双边匹配的定义。

定义1.1[38，52，372]（一对一双边匹配） 一对一双边匹配可以定义为一一映射：μ：A∪B→A∪B，且∀Ai∈A，∀Bj∈B，满足以下条件：(www.xing528.com)

（i）若μ（Ai）∉B，则μ（Ai）=Ai；

（ii）若μ（Bj）∉A，则μ（Bj）=Bj；

（iii）μ（Ai）=Bj当且仅当μ（Bj）=Ai。

在定义1.1中，μ（Ai）=Bj或μ（Bj）=Ai表示Ai与Bj进行匹配，并称（Ai，Bj）为Ai与Bj在匹配方案μ中形成的匹配对。特别地，在匹配μ中，μ（Ai）=Ai表示Ai没有匹配对象；同样μ（Bj）=Bj表示Bj没有匹配对象。根据μ确定的所有匹配对的集合称为一对一双边匹配方案μ，显然，匹配方案μ中匹配对的数量不大于min{m，n}。