论文部分内容阅读
博弈模型涉及多个利益相冲突的决策者。多个目标收益一般难以同时达到最大，所以在博弈论的研究中缺少运筹与管理科学其它领域所取得的最优化结论。但在双方市场中定义的博弈概念，却可以使市场同方参与者的收益同时达到最大。Roth研究了多对一市场中的这种最优化及其路径问题，但作者证明了Roth的结论是错误的，从而使优化理论成为匹配理论研究中的一个缺口、一个有待解决的问题。鉴于此，梳理了双方市场中资源的优化配置、探讨了解决方法并指出未来的研究方向。
博弈论的研究模型涉及多个利益相冲突的决策者。因为多个目标收益一般难以同时达到最大，所以在博弈论的研究中极度缺乏运筹与管理科学其它领域所取得的最优化结论；而且，博弈模型的理论分析一般不注重确定“最优”结果，而是首先注重确定在一些恰当定义下的稳定结果，如纳什均衡。于是，在以双方市场为研究对象的博弈理论—匹配理论—中研究最优化及其路径问题，就显得尤为重要与迫切。
“匹配”是市场的重要功能之一。谁得到了哪一份工作，谁进了哪一所学校，谁同谁结了婚，谁在哪里买了房产等等，都是匹配的结果。匹配博弈理论运用博弈论的分析方法研究现实双方市场的稳定、及因缺乏稳定而失灵问题，为现世经济现象的分析提供可靠的理论依据。Gale and Shapley 1962年发表在《美国数学月刊》（American Mathematical Monthly）上的文章“College admissions and the stability of marriage”，标志着匹配博弈理论的诞生。
2012年，诺贝尔经济学奖授予美国匹配博弈理论学家埃尔文·罗斯（Alvin E. Roth）与罗伊德·夏普利（Lloyd S. Shapley），使匹配博弈理论成为近期国际与国内同行高度关注的一个热点问题。巧合的是，作者在2012年证明了Roth （1985）关于多对一双方匹配市场中的最优化及其路径问题的结论都是不正确的；作者的论文在运筹与管理类国际一流学术期刊Mathematics of Operations Research上刊发后，立刻引起了国际同行的高度重视与关注，使该问题成为近期国际同行高度关注、博弈论学界急切想要解决的一个重大的、具有挑战性的前沿问题。鉴于此，本文梳理了双方市场中资源的优化配置、探讨了解决方法并指出未来的研究方向。
一、发展状况
在双方市场中定义的博弈概念（如匹配、稳定匹配等），可以使市场同方参与者（如企业或工人）的收益同时达到最大，这种最优化存在的理论依据是选择匹配的稳定性，选择匹配的稳定性赋予稳定匹配集合一定的格结构，而稳定匹配集合的格结构给出了达到这种最优化的具体路径。
Knuth （1976）解决了一对一双方匹配市场中的最优化及其路径问题。Li （2013）证明了Knuth的结论在替代偏好下不能推广到多对一市场。因为多对多市场是最一般化的双方匹配市场，企业与工人具有完全对称的地位，所以最优化及其路径问题在多对多市场也是一个未解难题。多年来不断有经济学家尝试解决这一问题，但都没有得到肯定的结论。
1.选择匹配的稳定性
给定两个不同的稳定匹配，让每一个企业从它在这两个稳定匹配下的匹配对象的并集中，选出它最偏好的工人集合来。这样选择的结果，定义了一个选择函数，称为由企业作选择的选择匹配。作者已经证明了，在替代偏好下，是一个匹配但不一定是稳定匹配。类似地，让每一个工人从他在这两个稳定匹配下的匹配对象中，选出他最偏好的企业来。这样选择的结果，定义了一个匹配，称为由工人作选择的选择匹配。
Gale and Shapley （1962）证明了：第一，当每一个参与者在市场对方个体上有一个严格的偏好时，一对一和多对一稳定匹配一定存在；第二，由拒绝接受算法产生的是一个提议方最优稳定匹配。Knuth （1976）在一对一市场中研究了这种最优化的理论依据：给定两个不同的稳定匹配，让每一个企业（工人）从它（他）在这两个匹配下的匹配对象中选出它（他）偏好的那个来。当参与者具有严格偏好时，Knuth证明了这样选择的结果依然是个稳定匹配。Knuth的成果给Gale and Shapley最优稳定匹配的存在一个自然的解释。
Roth （1984）推广了Gale and Shapley关于多对一稳定匹配的成果：一是当企业在所有工人集合上有一个完备的、具有传递性的和严格的替代偏好时，多对一稳定匹配一定存在；二是由拒绝接受算法产生的是一个提议方最优稳定匹配。 Roth （1985）在多对一市场尝试推广Knuth （1976）的结论：给定两个不同的稳定匹配，让每一个企业（工人）从它（他）在这两个匹配下的匹配对象的并集中选出它（他）最偏好的对象来，这一选择的结果被称为这两个稳定匹配的选择函数。Roth 在替代偏好下证明了：由企业作选择的选择函数是个稳定匹配，由工人作选择的选择函数不一定是个稳定匹配。
Martinez et al （2001）在可分离偏好下研究了由工人作选择的多对一选择匹配的稳定性，他们直接引用Roth的结论来完成他们的主要证明。Blair （1988）提到了，在替代偏好下，由企业作选择的多对多选择匹配不一定是稳定匹配。因为在多对多市场中，工人与企业具有完全对称的地位，所以由工人作选择的多对多选择匹配也不一定是稳定匹配。
由企业作选择的多对一选择匹配的稳定性自Roth （1985）提出后，历经28年，Li （2013）指出Roth的结论是不正确的。Li从选择匹配的构造入手，分析了选择匹配的基本属性，指出Roth的证明忽略了选择匹配的一个重要性质，从而存在严重的逻辑漏洞；并以具体实例表明Roth的结论不一定成立。因为Martinez et al （2001）关于由工人作选择的选择匹配稳定性的证明建立在Roth的结论之上，Li的结论显示他们的成果有待重新考证。又因为多对多市场是多对一市场的一般化，特殊市场不成立的性质在一般化市场一定也不成立。于是，Li（2013）昭示了多对一和多对多市场选择匹配的稳定性成为匹配理论研究中的一个缺口、一个有待解决的问题。 2.稳定匹配的格
格（lattice）是一个数学概念，但被广泛地应用于运筹与管理学的研究中，特别是在劳动力市场的研究中，给现实经济现象的分析提供一个理论依据。因为格具有的良好性质，如任意两个元素都有一个最小上界（上确界）和一个最大下界（下确界）。因此，在匹配理论的研究中格具有重要的地位。任意两个稳定匹配是否具有一个上确界和下确界？如果有，那么市场同方参与者之间除了竞争还可以合作，共同达到利益的提高。但在匹配理论中研究格，难点是选取一个恰当的偏序关系。
Knuth （1976）研究了一对一市场稳定匹配的格结构。在一对一市场中，企业的偏好定义在工人个体上。因此，在由企业作选择的选择匹配下，企业是在工人个体上作比较和选择；而企业公共偏好偏序也是定义在工人个体上；所以容易证明是稳定匹配集合在企业公共偏好偏序下的上确界算子，是下确界算子。Knuth利用和的稳定性，证明了一对一稳定匹配集合是一个满足分配律的完备格。
Roth （1985）尝试把Knuth在一对一市场的格结论推广到多对一市场。他首先证明了由企业作选择的多对一选择匹配的稳定性，然后声称是多对一稳定匹配集合在企业公共偏好偏序下的上确界算子，进一步声称稳定匹配集合是一个完备格。Roth将Knuth结论的一部分推广到了多对一市场，但较之Knuth的结论，他的不足之处在于：Roth的格缺少一个定义自然的下确界；第二，Roth的格不存在一个对偶的结论，即稳定匹配集合在工人公共偏好偏序关系下是否是一个格；最后，Roth没有对格进行分配律的证明。
Martinez et al （2001）在可分离偏好下研究了多对一稳定匹配集合在工人公共偏好偏序下的格问题。他们引用Roth的结论（是稳定匹配），证明了由工人作选择的选择匹配的稳定性，然后证明了多对一稳定匹配集合在工人公共偏好偏序下是一个完备格，和分别是上确界和下确界算子。但他们没有讨论格的分配律问题。
Blair （1988）研究了多对多市场上当参与者具有替代性选择函数时，稳定匹配集合的格问题。他证明了稳定匹配集合在一个“恰当”的偏序 （后继文献将之称为“Blair偏序”）下是一个完备格，但在企业公共偏好偏序下不一定是个格。但Blair格的上确界没有一个明确的定义，并缺少下确界，因而无法自然地解释多对多市场存在最优稳定匹配。而且，Blair的格不满足分配律。
Li （2013）指出Roth （1985）关于多对一稳定匹配的格结论是不正确的。在多对一市场中，企业与工人具有不对称的地位（这与一对一市场不同），工人的偏好依然定义在企业个体上，而企业的偏好定义在工人集合上。企业公共偏好偏序由企业在两个工人集合间择优选取定义，而选择函数却是由企业在两个工人集合的并集中选出最偏好的工人集合定义，这两个定义的结果是不一致的（这与一对一市场不同）。因此，不能简单地把Knuth在一对一市场的结论不加证明地推广到多对一市场。Li以具体实例表明，不一定是企业公共偏好偏序的上确界算子。Li分析了Roth的错误不仅仅是他关于稳定性的证明是错误的，还在于他选择了一个不恰当的偏序关系。因为Martinez et al （2001）的证明依赖于Roth的结论，所以多对一稳定匹配在工人公共偏好偏序下的格问题有待重新研究。
鉴于Li （2013）的证明，结合Blair （1988），多对一与多对多双方匹配市场中的格问题成为近期匹配理论研究中一个引人瞩目和有待解决的问题。
二、研究方向
Li证明了在替代偏好下不一定是稳定匹配，Roth （1985）证明了在替代偏好下不一定是稳定匹配。Li证明了，在替代偏好下，和不是企业公共偏好偏序的上确界和下确界算子。于是，劳动力市场中的资源优化配置研究有如下几个方向：多对一选择匹配的稳定性；多对一稳定匹配的格；多对多选择匹配的稳定性和稳定匹配的格，在前两个研究成果的基础上，解决最一般化匹配市场的优化研究。
三、研究意义
博弈论的研究模型涉及多个利益相冲突的决策者。因为多个目标收益一般难以同时达到最大，所以在博弈论的研究中极度缺乏运筹与管理科学其它领域所取得的最优化结论。但在双方市场中定义的博弈概念（如匹配、稳定匹配等），却可以使市场同方参与者（如企业或工人）的利益同时达到最大；Roth（1985）研究了多对一市场中的这种最优化及其路径问题，但作者在2012年证明了Roth的结论是错误的。鉴于Roth荣获2012年诺贝尔经济学奖桂冠，作者的论文及双方匹配市场中的最优化及其路径问题引起了广泛的社会效应与关注。因此，该问题的研究不仅具有重要的理论与现实意义，还具有重要的社会影响与深远意义。
1.理论意义
作者已经证明了Roth（1985）关于双方匹配市场中的最优化及其路径问题的结论都是不正确的，使该问题成为匹配博弈理论研究中的一个缺口。所以该问题的研究成果有望弥补与完善匹配博弈理论研究。
该问题的成果有助于解决“多对多匹配市场核的存在”这一匹配理论研究中的重大难题，同时为供应链匹配的最优化问题提供理论依据与支撑。
2.现实意义
鉴于选择匹配的稳定性与稳定匹配的格问题在最优化理论、市场机制设计与市场管理方面的广泛应用，该问题的研究有望促进这些相关领域的研究与发展。
该问题的研究成果有助于我国双方匹配市场现存问题的解决，如高校扩招及经济下滑带来的就业压力、房价波动引发地产商与购房者之间的矛盾、中小民营企业融资困境等问题。
3.深远影响
匹配理论作为博弈论的一个独立分支，一直是运筹与经济管理研究中的一个热点与难点，是计算数学、生物工程学和社会科学研究中的一个重要工具，但国内对该理论的研究和应用却极为欠缺。2012年诺贝尔经济学奖颁给了匹配博弈理论学家，使该理论受到国内同行的关注。鉴于国内对匹配博弈理论的研究比较欠缺，该问题的研究，将会引起国内外同行的兴趣与关注，促进国内学界在匹配博弈理论方面的研究与发展应用。
基金项目：国家自然科学基金项目（No. 71301056），广东省自然科学基金项目（No. S2013040016469）。
（作者单位：华南师范大学数学科学学院金融数学系）
博弈论的研究模型涉及多个利益相冲突的决策者。因为多个目标收益一般难以同时达到最大，所以在博弈论的研究中极度缺乏运筹与管理科学其它领域所取得的最优化结论；而且，博弈模型的理论分析一般不注重确定“最优”结果，而是首先注重确定在一些恰当定义下的稳定结果，如纳什均衡。于是，在以双方市场为研究对象的博弈理论—匹配理论—中研究最优化及其路径问题，就显得尤为重要与迫切。
“匹配”是市场的重要功能之一。谁得到了哪一份工作，谁进了哪一所学校，谁同谁结了婚，谁在哪里买了房产等等，都是匹配的结果。匹配博弈理论运用博弈论的分析方法研究现实双方市场的稳定、及因缺乏稳定而失灵问题，为现世经济现象的分析提供可靠的理论依据。Gale and Shapley 1962年发表在《美国数学月刊》（American Mathematical Monthly）上的文章“College admissions and the stability of marriage”，标志着匹配博弈理论的诞生。
2012年，诺贝尔经济学奖授予美国匹配博弈理论学家埃尔文·罗斯（Alvin E. Roth）与罗伊德·夏普利（Lloyd S. Shapley），使匹配博弈理论成为近期国际与国内同行高度关注的一个热点问题。巧合的是，作者在2012年证明了Roth （1985）关于多对一双方匹配市场中的最优化及其路径问题的结论都是不正确的；作者的论文在运筹与管理类国际一流学术期刊Mathematics of Operations Research上刊发后，立刻引起了国际同行的高度重视与关注，使该问题成为近期国际同行高度关注、博弈论学界急切想要解决的一个重大的、具有挑战性的前沿问题。鉴于此，本文梳理了双方市场中资源的优化配置、探讨了解决方法并指出未来的研究方向。
一、发展状况
在双方市场中定义的博弈概念（如匹配、稳定匹配等），可以使市场同方参与者（如企业或工人）的收益同时达到最大，这种最优化存在的理论依据是选择匹配的稳定性，选择匹配的稳定性赋予稳定匹配集合一定的格结构，而稳定匹配集合的格结构给出了达到这种最优化的具体路径。
Knuth （1976）解决了一对一双方匹配市场中的最优化及其路径问题。Li （2013）证明了Knuth的结论在替代偏好下不能推广到多对一市场。因为多对多市场是最一般化的双方匹配市场，企业与工人具有完全对称的地位，所以最优化及其路径问题在多对多市场也是一个未解难题。多年来不断有经济学家尝试解决这一问题，但都没有得到肯定的结论。
1.选择匹配的稳定性
给定两个不同的稳定匹配，让每一个企业从它在这两个稳定匹配下的匹配对象的并集中，选出它最偏好的工人集合来。这样选择的结果，定义了一个选择函数，称为由企业作选择的选择匹配。作者已经证明了，在替代偏好下，是一个匹配但不一定是稳定匹配。类似地，让每一个工人从他在这两个稳定匹配下的匹配对象中，选出他最偏好的企业来。这样选择的结果，定义了一个匹配，称为由工人作选择的选择匹配。
Gale and Shapley （1962）证明了：第一，当每一个参与者在市场对方个体上有一个严格的偏好时，一对一和多对一稳定匹配一定存在；第二，由拒绝接受算法产生的是一个提议方最优稳定匹配。Knuth （1976）在一对一市场中研究了这种最优化的理论依据：给定两个不同的稳定匹配，让每一个企业（工人）从它（他）在这两个匹配下的匹配对象中选出它（他）偏好的那个来。当参与者具有严格偏好时，Knuth证明了这样选择的结果依然是个稳定匹配。Knuth的成果给Gale and Shapley最优稳定匹配的存在一个自然的解释。
Roth （1984）推广了Gale and Shapley关于多对一稳定匹配的成果：一是当企业在所有工人集合上有一个完备的、具有传递性的和严格的替代偏好时，多对一稳定匹配一定存在；二是由拒绝接受算法产生的是一个提议方最优稳定匹配。 Roth （1985）在多对一市场尝试推广Knuth （1976）的结论：给定两个不同的稳定匹配，让每一个企业（工人）从它（他）在这两个匹配下的匹配对象的并集中选出它（他）最偏好的对象来，这一选择的结果被称为这两个稳定匹配的选择函数。Roth 在替代偏好下证明了：由企业作选择的选择函数是个稳定匹配，由工人作选择的选择函数不一定是个稳定匹配。
Martinez et al （2001）在可分离偏好下研究了由工人作选择的多对一选择匹配的稳定性，他们直接引用Roth的结论来完成他们的主要证明。Blair （1988）提到了，在替代偏好下，由企业作选择的多对多选择匹配不一定是稳定匹配。因为在多对多市场中，工人与企业具有完全对称的地位，所以由工人作选择的多对多选择匹配也不一定是稳定匹配。
由企业作选择的多对一选择匹配的稳定性自Roth （1985）提出后，历经28年，Li （2013）指出Roth的结论是不正确的。Li从选择匹配的构造入手，分析了选择匹配的基本属性，指出Roth的证明忽略了选择匹配的一个重要性质，从而存在严重的逻辑漏洞；并以具体实例表明Roth的结论不一定成立。因为Martinez et al （2001）关于由工人作选择的选择匹配稳定性的证明建立在Roth的结论之上，Li的结论显示他们的成果有待重新考证。又因为多对多市场是多对一市场的一般化，特殊市场不成立的性质在一般化市场一定也不成立。于是，Li（2013）昭示了多对一和多对多市场选择匹配的稳定性成为匹配理论研究中的一个缺口、一个有待解决的问题。 2.稳定匹配的格
格（lattice）是一个数学概念，但被广泛地应用于运筹与管理学的研究中，特别是在劳动力市场的研究中，给现实经济现象的分析提供一个理论依据。因为格具有的良好性质，如任意两个元素都有一个最小上界（上确界）和一个最大下界（下确界）。因此，在匹配理论的研究中格具有重要的地位。任意两个稳定匹配是否具有一个上确界和下确界？如果有，那么市场同方参与者之间除了竞争还可以合作，共同达到利益的提高。但在匹配理论中研究格，难点是选取一个恰当的偏序关系。
Knuth （1976）研究了一对一市场稳定匹配的格结构。在一对一市场中，企业的偏好定义在工人个体上。因此，在由企业作选择的选择匹配下，企业是在工人个体上作比较和选择；而企业公共偏好偏序也是定义在工人个体上；所以容易证明是稳定匹配集合在企业公共偏好偏序下的上确界算子，是下确界算子。Knuth利用和的稳定性，证明了一对一稳定匹配集合是一个满足分配律的完备格。
Roth （1985）尝试把Knuth在一对一市场的格结论推广到多对一市场。他首先证明了由企业作选择的多对一选择匹配的稳定性，然后声称是多对一稳定匹配集合在企业公共偏好偏序下的上确界算子，进一步声称稳定匹配集合是一个完备格。Roth将Knuth结论的一部分推广到了多对一市场，但较之Knuth的结论，他的不足之处在于：Roth的格缺少一个定义自然的下确界；第二，Roth的格不存在一个对偶的结论，即稳定匹配集合在工人公共偏好偏序关系下是否是一个格；最后，Roth没有对格进行分配律的证明。
Martinez et al （2001）在可分离偏好下研究了多对一稳定匹配集合在工人公共偏好偏序下的格问题。他们引用Roth的结论（是稳定匹配），证明了由工人作选择的选择匹配的稳定性，然后证明了多对一稳定匹配集合在工人公共偏好偏序下是一个完备格，和分别是上确界和下确界算子。但他们没有讨论格的分配律问题。
Blair （1988）研究了多对多市场上当参与者具有替代性选择函数时，稳定匹配集合的格问题。他证明了稳定匹配集合在一个“恰当”的偏序 （后继文献将之称为“Blair偏序”）下是一个完备格，但在企业公共偏好偏序下不一定是个格。但Blair格的上确界没有一个明确的定义，并缺少下确界，因而无法自然地解释多对多市场存在最优稳定匹配。而且，Blair的格不满足分配律。
Li （2013）指出Roth （1985）关于多对一稳定匹配的格结论是不正确的。在多对一市场中，企业与工人具有不对称的地位（这与一对一市场不同），工人的偏好依然定义在企业个体上，而企业的偏好定义在工人集合上。企业公共偏好偏序由企业在两个工人集合间择优选取定义，而选择函数却是由企业在两个工人集合的并集中选出最偏好的工人集合定义，这两个定义的结果是不一致的（这与一对一市场不同）。因此，不能简单地把Knuth在一对一市场的结论不加证明地推广到多对一市场。Li以具体实例表明，不一定是企业公共偏好偏序的上确界算子。Li分析了Roth的错误不仅仅是他关于稳定性的证明是错误的，还在于他选择了一个不恰当的偏序关系。因为Martinez et al （2001）的证明依赖于Roth的结论，所以多对一稳定匹配在工人公共偏好偏序下的格问题有待重新研究。
鉴于Li （2013）的证明，结合Blair （1988），多对一与多对多双方匹配市场中的格问题成为近期匹配理论研究中一个引人瞩目和有待解决的问题。
二、研究方向
Li证明了在替代偏好下不一定是稳定匹配，Roth （1985）证明了在替代偏好下不一定是稳定匹配。Li证明了，在替代偏好下，和不是企业公共偏好偏序的上确界和下确界算子。于是，劳动力市场中的资源优化配置研究有如下几个方向：多对一选择匹配的稳定性；多对一稳定匹配的格；多对多选择匹配的稳定性和稳定匹配的格，在前两个研究成果的基础上，解决最一般化匹配市场的优化研究。
三、研究意义
博弈论的研究模型涉及多个利益相冲突的决策者。因为多个目标收益一般难以同时达到最大，所以在博弈论的研究中极度缺乏运筹与管理科学其它领域所取得的最优化结论。但在双方市场中定义的博弈概念（如匹配、稳定匹配等），却可以使市场同方参与者（如企业或工人）的利益同时达到最大；Roth（1985）研究了多对一市场中的这种最优化及其路径问题，但作者在2012年证明了Roth的结论是错误的。鉴于Roth荣获2012年诺贝尔经济学奖桂冠，作者的论文及双方匹配市场中的最优化及其路径问题引起了广泛的社会效应与关注。因此，该问题的研究不仅具有重要的理论与现实意义，还具有重要的社会影响与深远意义。
1.理论意义
作者已经证明了Roth（1985）关于双方匹配市场中的最优化及其路径问题的结论都是不正确的，使该问题成为匹配博弈理论研究中的一个缺口。所以该问题的研究成果有望弥补与完善匹配博弈理论研究。
该问题的成果有助于解决“多对多匹配市场核的存在”这一匹配理论研究中的重大难题，同时为供应链匹配的最优化问题提供理论依据与支撑。
2.现实意义
鉴于选择匹配的稳定性与稳定匹配的格问题在最优化理论、市场机制设计与市场管理方面的广泛应用，该问题的研究有望促进这些相关领域的研究与发展。
该问题的研究成果有助于我国双方匹配市场现存问题的解决，如高校扩招及经济下滑带来的就业压力、房价波动引发地产商与购房者之间的矛盾、中小民营企业融资困境等问题。
3.深远影响
匹配理论作为博弈论的一个独立分支，一直是运筹与经济管理研究中的一个热点与难点，是计算数学、生物工程学和社会科学研究中的一个重要工具，但国内对该理论的研究和应用却极为欠缺。2012年诺贝尔经济学奖颁给了匹配博弈理论学家，使该理论受到国内同行的关注。鉴于国内对匹配博弈理论的研究比较欠缺，该问题的研究，将会引起国内外同行的兴趣与关注，促进国内学界在匹配博弈理论方面的研究与发展应用。
基金项目：国家自然科学基金项目（No. 71301056），广东省自然科学基金项目（No. S2013040016469）。
（作者单位：华南师范大学数学科学学院金融数学系）