双边匹配理论研究综述

摘 要：“匹配”是人类社会常见的现象，而“双边匹配”便是理解该问题的重要理论。该理论创始人凭借在该领域的研究奉献获得了2012年诺贝尔经济学奖，该理论也充分应用在了高考匹配、劳动力市场匹配等领域。本文通过对双边匹配概念、算法进行详述，帮助读者更全面的了解该理论。

关键词：双边匹配

1 双边匹配的概念

“匹配”是人类社会常见的现象，在婚姻中男女双方需要匹配，在市场上买方与卖方需要匹配，在劳动力市场上雇主与雇员需要匹配。而匹配理论便是从这些现象出发，研究其内在机制与相关问题。2012年，诺贝尔经济学奖授给授予学者埃尔文·罗斯（Alvin E. Roth）及加州大学罗伊德·沙普利（Lloyd S. Shapley），得奖的理由是“以鼓励他们在稳定配置理论及市场设计实践上所作出的贡献”。 “双边匹配理论”便是理论的核心。

双边匹配的概念，最早是由Roth（1985）总结提出，“双边”强调市场中的参与者属于两个不相交的集合，“匹配”强调了市场交换的双边性质，双方都具有稳定性偏好。双边匹配理论，就是以双边匹配为研究对象，研究具有稳定偏好的不相交的双方的匹配过程。

双边匹配通常按照其双边匹配对象的数目，分为一对一匹配、一对多匹配、多对多匹配。

一对一（1：1）匹配是指一方是一个个体，另一方也是一个个体的匹配。如男女婚姻匹配，最后匹配结果是一位男士匹配到一位女士。

一对多（1：n）匹配是指匹配双方一方是个体，另一方是组织（招收多个个体）的匹配。如雇员雇主匹配，最后结果每个雇主招到多个雇员，而每个雇员只匹配到一个雇主。其他的例子还有学校-学生匹配。

多对多（n：n）匹配是指双方都可以和多个对方匹配的情况。常见的是顾客与电商平台的匹配，单个顾客可以选择多个电商平台购买商品，而单个电商平台也同时服务多个顾客。

2 “双边匹配”经典婚姻模型与GS算法概述

Gale 和 Shapley在1962年提出的男女婚姻匹配模型与经典的GS递延接受算法，本模型是该领域许多其他研究的基础，包括模型与算法构建、稳定性（核）的讨论以及策略行为的讨论。

2.1 模型与算法构建

设有n位男士和n位女士，假设他们彼此都相互认识，双方都希望寻找到心仪的另一半。在匹配开始前，每一位男士对所有的n位女士都有一个心中的严格偏好排序，每一位女士同样对n位男士有一个严格偏好排序。双边匹配理论研究的，便是通过怎样的机制，能够让双方获得稳定的匹配结果，并且让双方都满意。

首先，我们可以把问题抽象化，设n位女士的集合为M={w1，w2，……，wn}，n位男士的集合为W={m1，m2，……，mn}，目标是要找到一个稳定的匹配集合C={（w1，mk1），（w2，mk2），……，（wn，mkn）}，其中ki属于M（i=1，2，…，n）。Gale 和 Shapley最早提出的是男士先选的递延接受算法，这种算法对男士有利。算法的过程如下：

第一轮：每个男士都向自己最喜欢的女士发出邀请。此时女士会存在三种情况，没有收到邀请，收到一份邀请，收到多份邀请。如果收到多份邀请，那么该女士需要按照自己的排序，选择最喜欢的那个男士，然后拒绝其他人。

第二轮：所有被拒绝的男士向他下一位喜欢的女士发出邀请，上一轮没有被拒绝的男士再次向他上一轮发出邀请的那位女士发出邀请。同第一步，收到多份邀请的女士选择最喜欢的那个男士，然后拒绝其他人。

……

第k轮：不断重复第二步，被拒绝的男士向他偏好列表的下一位女士发出邀请，其他均相同

直到：所有男士都没有被拒绝，算法结束。

2.2 “稳定匹配”问题

只要满足每个个体对对方都有严格偏好，且所有人的匹配都是可接受的（即有另一半總比单身好），那么该算法通过至多n2-2n+2轮后便会结束，并且Gale 和 Shapley证明了其结果是最优稳定匹配。这里的稳定匹配（stable matching）是指当算法结束后，对于任意男士mk，设其最终匹配了wp，在女士集合中，无法再找到一个女士wq，设wq匹配的mi，而这位女士的优先级列表中，是mk优先于mi的。通俗的来讲，所有男性已经和在考虑其他男士竞争的情况下不会拒绝他的，列表中最靠前的女性进行了匹配。Vate（1989）进一步指出，整个稳定匹配问题，其本质上就是一个线性规划问题。

值得说明的是，在这个模型中，因为每次都是男方提出主动邀请，所以最后的匹配结果对男方是最优的，而对女方仅仅只是可接受的。相反，如果算法每一轮都是女方提出邀请，而男方只有接受与拒绝的权力，那么最后的匹配结果对女方是最优的。

2.3 “策略行为”问题

“策略行为”是指市场的参与者通过策略性的提交自己虚假的偏好序列，来使自己情况得到改善的行为。Roth（1982）对策略行为进行了详细的探讨，证明了策略行为在婚姻模型中是有效的。婚姻模型中，不存在稳定的机制，使所有人申明最优偏好都是占优策略。在男士先选的M-最优中，对每一个男士而言，申明真实偏好排序是占优策略，而对女士而言，策略行为便可能有效。相反，在女士先选的W-最优中，对每一个女士而言，申明真实偏好是占优策略，此时男士的策略行为便可能有效。

更进一步，Roth 和 Sotomayor（1990）证明了至少有一个参与人能通过表达虚假的偏好而获益。不过，策略行为不总是有效的，也可能适得其反，所以对于被动方而言，申明真实偏好也并不一定是劣策略。

参考文献

[1]Gale D. and Shapley L.S. College admissions and the stability of marriage[J]. American Mathematical Monthly， 1962， 69（1）： 9–15

[2]Roth A.E. New Physicians： a natural experiment in market organization[J]. Science，1990，250（4987）：1524-1528.

[3]王塑，李西平，王新，李珊.基于双边匹配理论的人员-岗位适配性研究[J].人力资源管理，2013（12）：343-347.

[4]聂海峰.高考录取机制的博弈分析[J].经济学（季刊），2007（03）：899-916.

[5]张卫东，黄春华.双边匹配理论及其应用研究新进展——对诺贝尔经济学奖获奖成就的进一步阐发[J].经济学动态，2015（06）：137-147.

作者简介

范伟珂（1995-），男，汉族，四川成都人，学生，管理学硕士研究生，中央财经大学商学院人力资源管理专业，研究方向：人力资源管理。