2012 年，美国经济学家阿尔文·E·罗斯（Alvin E. Roth）和罗伊德·S·沙普利（Lloyd S. Shapley）因其“稳定匹配理论和市场设计中的实践”获得诺贝尔经济学奖。

最近发现了一位宝藏经济学家，他就是《小学二年级就能读懂的经济学的作者》的作者坂井丰贵。我们都知道，经济学的很多书，一般人都看不下去，然而，坂井丰贵就特别擅长把复杂的经济学问题表达得简单直白，即使不会复杂的模型和高深的数学基础，也能看明白。

《合适：从升学择校、相亲配对、牌照拍卖了解新兴实用经济学》是坂井丰贵16年在国内出版的书，在这本书中，他通过简单的案例说明，如何将2012年诺贝尔经济学奖的匹配理论用于肾脏移植、求职、择校、相亲、牌照拍卖等领域，讲得通俗易懂、简单有趣。其中，TTC算法（最适交易循环法Top-trading Cycles Algorithm）既简单又强大，我们一起来看看TTC算法如何实现最佳住宅分配和肾脏移植匹配。

一 基本概念：帕累托改进、帕累托最优、强核配置

背景：学生1住在房间1，学生2住在房间2，学生3住在房间3，学生4住在房间4。因为学生宿舍房间的位置、大小、光照和房租等条件不同，每个学生对于房间的偏好也有所不同：有的学生喜欢大的房间，不在乎房租；有的学生宁愿选择房租便宜一点的，不在乎光线和大小。

交换规则：通过交换房间，改善学生的居住满意度，保证每个人都不会换到比现在更差的房间，这种约定就是

上面的表格显示出，每个学生对于房间的偏好，比如，学生1最喜欢房间4，其次是房间3，然后是房间2，第四位才是现在的房间1。从表中，我们可以发现，学生1、3、4目前住的房间都是自己最不喜欢的，只要保证学生2不住在房间1中，交换对每个人都是有利的。

现在，我们来看两个方案A和B，在B方案中，学生1和2的满意度比方案A中的满意度更高，这就是说，方案B相对于方案A是一种帕累托改进，方案A不是最好的匹配方案。那么B方案是不是最好的方案？

再仔细看一下，我们就会发现，在B方案的情况下，学生2和学生3可以通过私下交换房间，而得到自己最想要的房间，这将会导致参与交换的人数减少，交换产生的满意度也会降低，

我们需要寻找一种不会发生阻止，又能使每个人的偏好得到最大的满足的分配，是一种帕累托最优的方案，即没有方案比这个方案更好的了。这种方案就是强核配置。为什么强核配置这么重要，因为这是保证资源得到合理配置的最佳解决方案，尤其是当资源能够拯救人的生命时，这一点就变得尤为重要。

方案C在这个例子中，就是一种强核配置。它能保证：一、没有人会进行私下交换，即阻止；二、满足了个体合理性；三、这是一个帕累托最优的方案。

强核配置除此之外，还有两个特点：强核配置一定存在，这已经被经济学家罗伊德·S·沙普利和赫伯特•斯卡夫证明；强核配置一定是唯一的，这被阿尔文·E·罗斯和安德鲁•波斯尔思韦特证明。现在的问题变成：如何找到强核配置？

在住宅市场模型中，假如有N个学生住在N个房间中，分配的方式就有N的阶乘：N！=N*(N-1)……*2*1种。比如，4个学生，4个房间会24种匹配方案，而到了10个学生，10个房间，就会产生360万种方案。

如何在如此庞大的分配组合中，找出唯一的强核配置方案呢？这就需要一个特别强大的算法:TTC算法（最适交易循环法Top-trading Cycles Algorithm）

二 TTC算法（最适交易循环法Top-trading Cycles Algorithm）

TTC算法是由数学家戴维•盖尔发明的，在1974年，首次被经济学家沙普利和斯卡夫在论文中公开发表。我们来看看TTC算法有多好用。

现在假设，7个学生住在7个房间中，那么总共就有5040种分配方案，我们需要在这些方案中找到唯一一个强核配置。在TTC算法中，按照学生和最喜欢的房间进行匹配，学生1对应房间5，依次如下面所示：

第一轮：

1→5

2→3

3→4

4→1

5→4

6→7

7→1

