匹配市场原理研究与算法实现

1、成绩（采用四级记分制） 本科毕业论文（设计）题目：匹配市场原理研究与算法实现学生姓名 学 号 指导教师 院 系 专 业 年 级 教务处制诚信声明本人郑重声明：本人所呈交的毕业论文（设计），是在导师的指导下独立进行研究所取得的成果。毕业论文（设计）中凡引用他人已经发表或未发表的成果、数据、观点等，均已明确注明出处。除文中已经注明引用的内容外，不包含任何其他个人或集体已经发表或在网上发表的论文。特此声明。论文作者签名： 日 期： 2013年6月1日摘 要匹配市场理论是博弈论在经济学中的应用，在双向选择问题领域应用广泛，该理论对参与市场匹配的双方具有指导意义。该理论可以应用在投标报价、城市地下空间规

2、划、公众聚集场所的消防工作部署、供应链的利润分配、商品住宅定价、信贷市场、自主招生择校、毕业生劳动市场、证券交易、器官交易、医疗保险计划等等问题。本文研究了匹配市场理论的基本原理，并展开分析了匹配市场理论在工作市场中用人单位与应聘者间的匹配问题、高考录取市场的高校与考生间的匹配问题。最后，在理论分析的基础上，用程序模拟实现了整个市场匹配算法。关键词：匹配市场：博弈论；匹配市场的应用 AbstractMatch Market Theory is Game Theory in economics; it has a very important role to the parties involv

3、ed in matching the market as well as a wide range of application of problem areas in the two-way choice. It can be applied in the tender offer, urban underground space planning, public gathering places for fire work arrangements, supply chain profit distribution, commercial housing choice, graduate

4、labor market, securities trading and organ trading, health care insurance pans and so on. In this paper, the basic principle of matching market theory and market theory to analyze the match in the job market between the employer and the candidate matching problem, university and college admission ma

5、rket matching problem between the candidates have been discussed. Finally, we program it, based on theoretical analysis.Keywords：Match Market Theory； Game Theory; the application of Match Market Theory 序言经济学是研究人类行为以及如何将有限或者是稀缺的资源进行有效合理的配置的一门社会学科。传统的经济学长期以来解决的是稀缺资源配置“静态均衡”的比较研究。随着社会、经济的发展，该类研究已经无法满足学

6、者们对资源配置问题的探索以及无法有效解决稀缺资源配置问题中遇到的问题，因此，学者们自20世纪以来，开始逐渐由这种“静态均衡”的研究转向资源配置问题中的“黑匣子”的研究，从而达到稀缺资源配置的“动态均衡”，这就产生了匹配理论。该理论是博弈论的一个分支，最先对匹配理论进行研究的是Gale和Shapley在他们1962年发表的大学录取和婚姻的稳定性一文，目前，经过近五十年的发展，匹配理论在西方国家的劳动力市场和公共学校的择校问题中已经得到了广泛的运用。我国传统的统考统招自从1979年恢复高考以来，已经运行了30多年，但是由于招生环境的复杂性的存在，使得统考统招存在很多的弊病，诸如“一考定终身”、学校

7、招生自主性弱等等。因此，国家与2001年提出并开始实行并且逐步推广了一种新的招生机制自主招生择校机制。然而，在这新兴的自主招生择校机制中仍然存在诸多问题：如“脚踏两只船”、“另觅高枝”等现象普遍存在。因此，利用匹配理论对该机制进行研究进而进一步指导参与者行为将有很大的实际价值。1 匹配市场简介1.1 博弈论简介匹配市场其实就是博弈论思想在经济学方面的实际应用。博弈论（Game Theory），博弈论是指研究多个个体或者团队之间在特定条件制约下的对局中利用相关方的策略，而实施对应策略的学科。有时也称为对策论，或者赛局理论，是研究具有斗争或竞争性质现象的理论和方法。 1.2 稳定匹配理论：匹配市场

8、在很多市场上，货物是私人的，但他们是不可分割和非同性质的，因此传统假定的充分竞争条件并不满足。如熟练技工市场，由于没有两名特征完全相同的技术工人，特定工种的技术工人服务市场相当小。在这些市场中，参与者通过相互交换实现大致的匹配。1.2.1 双向匹配假设有两组市场，参与者是相互分离的，如买方、工人、学生和卖方、雇主、学校，他们必须匹配，然后才能履行相应的职能。1962年，盖尔和沙普利对双向匹配市场进行了研究，他们排除了单边支付（私下交易）情形，认为工资以及其他匹配特征并非通过协商完成的。1.2.2 稳定匹配具体来说，假定市场是由一方是医学院学生和另一方是医院科室构成，每个医院科室只需要一名实习医

