匹配问题PPT课件

1 匹配博弈 2012年诺贝尔经济学奖介绍 2 2012年10月15日瑞典皇家科学院宣布 将2012年诺贝尔经济学奖授予美国经济学家阿尔文 罗思和劳埃德 沙普利 以表彰他们在 稳定匹配理论和市场设计实践 上所作的贡献 3 罗伊德 沙普利教授生于1923年 现为加州大学洛杉矶分校荣誉教授 1945年在普林斯顿大学取得博士学位 他和1994年获奖的纳什都是塔克的学生 纳什是非合作博弈的奠基者 而沙普利则是合作博弈的奠基者 合作博弈论里面的沙普利值就是以他的名字命名的 值得一提的是沙普利教授在二战期间加入过美国空军 前往中国成都支援中国抗战 埃尔文 罗斯教授生于1951年 目前就职于哈佛大学商学院 罗斯是斯坦福大学的运筹学博士 罗斯教授实际上已经离开哈佛 加盟了斯坦福大学经济学系 罗斯教授的研究领域极其广泛 包括博弈论 实验经济学和市场设计 目前的主要兴趣是市场设计 他最为著名的设计是 全国住院医生配对程序 斯坦福大学经济学系目前聚集了全世界最顶级的市场设计专家 4 颁奖声明说 尽管两位获奖者独立地进行了各自的研究 但沙普利的基本理论与罗思的实证实验相结合 产生了一个研究和改善众多市场功能的领域 今年的经济学奖实际上授予的是一个杰出的经济工程范例 随后 诺贝尔经济学奖评选委员会主席佩尔 克鲁塞尔和其他评委介绍了获奖者的研究成果 他们表示 两位获奖者在不同经济主体如何匹配以及匹配形式的各种可能性方面进行了深入研究 诺贝尔经济学奖评选委员会在声明中说 沙普利采用了所谓的合作博弈理论并比较了不同的匹配方法 其研究重点是如何使双方不愿打破当前的匹配状态 以保持匹配的稳定性 沙普利分析出一种被称为 盖尔 沙普利法则 的特定方法 以保证总能获得稳定的匹配 这一机制还可对相关各方试图操纵匹配过程加以限制 他的研究还揭示了如何通过机制设计对市场的某方产生系统性收益 5 罗思的贡献在于 他发现沙普利的理论能够阐明一些重要市场是如何在实践中运作的 通过一系列研究 他发现 稳定 是理解特定市场机制成功的关键因素 之后 他将这些研究成果运用于实验 并帮助重新设计了现有的诸多匹配机制 在沙普利理论的基础上 罗思还加入了对道德约束或其他特定条件的考量 据了解 在诸如器官捐献者与接受移植病人之间如何匹配器官资源 在学生与大学之间如何配置教育资源 或者在网络搜索引擎提供的广告位与广告商之间如何进行有效匹配 如何高效完成匹配等广泛领域 这些理论和实践都有应用 6 博弈论 从理论到实践瑞典皇家科学院表示 今年的诺贝尔经济学奖得主关注经济学的一个中心问题 如何尽可能适当地匹配不同市场主体 比如 学生必须与学校相匹配 人体器官的捐献者必须与需要移植器官的接受者相匹配 这样的匹配如何尽可能有效地完成 什么样的方法对什么样的人群有益 今年的诺贝尔经济学奖授予的这两位学者 分别从稳定匹配的抽象理论和市场制度的实际设计两个角度 对上述问题作出了自己的回答 沙普利使用合作博弈方法来研究和对比不同的匹配方法 其关键在于保证配对是稳定的 所谓稳定 指的是不存在这样两个市场主体 它们都更中意于他人 胜过它们当前的另一半匹配对象 沙普利和他的同事找到了所谓的GS算法 Gale Shapley算法 这种方法能确保匹配稳定 7 博弈与非合作博弈 合作 或者联盟 博弈从宏观的角度研究博弈 关注可以有约束力的承诺来得到的可行结果 合作博弈和非合作博弈的主要区别在于 当人们的行为相互作用时 参与人之间能否达到一个具有约束力的合作协议 与非合作博弈不同的是 合作博弈的分析单位是联盟 考虑的是参与人之间如何组建不同的联盟以实现协议的目标 以核为例 核只是为稳定性提供了一个检验标准 而没有描述联盟的具体形成过程 而非合作博弈恰恰是研究这个问题的 简单的说 存在约束力的合作协议的博弈就是合作博弈 反之 就是非合作博弈 8 最典型的例子就是寡头市场上的竞争与合作 如果两个寡头进行Cournot竞争 那么 他们都是最大化自己的利润为目标 而不管对方的利润如何怎样 因此是非合作博弈 但是 如果两寡头签订协议 形成垄断 共同最大化垄断利润 然后将合作所带来的总利润在两寡头之间进行分配 这就属于合作博弈的研究范畴 例如 石油输出国组织 OPEC 就是这样一个限产联盟 合作博弈和非合作博弈的侧重点不同 合作博弈强调集体理性 强调公平和效率 而非合作博弈强调的是个体理性 强调个体决策最优 其结果可能是无效率的 也可能是有效率的 即符合集体理性的 9 静态匹配博弈 匹配博弈是研究和应用都非常广泛的一类博弈 最早开始于GaleandShapley 1962 的一篇简短而有重要启发意义的关于大学招生和婚姻匹配问题的研究 并由Roth 1984 进行了重要发展 第一设计并分析中央匹配机制 第二 研究不存在中央匹配机制时 双方参与人通过搜寻达成匹配的过程 从Roth在对美国的医院和医科学校实习生之间的匹配程序进行研究之后 发现实际中使用的匹配原则恰好符合博弈论的预测结果 这一精巧的结果激励着众多博弈论学者对于劳动力市场的雇主和工人之间的匹配问题 婚姻匹配问题 拍卖问题等进行了一系列重要的研究 由于匹配问题最初是由婚姻问题开始研究的 因此 关于匹配问题的文献通常使用婚姻问题的术语 10 匹配问题经典实验 男女匹配 1962年 DavidGale 已经去世 和LloydShapley提出了下面的问题 给定若干男生和若干女生 未必数量相同 他们每个人都对所有的异性有一个稳定的偏好排序 是否存在一种男女匹配组合构成一种稳定的组合关系 现实世界中的很多交易并不满足瓦尔拉斯交换模型的假设 双边匹配市场就是就是一种特例 在这类市场中 至少有两个重要的假设 第一 参与人双方从博弈一开始就分别属于两个互不相交的集合 且位置不能互换 例如婚姻匹配市场上 男士和女士的集合分别为S和T i S j T S T 11 第二 只有经过双方一致同意后才能形成匹配 即一旦i和j匹配 就一定有j和i匹配 例如婚姻问题中的两大集合是未婚男士和女士的集合 两人一旦结婚 就相互匹配 劳动力市场也是一样 当然 在这里不考虑工人也可以自己开办企业成为雇主的可能 即总是假设工人和雇主这两大集合不存在交集 在一对一匹配问题中 最典型的就是婚姻匹配问题 很多匹配市场上 促进交易的中介机构广泛存在 例如就业指导中心 婚姻介绍所 房屋中介公司等等 因此 我们考虑由婚姻介绍所根据参与人偏好来进行匹配 现在我们考虑这样的婚姻模型 因此匹配问题是一个非常现实非常重要的问题 12 假设存在一个婚姻介绍所 很多未婚男女把自己的信息和偏好提供给婚姻介绍所 然后由婚姻介绍所根据参与人偏好来进行匹配 有两个有限集合M m1 m2 mn 和W w1 w2 wn 分别表示所有的未婚男士和女士的集合 M W 每个男士 女士 都对女士 男士 有各自的偏好 假设 单身 总是参与人可以选择的策略之一 即如果某人认为结婚不如保持单身的话 那么他总是可以选择单身 与传统的选择理论的假设相同 所有参与人的偏好都是完备且可传递的 即其偏好是理性的 13 假设P m 表示某男士在集合W m 上的偏好 比如P m w1 w2 w5 w9 m这表明 他最希望与w1匹配 其次是与w2 最后是单身 偏好没有出现的所有女士对于此都是不可接受 也就是与她们匹配不如单身给他带来的效用水平更高 如果某个人参与人选择了单身 则称他是自我匹配 女士偏好也类似地给出 P w 表示某男士在集合M w 上的偏好 比如P w m3 m1 m9 m12 m8 w 14 在匹配博弈中 我们假设参与人对于不同的匹配的偏好仅仅取决于自己的偏好 而不是考虑别人的参与人的偏好 也就是说假设参与人是自利的 即某男m认为匹配a比b好 当且仅当他认为u a 比u b 要好 所有参与人的偏好的集合记为P P P m1 P m2 P mn P w1 P w2 P wp 则婚姻市场就可以表示为 M W P 定义匹配 M W W M 从而如果 m m 则 m W 如果u w w 则u w M U x 称为x的配偶 所有匹配的集合记作 M W 为了表达方便 把每个匹配表示成一系列成对的配偶w4w1w2w3 m5 m1m2m3m4m5 15 假设 i i M W是参与人i的保留效用 每对男女的保留效用向量记作 m w 对于 m w M W 形成匹配所带来的效用是 m w 因此 M W 就是匹配博弈P 所有匹配博弈的集合记为G 0的所有匹配博弈的集合记为G0 对于任意P G和任意u M W 博弈P的匹配u所带来的总得益为 使得总得益最大的匹配称为最优匹配 所有最优匹配的集合记作O P 16 Gale和Shapley给出了该问题的一个著名算法 第一轮 所有男生向他们最心仪的女生求婚 所有收到求婚的女生们从自己的追求者中选择自己最喜欢的人作为男朋友 为了简单起见 假定女生只能选择一个作为自己的男友 第二轮 还处于单身状态 也就是被拒绝过 的男生们 每个人再次向自己还没有求过婚的女生中自己最喜欢的人求婚 无论自己喜欢的女生是否已经有男朋友 所有收到求婚的女生们现在从自己的求婚者中选择自己最喜欢的人接受为男朋友 如果原来有男朋友但现在的求婚者中有自己更喜欢的 则拒绝原来的男朋友 选择现在自己更喜欢的求婚者 第三轮 如果有的话 还是按照这样的规则来 一直进行到不再有男生求婚了为止 然后所有被接受的男生和接受他的女生结婚 如果有剩下的单身男生和单身女生 那么他们仍然保持单身 匹配过程全部结束 17 可以用下面这个例子来说明这个匹配问题和匹配算法 假定有三男 甲乙丙 和三女 1 2 3 甲和乙的偏好排序相同 都是1 2 3 丙的排序是女1 女3 女2 女1的偏好依次是甲 乙 丙 女2的偏好排序依次是甲丙乙 女3的偏好排序是甲乙丙 假定是男的开始求婚 女生只考虑接受与否 第一轮 甲乙丙都向女1求婚 女1接受甲 拒绝乙丙 第二轮 乙向女2求婚 丙向女3求婚 女2和女3分别接受乙和丙的求婚 匹配结束 最终匹配结果是甲和1 乙和2 丙和3 18 在传统的完全竞争的市场上 价格调整可以实现供需平衡 但在一些特殊市场中 由于法律或者道德的原因 价格不能用来作为配置资源的手段 资源只能以匹配或配给方式来分配 而且很多时候市场非常的小 可供分配的资源也存在很大差异 比如不同人的肾脏 不能适用完全竞争的经济学 这个时候 就需要匹配和市场设计理论 匹配市场的一个关键问题是 如何保证一个匹配组合是稳定的 在前面的例子中 假定信息是完全的 各方都了解其他参与者的偏好 且每个人都会如实报告自己的偏好 在实际应用中 参与各方会不会狡猾地瞒报自己的真实偏好 19 while存在男人m是自由的且还没对每个女人都求过婚选择这个男人m令w是m的优先表中还没求过婚的最高排名的女人ifw是自由的 m w 变成约会状态elsew当前与m1约会ifw更偏爱m1而不爱mm保持自由elsew更偏爱m而不爱m1 m w 变成约会状态m1变成自由endifendifendwhile 20 Gale Shapley方法的合理性说明算法的可终止性可证 每个男人按照自己的偏爱序一个个求婚下来 一定有一个女人会要他 试想一个男人被一百个女人拒绝掉了 那他的偏爱序中已经没有人可以求婚了 所以他得不到配对 对应地对面也肯定有一个剩女 可是这个剩女曾经拒绝过他呀 也就是说她有更好的追求者呀 她怎么可能成为剩女呢 算法的正确性也可证 假设有A男和B女私奔了 那么A在B的偏爱序中必然比B的丈夫靠前 按照算法 女人最后选择的一定是所有向她求婚的男人中她最喜欢的 这就是说A没有向B求过婚 要不然B选的就是他了 然而 男人是按照自己的偏爱序依次求婚的 而A又喜欢B甚于自己的老婆 所以A又必然向B求过婚 推出矛盾 故不可能出现私奔 21 3 稳定匹配激励相容 合作博弈中的稳定匹配概念 相当于非合作博弈中的纳什均衡概念 在非合作博弈中 纳什均衡指的是任一博弈参与人都不可能单方面改善自己的处境从而没有积极性偏离目前的策略组合 类似的 在合作博弈中 稳定匹配是指没有任何一个 联盟 可以单方面偏离目前的匹配结果来改善联盟成员的处境 前面讨论的GS算法实际上是一种确保稳定匹配的算法 这是因为任何一个男子 如果他发现某个女子比他女友更好的话 那么这个女子一定曾经拒绝过他 也意味着在该女子看来有其他男的比他更好 这意味着即使再给他一次机会 他还是会被拒绝 因此他会现实地接受目前的结果 也就是说他不会后悔 用博弈论的术语讲 这个算法达成的结果是稳定的 22 匹配的另外一个问题是 GS算法能否帮助匹配参与者在真实世界的市场上找到一个稳定的匹配结果 要回答这个问题需要利用非合作博弈工具来分析 在前面的GS算法中 无论是求婚还是拒绝都是个体分散决策 在实际应用 特别是医生和医院 学生和学校的匹配中 匹配结果都是通过一个中央结算所来进行的 很自然的 一个问题 是否所有的个体都会如实将自己的偏好顺序报告给这个中央结算所 他们是不是会操纵自己的偏好 以获得对自己最有利的匹配结果 23 罗斯 1982 证明 一般来说 不存在对所有参与人都激励相容的稳定匹配机制 罗斯还进一步证明 所有的偏好操纵 只要是非劣纳什均衡的 那么它都是一个稳定的匹配结果 这个结果看上去很糟糕 不过 在现实中 个体的信息非常有限 我们很难来了解其他参与者的真实偏好 所谓青菜萝卜各有所爱 因此 在一个很大的匹配市场上 个体伪报真实偏好的激励是非常有限的 所以一般来说不用太担心激励相容问题 这个结果表明在大的匹配市场上 Gale Shapley算法具有很强的应用性 这是为什么在过去的几年里面 无论是匹配的理论研究还是实际应用 都非常热门的一个重要原因 一些评论人士认为今年的诺奖非常冷门 这个是非常错误的 24 4 匹配应用之美国住院医生制度改善 虽然匹配理论的研究在上世纪6 7十年代就得到了学界的重视 但是它的实际应用却一直到八十年代才逐渐为人民所重视 匹配和市场设计的应用主要归功于罗斯 他在1984年的研究中清楚地表明类似于GS的算法是美国住院医生制度得到改善的根本原因 在40年代 美国的住院医生制度是非常糟糕的 医院为了竞争优秀的医学院学生 不断将给学生提供offer的日期提前 甚至提前到学生毕业前几年 而且为了让自己心仪的学生和医院签约 医院给学生考虑的时间日渐缩短 这样做的恶果很多 一是这个匹配结果本身未必是有效的 二是学生在压力下的签约通常会导致后悔 三是医院在被学生拒绝的情况下 不能给其他合适的学生提供更多的机会 25 为了解决这个问题 美国在50年代初期成立了一个 NationalResidentMatchingProgram NRMP 住院医生匹配项目来对所有的医院和医生进行匹配 作为一个中央匹配者在实习生和医院之间匹配 其方法本质上是和前面的GS算法是一样的 在实施这个项目后 参与这个项目的医院和医生比例极大地提高了 一般认为 正是这种算法极大地提高了稳定匹配的比例 否则的话医生和医院就会绕开这个项目自己去单独协商 26 27 5 匹配应用之肾脏交换项目 在多数国家 肾脏交易都是非法的 但是病人的家属可能会愿意为自己的亲人提供肾脏移植 可是亲人之间的肾脏血型未必匹配 直接的肾脏移植无法实施 但是如果 病人A的亲属A 愿意换肾 病人B的亲属B 也愿意换肾 而且刚好B 的肾适合A A 的肾适合B的话 那么互惠的双边交换就可能成功 在实际生活中 情况可能没有这么巧 那么这个肾交换链可能就会涉及更多的病人和捐赠者 以美国为例 目前等待肾脏捐赠的患者名单上有8 5万人 每年有4 000名患者因器官短缺而死亡 一个重要原因是捐赠匹配系统的效率太低 28 2003年 罗斯开始负责设计新系统 对于想捐肾给亲人 但由于血型不匹配无法实现的案例 该系统可以帮助他们与其他不匹配的捐赠组交换器官 目前 虽然利用这一系统进行肾脏移植的患者还不多 2009年只有不到1 000例 但是它的前景仍为许多人看好 纽约时报就曾经详细报道过一个涉及60位病人和30位器官捐赠者的连环交换 它取得了巨大的成功 这个成功在很大程度上要归功于研究匹配和市场设计的学者 特别是罗斯教授这样的人 一些评论家说诺奖只关心理论 不太关心现实 这也是非常错误的看法 好的市场设计 会和好的工程设计一样 具体而实在地影响到我们的生活 29 6 中国应用之婚恋网网站 市场设计是过去理论和业界最为关注的一个问题 在中国 除了学校录取 器官移植等 还有很多其它方面的应用 特别是网络平台作为匹配市场的应用 在这里用两个例子来说明 例子1 世纪佳缘婚恋网站 婚礼网站是典型的匹配市场 它采用什么样的匹配机制 会很大程度上影响到匹配的结果是否稳定 更重要的是 正如全美住院医生制度的例子所表明的 采用什么样的匹配机制 会影响潜在的参与者是否加入这个匹配市场 对于世纪佳缘这样的公司来说 好的匹配机制 不仅能够使得匹配结果更加稳定 而且会鼓励潜在的客户 也就是那些适龄未婚男女加入这个平台 30 目前婚恋网站一个重要的问题是参与人信息的真实性 确保信息的真实性可以极大鼓励参与程度 同时打击那些不以结婚为目的的交友行为 另一方面 匹配理论表明 应该尽可能让参与者对市场的另外一边有一个严格的排序 但是因为市场的参与者非常多 所以婚礼网站应该有一种合理的打分程序 来协助征婚者排序 明确的征婚条件可以提高婚姻匹配的效率 注意 个体的偏好是否功利是另外一回事 这里不讨论 31 7 中国应用之二手市场 例子2 二手商品市场 58同城 赶集网 二手商品市场的一个重要特征是 每一件商品差异都非常大 即使是同一品牌同一年份的汽车 也可能因为车主的使用情况而变得完全不同 另一方面 很多二手商品由于闲置没用产生应有的价值 比如很多家庭都有被淘汰的二手数码相机或者电脑 而这些产品对低收入家庭或人群却可能有一定的价值 如何使得这些商品能够分配到更更产生价值的人手里 是二手商品网络平台需要解决的问题 32 8 匹配应用前景广阔 今年的经济学奖是理论和应用完美结合的一个典型例子 经济学的发展实际上越来越注重其实际应用 好的经济学不仅有漂亮的理论 还能够实实在在的帮助我们改进福利 促进资源的更好分配 匹配理论的应用是非常广泛的 除了上面提到的这些例子 工作岗位的匹配 灾区资源的调配 大学课程和老师的安排 都可以适用这个理论 市场设计是过去10多年里面发展最迅速最热门的一个领域 它的成功和它与真实世界的密切联系有很大的关系 无论是电信波段 3G牌照 污染排放权 资产抵押信贷拍卖等都是市场设计的成功例子 33 排列博弈 排列博弈最早有Tijs 1984 作为一种成本博弈提出的 考虑下面这样一个机器排列问题 参与人i N 1 2 n 拥有一台机器Mi 且有一个任务Ji待完成 任何机器Mi都可以完成任务Ji 但是每台机器至多只能完成一个任务 允许形成联盟且效用可以参与人之间转移如果参与人之间不进行合作 则任务Ji只能在Mi完成在机器Mi上完成任务Ji所需要付出的成本是kij 1 I j n此问题可以用合作博弈 N c 来刻画 34 35 比如 C 2 3 min 6 9 8 10 15 即联盟 2 3 的最小成本是任务2在机器2上完成的成本 任务3在机器3上完成的成本与任务2在机器3上完成的成本 任务3在机器2上完成的成本的最小值 一次类推 再如C 1 2 3 min 2 6 9 2 8 10 4 1 9 4 10 7 3 6 7 3 1 8 12 可见 对于 S N 在求解c S 时要考虑 S 种情况 而且 如果三个参与人都愿意合作的话 那么成本最小的结果是 任务1在机器3上完成 任务2在机器1上完成 任务3在机器2上完成 这样 总成本是12 是所有排列中最小的 下表中列出了与该成本矩阵相对应的排列博弈 N c S 1 2 3 1 2 1 3 2 3 1 2 3 C S 02695101512 36 例2A B C三人下周要去看牙医 ABC分别预约在周一 周二 周三 A希望能够变更一下看牙时间 因为他下周一开始时会很忙 B的牙痛突然加剧 因此 他但愿尽早看医生 C也希望能够早点看病 以便下周剩下的时间可以集中精力工作 因此 三个人开始商量怎么调换时间 首先 三人各自写出来在某一天看病可以给自己带来的效用是多少 见表 37 用1 2 3分别代表ABC 作为练习 大家可以自己计算一下该博弈的核 它是 9 5 10 2 12 10 15 5 4 14 6 4 2 16 6 凸包 参与人集合N 1 2 n 每个参与人i N认为某个排列 N的价值是kNi i 任意联盟S N都可以变更 以使只有联盟的成员被排列 即 i i i N S 从该问题中可以构造博弈v 对于 S M P 联盟S的价值v S 定义为联盟S所有成员的价值之和在所有可行的排列上的最大值 正式地说 设 s表示满足 i i i N S 的所有排列 i N的集合 则 这就是排列博弈 38 时间表问题的描述设有班级集合C c1 c2 c 教师集合P p1 p2 p 教室集合R r1 r2 r 时间集合T t1 t2 t 时间与教室的笛卡尔积为 N T R t1 r1 t2 r2 t r N中的元素称为时间 教室对 给出了一组课程L L1 L2 L L中的元素Li代表一个五元组 h i p i c i r i req i 其中 h i 为周学时数 p i P为任课教师 c i C为上课班级 r i R为可用教室 req i req1 req2 req 是一组时间 教室和教学方式等的限制条件或要求 39 课表编排就是要求L到N的幂集2N中的一个映射 即 L 2N 并满足如下条件 1 设 Li Xi 2N 如果Xi中选用的时间集合为 t1 i t2 i t i i T 选用的教室集合为Ra i 则要求 Ra i R i 如果 Lm Xm Ln Xn 且m n 则必须Xm Xn 即同一时间中一个教室不能被两门以上的课占用 如果 Lm Xm Ln Xn 且m n 则当c m c n 或p m p n 时 就有 t1 m