从学生1开始，寻找第一个闭合循环，即1→5，5→4，4→1。此轮确定：学生1住房间5，学生5住房间4，学生4住房间1。

第二轮：剩下的学生2、3、6、7只能从剩下的房间2、3、6、7选择自己最喜欢的房间，比如，房间4已经被学生5住了，房间5被学生1住了，学生3只能放弃自己前面两个选择，选择第三偏好的房间2，依次如下所示：

2→3

3→2

6→7

7→7

从学生2开始，寻找闭合循环：第一个闭合循环，2→3；3→2；第二个闭合循环：7→7。此轮确定：学生2住房间3，学生3住房间2，学生7住房间7。

第三轮：只剩下学生6和房间6。强核配置结束。

在TTC算法中，每一轮至少会有1人离开，也就是说，如果有N个学生，N个房间，最多经过N轮就能找到强核配置，这比前面的N的阶乘种方案，工作量大大减少。在这个例子中，TTC算法通过3轮匹配，就能从5040种方案中找到了唯一、最佳的强核配置方案。

TTC算法不仅能够快速得出强核配置组合，还被证明

经济学家还证明了，强核规则唯是一满足帕累托最优、个体合理性和防策略性的规则。

三 从住宅模型发展到肾脏移植匹配

我们都知道，在各个国家都禁止进行器官买卖，以防止出现严重的伦理问题，所以肾脏交易市场的存在是不合法的。那么，连交易市场都不存在，肾脏移植问题能算是经济学问题吗？

肾脏移植的过程，其实就是将需要移植肾脏的患者和肾脏捐献者匹配起来，同时又因为肾脏捐献者大大少于肾脏患者，因此，肾脏移植匹配其实就是稀缺资源的分配问题，肾脏患者和捐献者之间存在一种供求关系，从这个角度来看，肾脏移植匹配确实是属于经济学研究的范围。

坂井丰贵说，

相比于住宅模型，肾脏分配模型进行了以下的修正：

住户=患者

住户的房间=针对某个特定患者的捐献者

空房间=新的捐肾源，在此案例中，假设房间5、6、7为空房间

新的入住者=没有捐献者的患者，在此案例中，假设学生5、6、7为新的入住者

不仅学生选择自己最满意的房间，房间也选择学生。规则如下：

·规则 1 现已有人住的房间，指定该既有住户。

·规则 2 现在空着的房间，按照指定优先顺序最高的学生。

现在我们来看一下，在新的情况下，TTC算法的应用。

第一轮：每个学生指出自己最满意的房间，同时，房间按照规则 1 和规则 2 指定学生，在第一轮中，空房间5、6、7优先供新的入住者学生5选择。为了区分学生和房间，房间编码用①—⑦表示。

1→⑤ ①→1

2→③ ②→2

3→④ ③→3

4→① ④→4

5→④ ⑤→5

6→⑦ ⑥→5

7→① ⑦→5

从学生1开始，形成了循环 1→⑤ →5→④ →4→① →1。于是，学生1得到房间 5，学生5得到房间 4，学生4得到房间 1。

第二轮，剩下学生 2、3、6、7，房间 2、3、6、7。学生指出其中自己最满意的房间，同时房间按照规则 1、2 指定学生，空房间6、7优先供新的入住者学生6选择：

2→③ ②→2

3→② ③→3

6→⑦ ⑥→6

7→⑦ ⑦→6

这一轮，产生两个循环：2→③→3→②→2 和6→⑦→6。学生2得到房间3，学生3得到房间2，学生6得到房间 7。

第三轮，现在只剩下学生7和房间6，学生 7 得到了房间 6。

这就是修正后的TTC算法的应用，因为实际中捐肾数量严重不足，所以，相当于患者得到的是列入等待名单靠前的权利。从前面的案例中，我们可以看到，TTC算法的简单和强大之处，在处理人与物的组合时，它真正做到了物尽其用。当被实际运用于医学界，因为更合理地匹配稀缺肾源而拯救了很多患者的生命。

通过《合适》这本书，我们可以获得另一种看待经济学的角度，那就是很多经济学家的基础研究工作，正在慢慢地改善这个世界。也许我们应该给予经济学更多的关注和支持，也学会用经济学的思维来改善自己的生活。

閱讀更多 馴養一本書 的文章

關鍵字: 罗伊德 哈罗·沙普利 诺贝尔经济学奖