稳定匹配算法的研究和演变.pdfVIP

第 9 卷  第10 期  2013 年 10 月 稳定匹配算法的研究和演变 陈　宁　李梦玲 关键词 ：稳定匹配 新加坡南洋理工大学 匹配市场(matching markets) 称为 “稳定”(stability) 。他们还 议，然后直到算法结束的时候才 中通常涉及两个不相交的个体的 通过一个简单的迭代算法—— 做出接受的决定。与此同时，那 集，里面每个个体对于另一个集 递延接受算法(deferr ed accep - 些被拒绝的个体做出新的提议， 里面的个体有偏好。我们可以根 tance algorithm) ，证明了稳定匹 这可能导致新的拒绝，直到没有 据这些偏好，对两个集里面的个 配的存在。文章中提到的经典 被拒绝了的个体想要进一步做出 体建立互相的匹配。在实际生活 双边匹配模型涉及两个不相交 提议。此时所有被保留的提议都 中有很多常见的匹配市场，比如： 集的个体 ：男人和女人。其中 最终被接受，由此产生了一个稳 学生和学校、员工和公司。匹配 每个人对于来自另一组的一个 定的匹配。 市场可以有多种形式：一对一（比 子集进行严格地优先排序。每 如一夫一妻制下的男女婚姻 ）， 个个体可以和另一边的至多一 稳定匹配的应用 多对一 （比如大学和学生匹配） 个个体匹配，因此该模型也被 或者多对多 （比如课程和学生匹 称为 “严格偏好的一对一匹配”。 自从盖尔和夏普利提出稳定 配）。在某些匹配市场里可能只 匹配理论后，该理论被广泛且富有 有一边的市场有偏好，比如住房 定义和算法 成效地应用于双边的环境中。例如， 分配和肾脏交换。 一个稳定的匹配是由互相可 大学的录取、婚姻的匹配、住院大 接受的个体的对(p air s) 组成的 夫就职。经济学家依据稳定匹配理 稳定匹配的起源 集合，并且满足以下条件 ：没有 论改进了现有的机制[2, 3,12] 。在学 两个个体可以通过相互匹配来改 校——学生匹配问题中，阿 卜 善他们现有的匹配。递延接受算 杜卡迪罗格鲁(Abdulkadiroglu) 模型 法通过以下步骤来找到一个稳定 和森梅兹(Sönmez) [4] 指出现有 戴维·盖尔(David Gale) 和劳 的匹配 ：市场一方的个体按照自 的许多机制存在很多缺陷 ：容 埃德 ·夏普利(Lloyd Shapley) 在 身偏好的先后次序对另一方的个 易被操控、匹配结果既不平等 [1] 体做出提议，那些获得比他们能 也不具有效率。他们提出了新 1962 年提出了稳定匹配理论 。 该理论首先发表在 《美国数学 接受的数目更多提议的个体，会 的匹配机制来改善现有的学校 月刊》(American M athematical 拒绝那些他们最不喜欢的个体的 录取机制。在波士顿、纽约和 Monthly ) 上。他们最先提出和介 提议，但他们不立即接受他们不 许多其它地区，这个机制已经 绍了双边匹配模型，并且提供了 拒绝的个体。相反，他们在不做 被采用而且很大程度地改善了 一个合适的解决方案，该概念被 出任何承诺的情况下保留这些提 旧机制。在美国和欧洲的 “肾 15 专题 第 9 卷  第 10 期  2013 年 10 月 [5~7] 脏交换项目”中 ，稳定匹配 那个包含他更喜欢的女人的集合； 稳定的匹配。由于在打破偏好里 理论的引入具有重大的社会影 如果他