论文研究-可调整个体优先级的双边匹配算法.pdf

所需积分/C币:10 2019-09-07 15:39:36 744KB .PDF
收藏 收藏
举报

针对传统双边匹配算法单边占优、缺乏最低保障以及无法精细调控个体优先级等问题,提出了可通用于一对一、一对多、多对多双边匹配的WYS算法。WYS算法通过外生给定优先级,使得每个参与主体都有机会遍历自身偏好序中全部对象,从而显著提高匹配结果中最差群体的效用以及全体总效用,并能够对个体效用进行精确调控。随后按照诺奖得主Roth提出的“经济工程学”范式设计实验对WYS算法的性质进行了深入探讨,大量随机实验表明WYS算法匹配结果稳定,能够给予参与主体某种程度的最低保障,且不存在单边占优问题。WYS算法对于维持市场厚度、兼顾效率与公平有重要意义,拓宽了匹配理论的应用范围。
计算机工程与应用 度很高,同时每个毕业生对于医院的偏好相似度也很序中的医院签约不考虑其余医院,则SP-{H3,H,H} 高。但是婚姻匹配等众多双边匹配问题屮,参与主用E1,P(E2E1P(E3)表示在E1的偏好序中E2排在 体的偏好差异性很大,稳定匹配集合的基数也会随之增F3之前 大,算法的单边占优以及缺乏最低保障等问题就会 匹配容量C:E能够匹配的对手实体数量。例 凸显,使得匹配结果较差的参与者积极性下降,降低市。如某医院E1欲招聘个学生,则EC=4。在就业市 场厚度,进而导致市场设计失败。实际上即使在单边场中,学生类型实体的容量恒为,医院类型实体的容量 占优问题并不严重的住院长生实习市场,采川医由每个医院根据择聘计划白定。 院优先的匹配算法也曾招致大量学生表达不满甚至退 已匹配列表M:目前暂时与E匹配的对手实 出 匹配系统因此如何提高效用较差者的满意度体列表。在算法运行过程中每个实体E的EM都会 成为决定市场设计成败的关链问题。李铭洋、樊治平不断迭代更新,算法停止时EM中的实体即为E的最 等关注到这题并提出了解决方案将双方主体匹配终匹配对象。当EM中的实体数量等于EC时,称 序值之和最小作为目标构建了多目标优化模型,使得结 已匹配满”。 果不再偏向于某《方解决了单边占优问题。但该厅 ()最差实体( ):EM 法并不能给予效用最差者以最低保障,仍然可能有个别中最不被F偏好的实体。算法运行过程中EWMF会 参与主体效用过差因此在维护市场厚度方面尚存在改随着EM的变化而不断更新 进空间,另外其方案也只能调整参与匹配某一方整体的 算法维护一个无序集合L和一个有序队列 优先级,而无法针对某个參与个休做出调整。 1。初始时将ES中所有实体都加入L,将T置空,然 为了更好地鮮决单边占优问题、最低保障问题以后启动第轮外层循环,循环过程中会不断调用 及提供灵活调控个休优先级的机制,本文提出了 函数,每次调川西数都意味着某个实体向另一个 算法。 实体发出了匹配申请,在执行过程中有可能解除 某些暂时的匹配,被解除匹配的实体会被放入T中,下 算法 一轮循环优先让T中的实体发出申请。算法框架参考 个典型的双边匹配问题中包含两类主体集合,以图,算法具体细节参考伪代码及注释。 医学毕业生就业市场上医院与学生的匹配为例,有学生 集合S一{S1,S2,…,S}和医院集合H-{H,H2,…,Hn}, ∠法开始7 每个学生S;试图寻找一个医院签约工作,每个医院H 将全部实体放入 试图招聘q个学生,每个学生S对其可接受的医院, .中,将T置空 以及每个医院对其可接受的学生,都有一个完备的、可 传递的、严格的偏好序。匹配结果为Sx的个子集 ∠和T皆为空、是/算法结束此时各 个实体的匹配列表 M中的内容即为 M,M中的每个元素是一个学生和一个医院的匹配 最终匹陀结果 对,在M屮每个学生只出现不超过次,每个医院出现 不超过q次。匹配结果稳定意味着M中不存在阻碍 外层循环 内层循环}将中的第个实体 对( ),一个好的双边匹配算法总能找出稳 移出T,并让E1按照偏 定的匹配结果。 为空 否好程度从大到小的顺序 依次给自己偏好序中的 算法将学生和医院都视为实体(),全体 是 所有实体发送匹配申请 学生和医院构成的集合称为实体全集ES。对于仟 (即调用函数) 是 实休E来说,与E不同类型的实体称之为对手实体。 为空 例如对一个医院实体来说,所有的学生实体是对手实 体。每个实体E拥有以下属性(实体的属性可以使用 将L中优先级最高的实体E2移 F属性名”的方式来表示): 出L,并让E2按照偏好程度从 大到小的顺序依次绐白己偏好 ()优先级R:外生给定ES一个全序,用正整数表 序中的所有实体发送匹配申请 示,ER为实体E对应的正整数,ER越大意味着E (即调用函数) 的优先级越高。 图 算法框架 ()偏好序P:每个实体E都有·个描述自己对于 算法伪代码 对手实体偏好程度的严格序列,在偏好序中越靠前则意 味着越希望与对方匹配。例如某学生S1最心仪的医院 是H3,其次是H5,再次是H1,该学生只考虑与该偏好 程与应用 王彦博,于瀚辰,沈体雁:可调整个体优先级的双边匹配算法 算法注释 只要L和T任何一个非空,就不断进行外层 循环。 只要T非空,就不断进行内层循环,每次循环都 四数注释 从T中取出一个实体处理 若E1不在E2P中,或E2不在E1.P中,则 将T中排第一位的实体移出T,并将该实体作E1和E2不可能匹配,直接绪束函数。 为变量E1。 若E1对丁E2来说还不如E2匹配的最差 E1按照偏好程度从大到小的顺序依次向其者,或E2对于E1来说还不如E1已匹配的最差者,则 偏好序中的实体发出申请,即调用 函数,函1和E不可能匹配,函数直接结束。 数的只体定义见下文伪代码。 :创建·个空的、有序的临时队列变量,命名为 判断L是否为空,若不为空就从L中取出一个 tmp list。 实体处理。 若F1已匹配满,则解除E1和FWMF的奢时 将L中R值最大的实体移出L,并将该实体作匹配状态,并进行其他相关处理 为变量F2。 解除E和E1.WME的暂时匹配状态。 :E2按照偏好程度从大到小的顺序依次向 若实体w1曾发出过至少一次中请且cl目 其偏好序屮的实体发出申请 前不在T甲,则将1放入临时队列 imp_ list"。 :算法结束,此时每个实体E的匹配列表EM 若E2已匹配满,则解除E2和E2.WME的暂 中的结果即为最终匹配结果。 时匹配状态,并进行其他相关处理 (E1,E2)函数定义伪代码 :解除E2和E2WME的暂时匹配状态。 若实体2曾发出过至少一次申请且2H 前不在T中,则将t2放入临时队列加 mp_ list中 :按照R值从大到小的顺序对加 np. list中的实体 进行排序 将 tmp_ list中的实体依序插入T中,插入每 一个实体时若T非空,就将该实体插到T中现存的最 后一个实体之前(这是为了保证最新被踢掉的实体在 T中排在最前列,从而下一轮循环中可以率先尝试发出 中请) :将E1和E2互相加入对方的暂时匹配列表 中,E和E2暂时成为可相匹配的实体 实验结果及讨论 进行与第章屮相同的随机实验次,分别用医院 优先的算法、学生优先的算法和算法对 个学生和个医院在阿机偏好序下进行匹配。其 计算机工程与应用 …学生占优的算法 学生占优的算法 医院占优的算法 医院占优的算法 算法 算法 X:偏好位次 X:偏好位次 ()医院匹配结果 ()学生匹配结果 图 次随机实验平均的医院与学生偏好位序满足累积曲线 屮八算法需要先没定优先级R,优先级高的实体会分对象水远没有机会尝试匹配,理论上存在改善其效用 优先发出申请并在最终匹巸鈷果中札对占优。实验中的空间。算法为参与配的双方主体设定一个 参考对手实体的偏好序来确定优凭级R,将学生和医外生优先级,让全部主体按照优先级依次发出申请,每 院按照被偏好程度从大到小排序,占据医院偏好序中第个主体都有机会遍历自身偏好序中的全部对象,只要设 名最多的学生为学生队列的第一位,若两学生占据医置合理的优先级,就可使得匹配双方被同等对待 院偏好序中第一名数量相同则根据占据医院偏好序中 ()算法提高了等传统算法中效用最差 第二名的数量排位,以此类推,对全体学生进行优先级排者的满意度。如表所示,次随机实验中算法 序,医院排序采用同样方法操作。学生队列排序结果为的个参与主体没有任何个匹配其偏好序位 So,医院队列排序结果为{Hn1,HR2 之后的对象,而算法匹配到偏好序位之后的主体 Hkoo,设定优先级结果为SR>H1R>Sk2R>数量为(学生优先)和(医院优先),算法在偏 Hk2R>…>HE10R理论上优先级可以随意设置,优好序位次 范围内匹配成功的主 先级越高的实体最终越占优,不同的优先级设定可能会体数量也都明显少于算法,即效用过差者的数目有 产生不同的匹配结果,上述设定方式符合最受欢迎者显著减少。囹展示了次实验中个主体匹配结 优先”的一般常理。通过实验可知算法解决了第果的偏好位序分布情况,相对于算法,算法的 章提出的传统算法存在的问题 ()算法非单边占优。图()展示了次随 次实验中个主体匹配结果的偏好位序统计 机实验医院的平均匹配结果:算法屮优先发出申请 偏好位序范围 一方的效用明显好于另一方,而算法的结果对于 学生优先的算法匹 医院和学生没有明显倾向性,多数参与主休都匹配到了 配总数量 其偏好序中前位的对象,不会使某一方达成最差的医院优先的算法匹 稳定匹配。、 等传统算法屮的劣势 配总数量 方由于只能被动选拌接受或拒绝,其自身偏好序中的部 算法匹配总数量 异常值点透 明度为 纽 算法 算法 算法 算法 算法 算法 (学生优先)(医院优先) (学生优先)(医院优先) )显示异常值 )不显示异常值 图 次实验中个主体匹配结果的偏好位序分布箱线图 王彦博,于瀚辰,沈体雁:可调整个体优先级的双边匹配算法 过大异常值数目明显较少且异常值的整体位序值不高,贷与小微企业匹配、教育招生匹配、人岗匹配等问题,为 箱线图上边缘和上四分位较低,下四分位和屮位较高,相领域基于双边匹配理论的市场设计实践提供了更 整体来看算法上下四分位之间的分布较为集中。强的理论基础。算法对于传统算法中效用最差的 算法相对于算法来说牺牲了很少一部分效用群体满意度有显著提高,对于提高主体参与意愿,维持 极高者的利益,换取了效用最差者结果的显著提升。 市场厚度有重要意义。同时算法通过外生指定不 算法提升了参与者的总体效用图为同优先级,能够倾向性地照顾不同主体,产生多种不同 次实验平均之后的学生和医院整体匹配结果偏好位的稳定匹配,而如传统算法只能选择照顾参与双方中 次累积曲线,其中 算法曲线最,两种算法的的某一方,为匹配机构的宏观调控和精细干预提供了可 曲线几乎重合,较算法更为平缓,意味着算操作空间 算法可通过设定匹配容量而用于一对 法的整体效川比算法更高。算法平均有 、一对多和多对多双边匹配问题,具有相当的通用性。 个主体匹配到了其偏好序中前位的对象,有个 主体匹配到了其偏好序中前位的对象,优于算法参考文献 的匹配结果。实验过程中生成偏好序的方式为 魏立佳从微观理论到社会实践—一市场设计的最新进展 之间随机打分,打分高者在偏好序中推名靠前,岩以匹 综述世界经济文汇, 配对象的打分值作为主体获得的效用,则、算法、学 生优先的算法和医院优先的算法给出的每个 参与主体的平均效用分别为 和 算法的总体效川更高。 学生占优的算法 医院占优的算法 算法 X:偏好位次 图 次随机实验平均的学生和医院整体 偏好位次满足累积曲线 )目前尚未从理论上证明算法的稳定性,但大量 随机偏好序的一对一、一对多实验发现随着优先级设定 不同,算法总能产生不同于经典算法的多种 稳定匹配结果,即算法产生的结果不存在阻碍对。 在进行了多轮次一组的实验之后,发现上述() ()结论在每一轮实验中都成立,另针对一对多、多对多 匹配进行了实验,上述()()结论仍成立,说明算法具 有相当的稳健性。 结束语 本文针对传统双边匹配算法存在的问题提出了全 新的算法,并接照的经济工程学范式没计实 验对算法的性质进行了深入探讨。 算法解 决了 等经典双边匹配算法的单边占 优问题,扩展了双边匹配算法的适用范围,尤其有助于 应对主体偏好·致性不强的场景,如婚姻匹配、银行信 (下转贝)

...展开详情
试读 6P 论文研究-可调整个体优先级的双边匹配算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_38743968 欢迎大家使用并留下宝贵意见
2019-09-07
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分,得勋章
最新推荐
论文研究-可调整个体优先级的双边匹配算法.pdf 10积分/C币 立即下载
1/6
论文研究-可调整个体优先级的双边匹配算法.pdf第1页
论文研究-可调整个体优先级的双边匹配算法.pdf第2页

试读结束, 可继续阅读

10积分/C币 立即下载 >