9、生，而每名医学院学生只需要一个实习机会。匹配就是将实习机会分配给申请的学生。很自然，学生对科室偏好不同，科室对不同学生偏好也不同。为了方便研究，假定偏好是严格的，当参与者匹配后状况恶化则匹配将不被接受。一般而言，当不能通过联盟改进参与者效用时，匹配就是稳定的。在这个特定的模型中，一个稳定的匹配必须满足一下两个条件：没有参与者认为这个匹配不可接受，没有科室和学生联盟希望重新匹配而不愿保持现状。第一个条件是个人理性条件，而第二个条件则是指成对匹配是稳定的。这两个条件暗示着没有任何联盟和“科室-学生”组合可以对匹配进行改进。1.2.3 可调整的价格与工资沙普利等人认为分配博弈的核心并非空集，匹配竞争

10、对一系列核心配置形成了严格限制。通过可转移效用，任何核心配置必须满足经济剩余最大化目标。总之，这种匹配是唯一的。然而，工资通常不是单一决定的，会产生利益的两极分化。当雇主最优或者工人最优稳定匹配时，相应的特征是市场以最低工资或最高工资水平出清。分配博弈紧扣自由竞争概念传承了传统的竞争分析，事实上，这个模型是连接核心理念与竞争均衡间的桥梁。研究发现，在雇主发起机制下，每个雇主开始都想聘用的求职者报出低工资，每个求职者都收到多分聘书，将满意的通知保留，其他的予以拒绝。遭到拒绝的雇主继续发放聘书，要么对原来的求职者提高待遇，要么向新求职者发放聘书。这个过程最终会实现雇主最优的稳定匹配。1.3 匹配市

11、场的场景 ·某一类商品（例如房子），一群买房和一群卖方，卖方和买方数量相同 ·商品的质量不同，大家的认识也有差别 ·买方对商品各有一个低价，都追求利益最大化 ·市场按照供需关系自动调整价格，试图达成买卖双方的某种匹配 ·我们关心最终能否大家都满意 -卖方：市场清仓，商品在底价之上都卖出去了 -买方：得到差价最大的商品1.4 匹配市场基本模型匹配市场的基本模型：二部图偏好卖家图 调整价格后的偏好卖家图1.5 匹配市场操作的一般过程第一步，初始价格为0，形成偏好卖家图，看其中是否存在一个买家受限组：第二步，与受限买家关联的卖家调整价格，形成新的偏好

12、卖家图，再看是否存在买家受限组：第三步，与受限买家关联的卖家调整价格，形成新的偏好卖家图，再看是否存在买家受限组：第四步，与受限买家关联的卖家调整价格，形成新的偏好卖家图，此时已经没有受限组，即存在完美匹配：此时，实现了最大估值之和，即实现了社会最优。1.5 市场清仓价格算法以上过程其实可以看成是计算市场清仓价格的算法，可以归纳如下：给定买方估值，卖方从初始价格（0，0，0）开始，按照轮次进行下属操作：a. 构造偏好卖家图b. 识别是否存在买方受限组（S）。若没有，则偏好卖家图存在完美匹配，结束；否则，将受限组对应的卖方集合N（S）中的价格都+1.若因此使得所有卖方价格都大于0，则统一约减最低

13、价至0。c. 开始下一轮。（统一约减不影响偏好卖家图关系）因为市场势能每一轮都是单点递减的，但总不会小于0，因此上述过程是一定能结束的。所以始终存在完美匹配的偏好卖家图，不会出现来回“震荡”的情况。2 匹配市场的应用匹配市场有着很广泛的应用，如：投标报价、城市地下空间规划、公众聚集场所的消防工作部署、供应链的利润分配、商品住宅定价、信贷市场、自主招生择校、毕业生劳动市场、证券交易、器官交易、医疗保险计划等等。可以说，生活中任何涉及到双方选择的问题都可以利用匹配市场理论来解决。这些都是现实生活中非常重要的问题，由此我们也可以看出诺贝尔奖委员会希望以经济学推动社会发展的良苦用心。2.1 就业市场中

