论文研究-基于偏好序的抗操作和抗自亏双边匹配方法.pdf

论文研究-基于偏好序的抗操作和抗自亏双边匹配方法.pdf,  针对基于偏好序的双边匹配问题,提出了具有抗操作和抗自亏性的匹配方法.具体地,首先,给出了稳定匹配方案和帕累托有效匹配方案的定义,以及匹配方法的抗操作性和抗自亏性定义.然后,通过借鉴经典G-S算法的思想,设计了确定最优匹配方案的IG-S算法.进一步地,讨论IG-S算法的特点,并证明了IG-S算法的合理性.最后,通过一个算例表明所提方
第2期 姜艳萍,等:基于偏好序约抗操作和抗自亏双边匹配方法 475 匹配方法须具有抗操作性和抗自亏性.同时,一个好的匹配方案,不仅可以尽可能反映匹配主体的偏好序,还 应该是稳定并且帕累托有效的.下面根据匹配主体双方给出的偏好序,对稳定匹配方案、帕累托有效匹配方 案、匹配方法的抗操作性和抗自亏性进行数学描述. 设e;利d分别表示甲方匹配主体A关于乙方匹配主体B;以及乙方匹配主体B;关于甲方匹配主 体Δ;的偏好序值.e越小,A;越偏好于与B;匹配同时d越小、B;越偏好于与A匹配需要指出的 是,由于匹配主体双方提出的偏好序中包含了三种形式的偏好关系,因此所对应的偏好序值也具有三种大小 关系.不失一般性,以任意两个乙方匹配主体B,和B为例,若A;给出的偏好序为B>B则>cn; 若B;~B,则6-C;若B?B,则cn?e 31稳定匹配方案 所谓稳定匹配方案是指匹配方案中形成匹配对的任意一方匹配主体,除当前匹配对象以外,无法找到新 的匹配对象,使得该匹配主体与新匹配对象的满意程度同时超过对各自现有匹配对象的满意程度 根据上述描述,下面首先给出稳定匹配方案的数学定义 定义2对于双边匹配p:A∪B→A∪B所确定的匹配方案,VA,A∈A,Bk,B1∈B,t≠l,k≠j 其中p(A)=B,(41)=Bk,若(A1,B;)和(A,Bk)满足如下五个条件之一:1)e>c且dk≤dk;2) e≤ei且k>dk;3)e≤e且dk≤dik:4)∈;?eak;5)dk?dk·则称该匹配方案为稳定匹配方案,否 则称为不稳定匹配方案 从定义2米看,条件1)说明了A相比匹配对象B;更偏好Bk:但Bk更偏好现匹配对象A的情形; 条件2)说明了B相比匹配对象A更偏好A2,但A更偏好现匹配对象乃;的情形;条件3)说明了A和 Bk均更偏好现匹配对象B;和A;条件4)说明了A;无法判断现匹配对象B,和Bk之间的偏好关系的情 形;条件5)说明了乙方匹配主体Bk无法判断现匹配对象A;和A之间的偏好关系的情形 定义2中的稳定双边匹配方案实际上是传统稳定匹配方案定义的扩充即定义2中的4)和5)重点考虑 了匹配主体双方给出无法判断偏好关系的情形,反映了当无法判断当前匹配对象与其它对方匹配主体之间的 偏好关系时,甲方匹配主体或乙方匹配主体宁愿与当前匹配对象进行匹配.事实上,可以为“优于(>)”、等 价于()”或“劣于()”,并且为“优于(x)”、“等价于(~)”和“劣于(3)”的概率均等例如,设Pr(n< e)、Pr(e;=enk)和Pr(e>E)分别表示A2认为B优于Bk、B;等价于Bk和B,劣于Bk的概率,当 满足cn?ei时,则Pr(ei<e;k)=Pr(e;=eik)=Pr(eni>e)=1/3.本文假设匹配主休均是风险中性的, 显然,?e无法使得A;放弃原匹配对象乃;而选择乃k 32帕累托有效匹配方案 帕累托有效匹配方案主要考虑了两种情形:1)无法使得所有匹配主体获得比当前匹配方案更好的匹配 对象:2)当一方所有匹配主体获得更好匹配对象时,另一方所有匹配主体只能获得比当前匹配方案较差的匹 配对象:具体地.下面给出帕累托有效匹配方案的数学定义 定义3对于任意的匹配方案u和p,如果满足如下两个条件 1)对于∨A∈A.设(A)=B3,(A)=BkB,Bk∈B,A;在中的匹配对象均不劣于在1中的 匹配对象即c;≤cik;同时,至少存在一个甲方匹配主体A1∈A,1(A1)-Bn,(A)-Bn,B,Bn∈B,满 足At在中的匹配对象优于在p中的匹配对象,即c1<cn; 2)对于VB;∈B,设(B1)=A1,p1(B,)=At,A,At∈A,B,在中的匹配对象均不劣于在中的 匹配对象.即dx≤dt;同时,至少存在一个甲方匹配主体Bk∈B,p(Bk)=4p,p1(Bk)=Ar,Ap,A∈A 满足Bk在1中的匹配对象优于在1中的匹配对象,即dnk<dmk;则称匹配方案u帕累托占优于匹配方案 特别地,如果没有其他匹配方案帕累托占优于匹配方案P,则称为帕累托有效匹配方案;如果某个匹 配方案帕累托占优其他所有匹配方案,则称该方案为帕累托最优匹配方案 3.3匹配方法的抗操作性 所谓具有抗操作性的匹配方法主要是指对于任意一个匹配主体,无法在故意提供错误偏好序的情形下, 获得比当前匹配方案更好的匹配对象.如果一个匹配方法不具有抗操作性,那它就不能保证匹配主体双方提 供自己真实的偏好序15 定义4设、1′和p"是采用匹配方法M获得的三个匹配方案,其中,μ为所有匹配主体给出真实偏 476 系统工程理论与实践 第36卷 奷序时确定旳匹配方案,μ和μ″分别为A;和B故意给出错误偏好序、而其他所有匹配主体给出真实偏 好序时的匹配方案.不妨设1(4:)=B,p(A)=Bk,1(B3)=A,A1,A∈A,B;,Bk∈B若|同时满足 如下两个条件:1)≤或ex?eik;2)d;≤或d;?l;则称M具有抗操作性 注1当A(或B)给出错误偏好序时,Aa(或B;)的偏好序会因此改变,但不影响对方匹配主体对A (或B3,)的偏好序 注2≤C认或e;?ek,表明甲方匹配主体A更偏好选择提供真实偏好序时的匹配对象B; 注3d≤d或d;'l;表明乙方匹配主体B;更偏奷选择提供真实偏好序时的匹配对象A2 为了说明匹配方法的抗操作性,下面给出一个例子 例1假没一个匹配方法M为:每个甲方匹配主体首先向当前最偏好的乙方匹配主体提出意向,若乙方 匹配主体当前只收到一个甲方匹配主体提出的意向.则该甲方匹配主体与乙方匹配主体匹配,并一起退出匹 配流程:若乙方匹配主体当前收到多个甲方匹配主体提出的意向,则乙方匹配主体从多个意向中,选择当前 最偏好的甲方匹配主体进行匹配,并与所选中的甲方匹配主体一起退出匹配流程;剩余的甲方匹配主体和乙 方匹配主体重复上述过程,直到所有的甲方匹配主体无法提出新的匹配意向或所有的甲方匹配主体都匹配上 为止,则匹配结束 设由m=3个甲方匹配主休A1,A2,A3和m=4个乙方匹配主休B1,B2,B3,B4参与的双边匹配问题 中,甲方匹配主体和乙方匹配主体提供的偏好序为 A1:B2×B1>乃3~B4:B1:A2xA1>A3; A2:B2×B4>B3~B1:乃2:A3>42>A1 A3: B1> B2?B> B3: B3: A3 >A1>A B: A1>A2 >A 则根据匹配方法M,可以得到匹配方案={(A1,B3),(A2,B2).(A3,B1)} 假设叩方匹配主体A1提出错误的偏好序为:B1>B2>B3~B4,而其他甲方匹配主体和乙方匹配主 体给出的偏好序不变,此时根据匹配方法M,可得到匹配方案′={(A1,B1),(A2,B2),(43,B3)} 通过将匹配方案μ和μ′进行对比,并结合甲方匹配主体A1提供的真实偏好序,发现相较于乙方匹配 主体B3,甲方匹配主体A1对匹配方案p中的匹配对象B1更为满意,即e1<e13,表明甲方匹配主体A1 可以通过提供错误偏好序的方式,使自己获得更好的匹配对象,从而说明匹配方法M不是抗操作的 4匹配方法的抗自亏性 所谓白亏属性信息是指匹配主体故意隐藏白身部分优点时针对属性给出的信息.具备抗白亏性的匹配 方法是指对于任意一个匹配主休,无法在故意提供自亏属性信息的情形下,获得比当前匹配方案更好的匹配 对象.如果一个机制不是抗自亏的,那它就不能保证匹配主体提供真实的属性信息,从而使得对方匹配主体 无法对其给出真实的判断 定义5设、1′和1”是采用匹配方法M获得的三个匹配方案,其中,1为所有匹配主体给出真实属 性信息时确定的匹配方案,μ和∥"分别为A;和B,故意给出自亏属性信息、而其他所有匹配主体给出真 实属性信息时的匹配方案.不妨设p(A2)=B,1(A1)-Bk,(B3)-A,A,A1∈A,B3,Bk∈B,若p同 时满足如下两个条件:1)c≤ci或c;?ei;2)d≤dl;或d?d1,则称M具有抗自亏性 注4当A(或B)给岀镨误偏好序时,其不影响自已给岀的偏好序,同时也不影响对方匹配主体对除 A1和B其他匹配主体的偏好序,但相对于提供真实信息,A(或B3)却会因此排在对方匹配主体给出的偏 好序中较靠后的位置 注5≤e或e;?e,表明甲方匹配主休A;更偏好选择给出真实属性信息时的匹配对象B 注6d≤d;或di;'ω,表明乙方匹配主体B;更偏好选择给出真实属性信息时的匹配对象A 为了说明匹配方法的抗自亏性,下面仍然以例1中的匹配方法M和相应双边匹配问题为例 例2设由m=3个甲方匹配主体A1,A2,A3和m=4个乙方匹配主体B1,B2,B3,B4参与的双边匹 配问题中,甲方匹配主体和乙方匹配主体提供的偏好序与例1相同.则依据匹配方法M,可以得到匹配方案 1={(A1,B3),(A2,B2),(A3,B1)} 现假设乙方匹配主体B2提供自亏信息,则此时三个甲方匹配主体提出的新偏好序为 A1:B1>B2>B3~B4;A2:B4>B3~B1B2;A3:B1>B4>B2>B3 第2期 姜艳萍,等:基于偏好序约抗操作和抗自亏双边匹配方法 477 从三个甲方匹配主体提供的偏好序来看,当乙方匹配主体B2提供自亏属性信息时,其在对方匹配主体的 偏好序列表中的位置均有所韋后,此时依据匹配方法M,可以得到如下的匹配方案"={(41,B1),(A2,B4), (A3,B2)} 通过将匹配方案μ和μ″进行对比并结合乙方匹配主体B2提供的真实偏好序,发现相较于甲方匹配 主体A2,乙方匹配主体B2对匹配方案1"中的匹配对象A3更为满意,即d3<d22,表明乙方匹配主体B2 可以通过提供自亏属性信息的方式,使自己获得更好的匹配对象,从而说明匹配方法M不是抗自亏的 4匹配方法 41基于偏好序的IG-S( Improved G-S)算法 通过倩鉴经典GS算法的思想,本文给出了基于偏好序IG-S算法.该算法的核心思想为:每个甲方 匹配主体首先向当前最偏好的乙方匹配主体提出意向.若甲方匹配主体当前有多个等价最偏好的或多个无 法判断的乙方匹配主体,则该甲方匹配主体分别向多个乙方匹配主体提出匹配意向;然后,乙方匹配主体在 收到的多个匹配意向中,选择最偏妤的甲方匹配主体,并与当前匹配对象进行比较,从而确定最优的匹配对 象若某一乙方匹配主体当前的意向列表中有多个等价最偏好的或多个无法判断的甲方匹配主体,则通过某 种分析方法(如标记操作等)进行选择;进一步地,被选中的甲方匹配主体进行反选:若选择该乙方匹配主体, 则拒绝其他乙方匹配主体;若没有选择该甲方匹配主体,则乙方匹配主体从其意向中删除这个甲方匹配主体, 重新进行选择,直到选择到反选时亦选择其的甲方匹配主体或者在意向列表中再也无法选择甲方匹配主体时 为止.被拒绝的匹配主体重复上述步骤,直至没有被拒绝或无法提出意向为止 下面给出具体的算法,首先对算法中使用的变量进行描述 设l为迭代变量,P(为第l次选代中符合A1偏好的对方匹配主体集合,P2∈B:Q吕,,第L次迭 代中B收到匹配意向的乙方匹配主体集合,QB,cA;A(1为第t次迭代中只提出一个吧配意向的甲方 匹配主体集合,A()2为第次迭代中提出多个等价最偏好匹配意向的甲方匹配主体集合,A()3为第次迭 代中提出多个无法判断匹配意向的甲方匹配主体集合,A)1,A)2,A3cA,A1UA2UA(3-A且 A(b∩A=0,u≠,t,v=1,2,3.设U(和V(分别表示第t次迭代中尚未匹配和已经匹配的甲方匹 配主体集合,可见,U()uV(=A,U(n(=0;设(为第t次迭代中获得的匹配方案 本文提出的IGS算法可描述如下: Step1迭代变量初始化令迭代变量t-1,P(1)-B,QB)-0,U(1)-A,V(1)=0.p()(4)-0, )(B)=0 Step2判断A提出的匹配意向类型若A;∈A(1,则转Step3;若A;∈A(2,则转Step4:若 A2∈A3,则转Step5; step3A∈A)1向最偏好的乙方配主体提出匹配意向设B(om表示A,在PA中最偏好的唯一 乙方匹配主体,即若B(1y∈PA,E:()my=min(e,B∈P4(},则QB ∪{A;},转Step6 step4A,∈4(2提出多个等价最偏好的匹配意向设B24在PA中多个等价最偏好的乙方匹配 主体组成的集合,即若对于ⅤB(m∈B2sPA,y-1,2,…,|B(2其中|B(2为集合Bu2的基数有 e(= min cij,B3∈P(.则Qm=QU4小,转 Step54∈A(2提出多个元法判断的匹配意向设B3A在PA0多个无法判断的乙方匹配主体组成 的集合,即若对于B(0)m,B(0∈B(03PA,有E()m2eo)或e)m=E0则QB= QBNN U4 y 转Step6 step6判断A2是否为B()xy收到意向列表中最偏好的甲方匹配主体.考虑如下两种情形 1)当B)当前只有一个最偏好的甲方匹配主体A时,即若do=minl()yA∈QBn,则A 为B()收到意向列表中最偏好的甲方匹配主休 2)当B()y当前有多个等价最偏好或无法判断的甲方匹配主体时,设A为B()iy当前多个等价最 偏好的甲方匹配主体组成的集合,设A为B(1当前多个无法判断的甲方匹陀主体组成的集合 下面对集合A1m和A2中的每一个甲方匹配主体进行标记操作 设s()1(Ak)和s2(A)为第t次迭代中A在集合A1和A0m中的标记值,Ak∈A(0,则(01(Ak) 0,5()2(Ak)=0,0=12,3.对于任意的A∈A1考察(A,则有 478 系统工程理论与实践 第36卷 若8(A)为唯一最小标记值,q∈1,2时,则A为B)收到意向列表中最偏好的甲方匹配主体; 若s(4)为多个最小标记值之一且满足c(oy=min(0m,Ak∈4m},q∈1.2时,则A为 B(y收到意向列表中最偏好的甲方匹配主体 stcp7A反选,判断A是否接受B(wy,若A仅被B()w确定为当前收到意向列表中最偏好的甲 方匹配主体,则A接受B()y,转Step7若A被多个乙方匹配主体确定为当前收到意向列表中最偏好的 甲方匹配主体,此时设B(为满足上述条件的乙方匹配主休集合B(≌B,显然,Bt)∈B0),如果满足 iy=min{,B∈B0},转Step8 Step8判断(是否具有匹配对象若(-1)(Ba)=0,转Ste9,否则转Step10 Step9B(l接受A2.1(t1)(B()a)=A,V(=V(0)U{4},U7(=U()-{4},转Step11 step10判断B()y是否放弃原匹配对象而接受A设Ar为B(ai在第t-1次迭代时确定的匹吧 对象,即(-1(B()=A,A∈A若满足d2(1y<drti时,则B(放弃原匹配对象A而接受A, (B()2)=A2,V()={V()-{4}{4.)={)-{A}U{Ar},PA=P-{B)},转Step step1l判断算法是否终止令t=t+1,若U(≠0且∨A2∈U(,P4≠0.转Sep2;否则转Step 12 Stcp12结束程序 从上述IGS算法来看,IGS算法在已有的G-S算法基础上,加入了标记操作、反选等步骤,因此,增加 」计算量.关于计算量的比较,既可以通过算法的时间复杂度进行比较(即不妨设m<m,则GS算法的时 间复杂度为Om2),而IGS算法的时间复杂度为O(mAm),其中Am=m(n-1)…(m-m+1),也可通过 执行实际算法的时间进行比较 4.2IG-S算法体现的特点 通过将传统的GS算法和本文提出的IG-S算法进行比较,并结合具体的匹配例子,下面对IG-S算法 中新的操作和特点进行说明 1)向多个匹配主体提出意向.当甲方匹配主体当前具有多个等价最偏好的或无法判断关系的乙方匹配 主体时.在IG-S算法中允许甲方匹配主体向多个乙方匹配主体同时提出意向,从而使得甲方匹配主体给出 的偏好序尽可能都被考虑,同时也会由于提出匹配意向数量的增多,而使得甲方匹配主体匹配到较偏好匹配 对象的概率增大;而在GS算法中甲方匹配主体只能从多个等价最偏好的或无法判断关系的乙方匹配主体 中任意选择一个来提出匹配意向,这会导致甲方匹配主体给出的偏好序只能部分被考虑,同时也会由于所提 出匹配意向的随机性,而造成最终匹配方案缺乏稳定性 以现实生活中的求职匹配为例,当求职者具有多个无法判断优劣的企业时,考虑到希望尽快找到工作,并 尽可能避免由于轻率选择而造成的后悔,求职者往往同时分别向这些企业投递简历 2)标记操作.当乙方匹配主体收到的匹配意向中具有多个等价最煸好的或无法判断关系的甲方匹配主 体时,在IG-S算法中,进行标记操作,标记值越小,相应卬方匹配主体的优先性越强.在所提出的IG-S算法 中,将只提出一个匹配意向、提出多个等价最偏好的匹配意向、提出多个无法判断的匹配意向分别被标记为 1、2和3,主要是基于匹配的变动性和意愿的考虑: 对于只提出一个匹配意向的甲方匹配主体,认为提出的匹配意愿最为坚定,因此优先性最优; 对于提出多个等价最偏好的匹配意向的甲方匹配主体,认为提出的匹配意愿较为坚定,主要担心被多个 乙方主体接受时,需要任意选择一个乙方匹配主体作为匹配对象,而所选择的随机结果也许会使得匹配主体 错过最合适的匹配对象,因此优先性次优; 对于提出多个无法判断的匹配意向的甲方匹配主体,认为提出的匹配意愿最不坚定,主要在于被多个乙 方匹配主休接受时,由于偏好关系的不确定性,无法选择一乙方匹配主休作为匹配对象,因此优先性最差 而在G-S算法中,当乙方匹配主休面临同样的情况时,其只能从多个等价最偏好的或无法判斷关系的甲 方匹配主体中随机选择一个,因此不会进行标记操作.显然,G-S算法中乙方匹配主体的做法,忽略了甲方匹 咒主体所提的匹配意愿的坚定性,同时一旦选中提出多匹配意向的甲方匹配主体,很可能造成所选中的甲方 匹配主体.放弃该乙方匹配主体而选择其他乙方匹配主体的现象 以现实生活中的家政服务匹配为例,当雇主具有多个无法判别优劣的最偏好家政人员,其往往更倾向于 第2期 姜艳萍,等:基于偏好序约抗操作和抗自亏双边匹配方法 479 选择向该雇主提出单一匹配意向的家政人员,主要因为当雇主提出聘请意向后,该家政人员不有在犹豫和变 动;当不貝有只向该雇主一人提出匹配意向的家政人员时,雇主转而倾向于提出多个匹配意向且把该雇主作 为多个最优匹配意向之一的家改人员,虽然可能家政人员不会选择该雇主,但一旦选择,就不会有犹豫和变 动;如果上述情况均不存在,雇主只能选择提出多个匹配意向且可能把该雇主作为多个最优匹配意向之一的 家政人员,此时家政人员可能会选择该雇主,并且一定存在犹豫和变动,但是相较于雇佣不到家政人员,雇主 只能选择家政人员. 3)选择将自己排在较靠前位置的甲方匹配主体.考虑到当乙方匹配主体的匹配意向具有多个等价最偏 好的或无法判断关系的甲方匹配主体时,该乙方匹配主体更愿意选择将自己排在较靠前位置的甲方匹配主 体,因此,在IGS算法中,当乙方匹配主体收到的匹配意向中具有多个相同最小标记值的对方匹配主体时 会选择将白已排在较靠前位置的甲方四配主体 而在GS算法中,当乙方匹配主体的匹配意向具有多个等价最偏好的或无法判断关系的甲方匹配主体 时,由于其只能随机选择一个甲方匹配主休,而忽略了甲方匹配主体本身的偏好序,可能出现该乙方匹配主 体选择到对其偏好程度不高的甲方匹配主体,最终影响匹配结果旳稳定性 以现实生活中的大学自主招生录取匹配为例当学生收到多个最偏好或多个无法确定偏好的大学的自主 招生录取的意向时,由于根据自身的偏好序无法选择最偏好的大学,此时学生从发展的角度,更愿意选择更承 认自己实力的大学,即综合名次靠前的大学 4)反选.当某匹配主体在提出匹配意向后,被多个对方匹配主体确定为当前意向中最偏好的匹配主体 时,由亍该匹配主体只能与一个对方匹配主体进行匹配,此时该匹配主体进行反选.来选择当前的匹配对象 其中反选的依据是根据自身的偏好序以及在对方偏好序中的序值 而在G-S算法中,由于其只能选择一个匹配主体提出匹配意向,因此不会出现甲方匹配主体进行反选的 情形.而本文提出的IGS算法,允许甲方匹配主体提出多个匹配意向,并且进行反选,可以更有效地利用匹 配主体双方的偏好序信息 以现实生活中专利技术与企业的匹配为例,当拥有专利技术的科研机构向企业提出匹配意向后,如果被 多个企业选中为当前意向中最偏好的专利技术,此时由于匹配数量的限制,选择权转而落在该科研机构,即 科研机构进行反选. 4.3IG-S算法的相关理论证明 在本节中,主要从IG-S算法的退化性、抗操作性和抗自亏性等角度,以及所获匹配方案的稳定性和帕累 托有效性等角度,对IG-S算法的合理性进行证明. 下面首先给出IG-S算法的退化性定理、抗操作性定理和抗自亏性定理的描述及证明. 定理1(退化性)当任意匹配主体针对对方匹配主体均给出强偏好序时,改进的GS算法与经典GS 算法等价 从IG-S算法的流程可以很容易证明定理1的结论,这里不再赘述. 定理2抗操作性)IGS算法具有抗操作性 证明不失一般性,设甲方匹配主体A故意提供错误偏好序信息.μ和μ分别表示A1提供正确偏好 和错误偏好序信息时,运用IGS算法获得的匹配方案.采用反证法,即彐B,Bk∈B,满足p(A4)=B, 1(A)=Bk且ek<∈ 不妨没p(Aa)=Bk.由于eik<ei,则根据IG-S算法,A先向Bk提出匹配意向,并且被Bk拒绝,即 k<d1k.因(A)=Bk,所以在匹配方案中A具有更好的匹配对象B2,故没有向Bk提出匹配意向, 即如果设p(A4)=B,则满足eq<cqk 同理设/(A2)=Ba,则有d<d,设1(A)=B3y则有emy<eai; 设g和γ分别为A提供错误偏好时,确定A与弓。匹配的迭代次数和确定Aa与乃,匹配的迭代次 数H于d<dq,只有A与B匹配之后,才可以确定A与B。匹配,则有p<g; 进一步地,设p(A2)=By,则有d29<dy;设(A2)=B,则有e29<eay 设h为A提供错误偏好时,确定A2与B的匹配迭代次数.由于d3y<dy,只有A2与Bg匹配之 后,才可以确定A与B匹配,则有1<p<g 以此类推,当A提供错误偏好序时,总可以找到A,其在第一次迭代时就与B,∈B匹配,即p(A) 480 系统工程理论与实践 第36卷 B,并且有1<…<p<g 若设μ(Aa)=B,μ(Aa)=Bn,则有eωh<εα且dal<dr;若设λ为A1提供错误偏好时.确定Aa 与Bn匹配的迭代次数,则有:A<1<…<p<9;显然与入≥1矛盾 定理3(抗自亏性)IG-S算法具有抗自亏性 证明不失一般性,设甲方匹配主体A2故意给出自亏属性信息,μ和分别表示甲方匹配主体A;提 供真实和自亏属性信息时,运用IGS算法获得匹配方案.采用反证法,即设vB;,Bk∈B,满足1(A)=B 1(A)=Bk且ek<Ci 由于A:提供的偏好序是真实的,因此,A总是先向Bk提出匹配意向,然后再向B;提出匹配意向.但 由于μ(A)=B,说明A1被Bk拒绝另一方面,当A1给出自亏属性信息时,A1在每个乙方匹配主体的偏 好序值均不优于Aa给出真实属性信息时的偏好序值,即说眀若A给岀自亏属性信息,A;仍然被Bk拒绝, 这与p(A)=Bk矛盾.综上,IGS算法具有抗自亏性得证 然后,给出IGS算法所获匹配方案的稳定性和帕累托有效性定理的描述及证明 定理4IG-S算法获得的匹配方案为稳定匹配方案 证明设为所获得的匹配不妨设A1,A∈A.VB,Bk∈B,有p(A1)=B1,A(4)=Bk.采用反证 法,现假设为不稳定匹配则存在如下情形:ek<e且dik<dk 根据IG-S算法的思想,A;总是先向更偏好的乙方匹配主体提出匹配意向,即若eik<e时,则A;先 对B提出匹配意向.而μ(Bk)≠A说明Bk拒绝了A不失一般性,不妨设Bk在第t次迭代时拒绝Az 而选择了A1∈A,则dk≥dk; 但是由于μ(Bk)=A≠A,说明Bk一定拒绝了Aq而选择了更偏好的A,即dzk≥dk≥dk.显然 与已知条件d<dk矛盾,故定理4成立 定理5IG-S算法获得的阢配方案为帕累托有效匹配方案 证明设为所获得匹配方案采用反证法,现假设μ不是帕累托有效匹配方案,则一定存在某一匹配 方案,即彐B;∈B,A,A∈A,H(B;)=A1,p(B)=A,满足d<d1 由于d<d,在应用IG-S算法时,B;先向甲方匹配主体A提出匹配意向,而A拒绝B,否贝 (B;)-A 另一方面,只有出现更偏好的乙方匹配主体时,A才会拒绝B,不妨设(A)-Bn,Ba∈B,满足 qa<c说明A认为匹配方案μ优于,这与p′咱累托占优矛盾 此外:还可证明IGS算法满足如下定理 定理6在IS算法获得的匹配方案中,对于任意乙方匹配主体的偏好序中,如果有两个具有强偏好的 甲方匹配主体向其提出匹配意向,则与排在其偏好序前面的甲方匹配主体匹配的概率大于或等于与排在后面 的甲方匹配主体匹配的概率 证明不失一般性假设B认为A优于A,即d1<dP(B1)和P(B)分别表示A和A被B 拒绝的概率,B;∈B,A2,A1∈A A被乃;拒绝包含两种情形:一种是B拒绝A,此时由于而<dy,则A被B;拒绝;另一种是乃 与A;匹配,此时由于d<d则A因竞争力不强而被B;拒绝 进一步地,有P(B)=P(B)+ P(B)(1-P(B),这里表A在B;的偏好序中,优 Ak∈AcA 于A2且向B提出意向的甲方匹配主体集合,B(B1)表示Ak被B;拒绝的概率.由于B(B3)>0且 1-P2(B1)>0,则P(B,)≤P(B)进而1-P(B)≥1-P(B),结论得证 5算例 Ⅹ市某专利技术服务中介公司,主要负责科研单位wb服务专利技术与TT企业的匹配服务,现该中介 公司收到6个科研单位的veb服务专利技术的转让请求和5个IT企业的需求请求,即甲方匹配主体集合 A={A1,A2,A3,A41A5,A6},乙方匹配主休集合B={B1,B2,B3,B4,B5}.该中介公司分别将甲方匹配主 体和乙方匹配主体的相关信息发布给对方.之后,甲方匹配主体和乙方匹配主体分别针对对方给出相应的偏 好序,如表1所示.其中甲方匹配主体关于乙方匹配主体给出的偏好序主要考虑了专利技术的转让收益、企 业的技术水平和专利技术的转化速度等指标;乙方匹配主体关于甲方匹配主体给出的偏好序主要考虑了专利 第2期 姜艳萍,等:基于偏好序约抗操作和抗自亏双边匹配方法 481 技术的潜在价值、专利技术的复杂程度、专利技术主题领域的市场前景度和引进专利技术等指标 表1甲方匹配主体和乙方匹配主体给出的偏好序 偏好序 偏好序 A1B5×B3×B2B1>B4B1A4xA5?43?A2xA1xA A2B4?B2>B1~B3~B5B242>A3?A5~A1xA4>A A3B3>B5?B4>B1~B2B31?43>A1~12>4>4 A4B4~B5×B3~B2×B1B441×A2>A4~A3?A6>A5 A 5 B1yBA B2>B3? B5 Bs A4 >A? A3? A5 A1xA6 A6B3?B2×乃1>B5xB4 表2IG-S算法的迭代过程 迭代次数B(y或Bt 当前匹配结果1()Ur( t=141:B5;A2:{B2,B4}B1:A5;B2:{42,A6} B1台45;B2+A2A1,A6 A3:B3;A4:{B41,B}B3:{A3,Ac};B4:{A2,A4}B3A3;B5←A4 A5:B1;A6:{B2,B3}Bs:{A1,A4}; A1:B3;A6:B B1:A6;B3:A B1→45;B2A2A1,A6 B3台A3;B5←A4 t=3A1:B2;A6:B B2:A1;B5;A6 B1445;B2A241,A6 A3: B 4 t=4 41:B1;A6:B B1:A1;B4:A6 B14→A5;B2←A2A1,A6 43;B5←4 t=5 A1: B B BBBB →4s;B2442A6 A3;B4←A ←→A4 表3A5提供错误偏好时的迭代过程 达代次数B(t3或By1B2,B4} QB 前匹配结果 B2:{A2,45,A6};B24A2;B3A3A1,4s A3:B3;A4:{B4,B5} B3:{A3,A6 B4台A5;B5←A4 A5:{B2.B4};A6:{B2,B3}B4:{A2,A,A5}; B5:{A1 t=2 A1: B3: A6: B B1: A6: B3: A1 B1 t A6: B2 ++A2 A1 A3:B4←A B54A4 根据表1中双边匹配主体提供的偏好序,下面采用IG-S算法,求得最优的双边匹配方案,具体的迭代过 程如表2所示 从表2可以看出,当匹配主体双方提供真实的偏好序时,最优的双边匹配方案为B1+A5、B2台 A2、B3+A3、B4+A和B5+A 为了说明IG-S算法的抗操作性,不失一般性,假设甲方匹配主体As提供错误偏好序为:B B1>B3?B5,则此时用IGS算法,具体的迭代过程如表3所示 从表3可以看出,当甲方匹配主体A5提供错误偏好序时,最优的双边匹配方案为B1←A6、B2 2、B3→A3、B4+A5和B5分A4 对于甲方匹配主体A5而言,当提供真实和错误的偏好序时,所获得的匹配对象分别为乙方匹配主体B1 和B4.按照表1中甲方匹配主休A提供的真实偏好序,有:B1>B4,即e5=1<e54=2;可见,甲方匹 配主体A5更偏好于提供真实偏好时的匹配对象B1,此时甲方匹配主体A5没有提供虚假偏好序的动机,可 见,兀配方案具有抗操作性 进一步地,为了说明IG-S算法的抗自亏性,不失一般性,假设甲方主体提供自亏属性信息时,乙方匹配 主体提供的偏好序为 B1:A4>A5?43xA1>A2>A6;B2:A3?A5~A1>A4>A6×A B:A6?A3>41xA4>A2>A5;B4:A1>A4~A3?A6>A2>A B5: A4? A3?A5?A2? A1>ac 482 系统工程理论与实践 第36卷 此时采用IGS算法,具体的迭代过程如表4所示 表4A2提供自亏信息时的迭代过程 迭代次数B()y或Bt 当前匹配结果p()U t=1A1:B5;A2:{B2,B4}B1:As;B2:{A2,A6} B1台A5;B2←A6A1,A 13:B3;A4:[B4,Bs}B3:{A3,A6};B4:{2,A4}B3A3;Bs4A4 1;A6:{B2,B3}乃5:{A1,A4}; t 41:B B1:A2;B3:{A1,A2} B1+A5;B2+A6A1,A2 4:{B1,B3,B5} 乃34A3;乃5←A 11:B B B1+45;B2+A641,A2 43;B5←A B1: A B145;B2A6A1,A2 B4A3;B5←A4 t=5A1:B4 BA: A B 43;B4←A B5 <A 从表4可以看出,当甲方匹配主体A2提供自亏属性信息时,最优的双边匹配方案为B1→A5、B2 b6、B3台A3、B4纱A1和B5←A4.对于A2而言,分别提供真实和自亏属性信息时,所获得的匹配对象 分别为B2和A2(即没有匹配对象).由表1中A2的偏好序可知,B2为A2最偏好的四配对象,显然,A2更 愿意提供真实的信息 此外.本文还对IG-S算法与已有随机算法进行了对比首先,将表1中的偏好关系“?”以等概率分别取 “”、“〈”和“”3种偏好关系,显然,偏好关系“?”的不确定性造成了偏好关系的穷举,即若所有匹配主 体的偏好关系“?的总数目为L时,则随机算法需要根据3个匹配主体双方提出的偏好序,确定匹配方案 在本例中,L=11,故随机算法需要根据31个匹配主休双方提出的偏好序,计算相应的匹配方案.即采用文 献[17中提出的随机算法,求得的最优匹配方案,如表5所示 表5随机算法求得的最优匹配方案 序号 最优匹配方案 1B1→As;B2台A1;B3分A6;B4台A2;B5←A4 2B1A5;B24A1;B34A3;B4442;B5444 3B1A5;B台A2;B3台A6;B44A1;B5A4 4B1→A5;B2 5B1→As;B台A2;B3台A3;B4分A1;阝5台A 从表2和表5可以看出,采用本文提出的IG-S算法求得的匹配方案,实际上是采用随机算法求得的匹 配方案的一个子集,也就是说,采用随机算法会获得更多数量的匹配方案.这主要是于偏好关系“?”的不 确定性所致.然而,在实际的双边匹配问题中,无论决策者面对多少匹配方案,都必须选择一个匹配方案,并 推荐给匹配主休双方.显然,随机算法所求得的多个匹配方案,给决策者进行匹配造成了难度.同时,随机算 法依赖于“?”的不确定性进行偏好关系的穷举,与本文所提的IG-S算法相比,具有明显的算法运行时间长 和运行效率低等不足之处.此外,随机算法常常难以满足抗操作性[16.可见,本文所提出的IGS算法弥补 了随机算法的不足 6结束语 本文针对基于偏好序的双边匹配问题,给出稳定和帕累托有效匹配方案的定义,以及匹配方法的抗操作 性和抗自亏性定义.通过借盗经典G-S算法的思想,并加入标记操作、反选等步骤,设计了IG-S算法,分析 并证明了IG-S算法的特点利合理性.与已有研究成果相比,所提出的IG-S算法,重点考虑了匹配主休双方 给出未知偏好序的情形,进一步扩展了G-S算法的应用范围.同时,所提出的IG-S算法,还具备了抗操作性 和抗自亏性,弥补了已有研究方法中大多假设匹配主体双方一定给出真实有效信息的不足,更贴近于现实决 策需要.值得指出的是,本文所提出的IG-S算法,还为解决其他双边匹配问题,如:考虑不完全偏好序的双

...展开详情

论文研究