首页 理论教育 双边匹配:一对多的解决方案

双边匹配:一对多的解决方案

时间:2023-07-17 理论教育 版权反馈
【摘要】:在现实中存在许多典型的一对多双边匹配问题,如大学录取问题、医院与实习生匹配问题等。首先给出一对多双边匹配定义的相关符号说明。中介依据上述双边主体给出的偏好序值信息,通过某种决策方法,获得甲乙双边主体最优的一对多双边匹配。根据μ确定的所有匹配对的集合称为一对多匹配方案μ。

双边匹配:一对多的解决方案

在现实生活中还存在这样一类决策问题:存在两个不同的双边主体集合,双边主体中的每个主体向中介提交对对方主体的偏好信息,一方主体中的每个主体期望与对方主体中的一个主体进行匹配,而另外一方主体中的每个主体期望与对方主体中的多个主体进行匹配,中介依据双边主体提交的偏好信息,通过某种决策分析方法获得双边主体都满意的匹配结果,这类决策问题通常被称为一对多双边匹配问题。在现实中存在许多典型的一对多双边匹配问题,如大学录取问题、医院与实习生匹配问题等。首先给出一对多双边匹配定义的相关符号说明。

设甲方主体集合为A={A1,A2,…,Am},其中Ai表示第i个甲方主体,i=1,2,…,m;乙方主体集合为B={B1,B2,…,Bn},其中Bj表示第j个乙方主体,j=1,2,…,n。每个甲方主体Ai最多与一个乙方主体进行匹配,而每个乙方主体Bj最多可以与qj个甲方主体进行匹配,qj∈N+,其中N+为正整数集,j=1,2,…,n,并且∃qh>1,h∈{1,2,…,n}。令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.2[38,52,372](一对多双边匹配) 一对多双边匹配可以定义为一个映射:μ:A∪B→2A∪B,且∀Ai∈A,∀Bj∈B满足以下条件:

(i)μ(Ai)⊆B,且|μ(Ai)|≤1。特别地,若|μ(Ai)|=0,则表示Ai没有匹配对象。

(ii)μ(Bj)⊆A,且|μ(Bj)|≤qj。特别地,若|μ(Bj)|=0,则表示Bj没有匹配对象。

(iii)μ(Ai)={Bj}当且仅当Ai∈μ(Bj)。

在定义1.2中,|μ(Ai)|和|μ(Bj)|分别表示与Ai匹配的乙方主体数量和与Bj匹配的甲方主体数量;μ(Ai)={Bj}或Ai∈μ(Bj)表示Ai与Bj进行匹配,并称(Ai,Bj)为Ai与Bj形成的匹配对。根据μ确定的所有匹配对的集合称为一对多匹配方案μ。(www.xing528.com)

中介依据上述双边主体给出的偏好序值信息,通过某种决策方法,获得甲乙双边主体都尽量满意的一对多双边匹配。不同于一对一双边匹配问题,在一对多双边匹配问题中,期望匹配多个甲方主体的乙方主体存在一个如何选择多个甲方主体的问题。乙方主体对多个甲方主体的偏好通常表现为响应性的(Responsiveness),下面给出响应性偏好的数学定义。

定义1.3[42] 在一对多双边匹配中,*A⊂A,|*A|<qj,对于∀Bj∈B若满足以下两个条件:

(i)对于∀Ai∈A\*A,*A∪{Ai}≻Bj*A当且仅当1≤sij≤m;

(ii)对于∀Ai,Ak∈A\*A,*A∪{Ai}≻Bj*A∪{Ak}当且仅当sij<sij

则称Bj的偏好是响应性的。

下面举例来说明响应性偏好的含义。

例1.1 设甲方主体集合为A={A1,A2,A3,A4,A5},乙方主体集合为B={B1,B2},q1=1,q2=3,甲乙双边主体的偏好序值信息构成的矩阵分别为

,若B2的偏好是响应性的,那么对B2而言,与{A4,A5}∪{A1}进行匹配要优于与{A4,A5}进行匹配;与{A4,A5}∪{A1}进行匹配要优于与{A4,A5}∪{A3}。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