14、的实际应用假定应聘者数目和用人单位数目相等，各自对对方有明确的偏好或者说排名，而且只能一一配对。以应聘者为主动方来构造匹配市场模型，假设有四家用人单位以及四个求职者，求职者a，b，c，d对用人单位A，B，C，D的估值分别为（2，9，6，3）、（8，1，4，6）、（5，3，7，2）、（9，6，4，1）。经过1.5小节中市场清仓价格算法运算后可得到完美匹配图如下：由此我们可知，求职者a选B公司，b选D公司，c选C公司，d选A公司是比较合适的。按这个算法，双方一定能一次性达成稳定的组合，绝不会发生配对之后求职者觉得另一所用人单位更好、同时那所用人单位也觉得这个求职者更好，于是两情相悦跳槽的情况；也绝

15、不会有剩下没人要的用人单位或者求职者。这个办法的结果必然是稳定的，但是不能保证所有参与的人都挑选到他的第一选择。那么总有相对占便宜和相对吃亏的一方。该算法指出，主动的一方总是能得到较好的结果。其实，在相互选择，确定最优匹配图后，会出现结果不为一的情况。这是由哪一方主动选择造成的。同时，利用匹配市场主动地一方能得到较好的结果这一特性，我们也可以用之于对弱势群体的保护，如：学校自主招生时候让学生来做主动的一方，器官捐献时，让病人来做主动的一方。2.1 自主招生中的实际应用假设有按学习成绩从高到低排列的学生a、b、c，d，e，f，按公众心中排名由高到低的学校A，B，C，D，E，F。学校自主招生名额均

16、为1，若学生通过自主招生考试则获得拟录取资格，则其在报考志愿时如果选择获得拟录取资格的学校，则其成绩相应上升一档。同时，自主招生考试也是学校获得对学生水平的估值的途径。 现假设自主招生时学校采取主动（现实中也确实是这样的）。自主招生后，A学校对学生a，b，c，d，e，f的估值分别（7，8，6，3，8，2），B学校对学生a，b，c，d，e，f的估值分别为（8，5，4，6，1，8），依此类推，偏好卖家图如下：假设只有b通过了A学校的自主招生考试，则其在A学校的估值加一，也就是说A学校对学生a，b，c，d，e，f的估值变为（7，9，6，3，8，2），偏好卖家图变为：最后，由1.5节市场清仓算法可得出

17、，完美匹配图如下：则可知，当A学校选择e学生，B学校选择f学生，C学校选择c学生时会形成完美匹配，即不会发生学校觉得哪个学生更好、同时学生也觉得该学校更好，从而两厢情悦发生跳槽的事情。若把学生自主招生的成绩作为一个标准来看，那么由此，可以给学校招生时分数定义做出指导。若是学生采取主动的方式，则可对学生选取学校的标准做出指导。由匹配市场的特性可知，本假设是由学校采取主动的方式，因此对学校是有利的，由此可以看出，处于社会主义初级阶段的中国在该方面是不够成熟的，由弱势群体学生来采取主动的自主招生将会是以后的主流。3 匹配市场原理实现 估值矩阵为：12，4，2 8，7，6 7，5，2 时，程序运行结果

18、如下： 估值矩阵为：2，9，6，3 8，1，4，6 5，3，7，29，6，4，1 时，程序运行结果如下： 估值矩阵为：7，9，6，3，8，2 8，5，4，6，1，8 5，3，7，2，6，76，4，1，2，6，38，4，5，2，1，66，3，2，9，7，4 时，程序运行结果如下：总结与展望尽管沙普利和罗斯的稳定理论及市场设计实践并不如金融市场的泡沫理论、套利理论般炙手可热，但从克服市场失灵，提升资源配置效率角度看，这些理论及其应用具有巨大现实意义和深远的影响，尤其是对像中国这样的发展中国家更是如此。致谢在本人毕业设计的完成和论文的撰写中，指导老师XXX老师给了我很大的帮助，以及指导。从开始资料的查阅和后来的毕业设计大体框架的定稿，再到后来论文的修改，X老师给我指明了方向，让我在毕业设计的完成上事半功倍，这样我才能顺利完成本次毕业设计。在此，我表达对X老师最诚挚的祝福以及感谢。 同时，我也要感谢在毕业设计完成过程中我的室友和同学对我的辅导以及支持，对他们给我提出的各种建议以及意见表示感谢。最后，在大学即将毕业之际，我对XX大学XX学院