盖尔-沙普利算法
出自 MBA智库百科(https://wiki.mbalib.com/)
盖尔-沙普利运算法（Gale-Shapley algorithm）
目录 |
盖尔-沙普利运算法（Gale-Shapley algorithm）简称 “GS算法”，也称为 “延迟接受算法”（deferred-acceptance algorithm），是大卫·盖尔（David Gale）和罗伊德·沙普利（Lloyd Stowell Shapley）为了寻找一个稳定匹配而设计出的市场机制。[1]
市场一方的对象 Ai，i=1,2,...,m 向另一方的对象 Bj，j=1,2,...,n 发出邀约，每个 Bj 会对接到的邀约进行比较，保留自己认为最好的，拒绝其它的。邀约被拒绝的 Ai 继续向其它的 Bj 发出新的邀约，直到没有 Ai 希望再发出邀约为止。此时各 Bj 才最终接受各自保留的邀约。该算法的一个关键之处在于，合意的邀约不会立即被接受，而只是暂时保留不被拒绝，也就是 “延迟接受”。[2]
经济学是研究资源最优配置问题的，而真实世界里配置资源的方式多种多样，市场或者说价格机制是经济学研究最多的。但是有一些市场里头，价格的作用受到法律、习俗或伦理道德等限制。最明显的例子就是找对象的时候不是价高者得，而是情投意合才结成夫妻。
[3] 1960年，大卫·盖尔问沙普利：“不论人们一开始的最佳选择是谁，人们最终都能获得稳定的婚姻吗？”
沙普利最终在回信中回答：“让每个男生先向自己最佳选择求婚，然后让女生们在追求者中选出最喜欢的那一个，但先不告诉这个男生，而是告诉其他男生他们已经被拒绝。直到再也没有追求者出现，女生才告诉她最喜欢的那个男生，他被接受了。接着那些被拒绝了的男生会向他们的第二选择、第三选择求婚，直到被接受为止。最后，每个女生都只剩下一个追求者。这时候他们的婚姻就是稳定的，因为男方和女方都会对拒绝过他们的异性产生反感。”
征婚选择的最佳策略：“有n个美女逐个介绍与你约会，依序每次只见一个，你选了她就没机会见到后面可能更好的；如果让她走了，也许后面都不如她，问怎么选结果最好？”这问题经数学推演后有个很简单的一般结果，最大概率选到了心仪美女的策略是：对于n个依次来临的机会，首先对前[n/e]个仅仅作了解，不做选择，然后开始将约会的与前面所有见到的相比，如果更好就接受，否则等下一个。这里e=2.71828…，[n/e]是n/e的整数部分。
1962年沙普利和大卫合写了论文《高校招生与婚姻稳定性》，并发表在《美国数学月刊》上。文中写到：以10名男子和10名女子“婚配”为范例，设想如果由每一名女子先作选择并向最中意男子“求婚”，然后再由每一名男子审视所获所有“求婚”并回绝除了最中意女子以外的其他所有“求婚”，就可以实现稳定分配。设想的核心，是男子保留并延迟接受最中意女子的“求婚”。这一方法获称“盖尔-沙普利运算法则”，又称“延迟接受运算法则”。
看似两个风马牛不相及的事情，被这二位发现了相同的数学形式，不得不佩服数学家的敏锐目光。在这篇文章的基础上，后人不断将其应用于社会的各个方面，比如高校招生、肾脏匹配等，大大促进了社会的发展与稳定。
1984年，罗思研究全国住院医师匹配项目所采用的运算法则，发现它与盖尔-沙普利运算法密切关联。在随后将近10年间对类似项目的研究中，包括对英国的研究，他发现，算法是否能够实现稳定匹配，关系到实际效果的好坏。
1995年，罗思受邀设计一种新算法，以改善全国住院医师匹配项目，满足多种新需求，如毕业生男女情侣想在同一座城市就业。罗思及其同事设计的新算法1997年投入应用，如今每年为美国医院超过2万个岗位提供匹配。
应用于“移植” 。沙普利和罗思的研究在其他领域同样得到应用，如美国小学生选择自己“中意”的公立中学，而公立中学同样选择小学生。这类选择、匹配或分配的主体都具备决策能力，有能动性。
另一种情形下，选择、匹配或分配完全带有被动性质，如肾脏等人体捐献器官如何与需要这些器官的病人匹配。沙普利及其同事建议采用一种非常简单的运算法则，如今在美国一些州已经形成相当复杂的捐献器官交换网络。
设有 5 位男士 A、B、C、D、E 和 4 位女士 a、b、c、d，他们的择偶偏好顺序如下：
| 男人 | 偏好 | 女人 | 偏好 |
|---|---|---|---|
| A | b>a>c>d | a | A>B |
| B | c>b>a>d | b | A>B>C |
| C | c>b>a>d | c | A>B>C>D |
| D | d>c>b>a | d | A>B>C>D>E |
| E | d>c>b>a |
对于以上案例，Gale-Shapley 匹配算法的执行过程如下：
- 算法第一轮，a 女士没有接到邀约，b 接到 A 的邀约，c 接到 B、C 的邀约，d 接到 D、E 的邀约。C、E 先生被拒绝；
- 算法第二轮，C 先生对 b 发出邀约被拒（因为 A>C），E 先生对 c 发出邀约被拒（因为 c已收到B、C的邀约，且c 只接受 A、B、C、D）；
- 算法第三轮，C 先生对 a 发出邀约被拒（因为 a 只接受 A、B），E 先生对 b 发出邀约被拒（因为 A>E）；
- 算法第四轮，C 先生对 d 发出邀约，此时 d 拒绝了 D，而 E 先生对 a 发出邀约被拒；
- 算法第五轮，D 先生对 c 发出邀约被拒（因为 B>D），E 先生退出；
- 算法第六、七轮，D 先生对 b、a 相继发出邀约被拒，第八轮 D 先生退出。
- 至此，D、E 先生和 a 女士单身，b 女士正式接受 A 先生，c 女士正式接受 B 先生，d 女士正式接受 C 先生，匹配完毕。
最后实现的匹配是 A-b，B-c，C-d。基于以上执行过程有如下几个结论：
- 1、Gale-Shapley 算法不一定得到最大匹配。例如 A-a，B-b，C-c，D-d 的匹配能成 4 对，但不是稳定匹配。因为 A 偏好 b 而 b 也偏好 A。稳定匹配条件要求没有配对的两人不能相互 “喜欢”（单方面偏好可以）；
- 2、在算法执行过程中，有可能出现先前保留的邀约后来被拒绝的情况。比如 d 女士开始时保留了 D 先生的邀约，但后来又拒绝他，转而接受 C 先生，体现了算法的延迟选择性。如果不允许延迟选择，必须当即拍板，则问题转化为秘书问题，与 Gale-Shapley 算法假设的情形不同；
- 3、如果把男女角色对调，女士发出邀约，男士来接受或拒绝，在本案例中得到的匹配结果也是 A-b，B-c，C-d。这是因为本案例中只有一个稳定匹配。当存在多个稳定匹配时，只要邀约的发出方不滥发邀约（一轮只邀约一个人），匹配的结果对邀约的发出方有利。如果滥发邀约（例如每轮邀约所有可接受者），则相当于角色对调，结果对邀约的接收方有利。
盖尔-沙普利运算法的实践意义[2]
诺贝尔经济学奖评选委员会在声明中指出，沙普利采用合作博弈理论和比较不同匹配的方法进行研究，确保配置的稳定性，并在匹配过程中限制变量的影响，从而保证匹配的双方不会被对方干扰。
沙普利和其研究团队的成果展现了一种特定方法的设计如何系统地有益于市场中的一方或另一方。而罗斯发现，沙普利的理论能够阐明一些重要市场在实践中的运作机制。通过一系列实验，他发现“稳定”是了解特定市场机制成功的关键因素。此外，他还重新设计了现有的体系以匹配医生和医院、学生和学校、患者和志愿者。这些新的发展都基于沙普利的匹配稳定理论，罗斯还就涉及道德限制和特定情况的方面进行了修正。
“沙普利值”提出了一个好的方法和机制，可以帮助企业如何根据边际贡献进行分配。这种方法是由沙普利在1951年首创的，对于一个参与者而言，不确定结局（如“赌博”、“抽彩”等）的值是以其效用大小对预期结局的评价：这是他期望获得的先验测度（这是“效用理论”的主题）。
类似的方式，人们感兴趣评价一种对策，即，测量该对策中每个局中人的值。由于“沙普利值”强烈的直观吸引力及数学上的易处理，它已成为很多研究的应用的焦点，尤其是在大型经济模型中。交换经济模型已成为许多经济理论研究的焦点。
主要解答的概念是竞争均衡，其中价格以总供给等于总需求的方式确定。通过允许每个联盟能自由地相互交换所拥有的商品而获得的合作对策，被称为市场对策。人们可以求得相应于市场对策的价值。在一个大型交换经济中（单个的交易者是无关紧要的），所有价值配置具有竞争性；因而，若效用是光滑的，那么，所有竞争的配置也是价值的配置。
这一值得注意的结果包括两个很不相同的方面：其一，产生于供给和需求的竞争价格；其二是经济行为的边际贡献。“沙普利值”在经济理论上的其他应用包括税收模型，其中，政治权力结构建立在交换经济或生产经济的基础之上。此外，确定“沙普利值”的那些公理可以方便地转换为适合于解决诸如以一种“公平”的方式考察配置联合成本的问题。
罗斯意识到了沙普利的理论计算结果可以让实践中重要市场的运作方式变得更清晰。在一系列的经验性研究中，罗斯和他的同事展示，为了理解某个特定市场制度为何成功，研究其稳定性是关键。罗斯后来成功地通过系统性的实验室实验支持了这个结论。罗斯在匹配理论和GS算法的基础上，亲身参与了诸多社会实际问题的解决，比如纽约市学生入学问题，医学院学生分配问题以及肾脏移植的匹配问题等。
正如前面已经提到的，这类市场设计可以被推广到大量价格的作用受限的市场里，其中最主要的一类应用是学生择校与就业。学生要选到自己的理想学校和就业单位，而学校和就业单位也想挑选最佳学生，这显然属于两个群体之间如何最优配对且能稳定配对的问题。中国有不少研究高考择校问题的学者，已经在这方面做了一些探索，比较不同的择校机制之间的优劣。
事实上，沙普利和后来的研究者已经对盖尔-沙普利运算法做了改进，也可以被应用到价格起作用的市场中，例如拍卖，尤其是网络拍卖。
- ↑ The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 2012.诺贝尔官网
- ↑ 2.0 2.1 杜丽群 .稳定配置与市场设计实践理论为什么会获诺贝尔经济学奖[N].东方早报,2012-10-23(4).
- ↑ 彭求实.盖尔－沙普利算法 课程分享.知乎.2022-07-29
