多对一稳定匹配格结构.pdf

第38卷 第4期 应 用 数 学 学 报 Vo1．38No．4 2015年 7月 ACTAMATHEMATICAEAPPLICATAESINICA July,2015 多对一稳定匹配的格结构 李建荣 (华南师范大学数学科学学院，广州510631) (E—mail：jrli77@163．tom) 摘 要 在双方市场中定义的博弈概念，可以使市场同方参与者的收益同时达到最大．这种最优 化存在的理论依据是选择匹配的稳定性，选择匹配的稳定性赋予稳定匹配集合一定的格结构， 稳定匹配集合的格结构给出了达到最优化的具体路径．本文用博弈论的分析与证明方法研究多 对一双方匹配市场中的优化路径，证明稳定匹配集合在 Blair偏序下是一个满足分配律的完备 格． 关键词 匹配博弈；稳定匹配；格 MR(2000)主题分类 06D10；91B68 中图分类 0225；F224．32 1 引言 博弈论的研究模型涉及多个利益相冲突的参与者，每个参与者有多个不同的策略， 每个参与者的最终收益不仅取决于他 自己执行的策略，还取决于所有其他参与者执行 的策略．一般情况下，多个 目标收益难以同时达到最大；所以在博弈理论研究中，缺少 运筹与管理科学其它领域取得的最优化结论．博弈理论关注的是在一些 恰“当”定义下 的稳定结果，如纳什均衡或帕累托最优．因此，在匹配博弈理论中研究最优化及其路径 问题，具有重要的理论和现实意义． 2012年诺贝尔经济学奖授予美国匹配博弈理论学家埃尔文 ·罗斯 (AlvinE．Roth) 与罗伊德 ·夏普利 (LloydS．Shapley)，使匹配博弈理论成为近期国际与国内同行高度关 注的一个热点问题．巧合的是，作者 []在 2012年证明了Roth[2]关于多对一双方匹配市 场中的最优化及其路径问题的结论都是不正确的；而双方市场中的最优化及其路径问 题在最优化理论，市场机制设计与市场管理领域都有广泛应用；鉴于此，本文研究了多 对一双方匹配市场中的优化路径． 本文 2013年 12月 9日收到．2014年 4月 11日收到修改稿． 国家 自然科学基金 (No和广东省自然科学基金 (No．$2013040016469)资助项目 642 应 用 数 学 学 报 38卷 在双方市场中定义的博弈概念 (如匹配、稳定匹配等)，可以使市场同方参与者 (如 企业或工人)的收益同时达到最大 ([3，定理 2])．这种最优化存在的理论依据是选择匹配 的稳定性，选择匹配的稳定性赋予稳定匹配集合一定的格结构，稳定匹配集合的格结构 给出了达到最优化的具体路径．Li4[]证明了多对一选择匹配的稳定性．本文用博弈论 的分析与证明方法研究多对一双方匹配市场中的优化路径，证明稳定匹配集合在Blair 偏序下是一个满足分配律的完备格． 格 (1attice)是一个数学概念，但被广泛地应用于运筹与管理科学的研究中，为现实 经济现象的分析提供了一个有效的数学工具．因为格具有的良好性质，如任意两个元素 都有一个最小上界 (上确界)和一个最大下界 (下确界)，因此在匹配理论的研究中格具 有重要地位．任意两个稳定匹配是否具有一个上确界?如果有，那么市场同方参与者之 间除了竞争还可以合作，共同达到利益的提高．但在匹配理论中研究格，难点是选取一 个恰当的偏序关系． Knuth[]研究了一对一稳定匹配的格结构，证明了一对一稳定匹配集合是一个满足 分配律的完备格． Roth[1尝试把Knuth的结论推广到多对一市场．他首先证明了由企业作选择的多 对一选择匹配的稳定性 (2『，定理 7])，在此基础上称多对一稳定匹配集合在企业公共偏 好偏序下是一个完备格 ([2，定理 10])．Roth将 Knuth结论的一部分推广到了多对一市 场，但较之Knuth的结论，他的不足之处在于：首先，Roth的格缺少一个定义 自然的 下确界；其次，Roth的格不存在一个对偶的结论，即稳定匹配集合在工人公共偏好偏 序下是否是一个格；最