案例分析：肾交换

许多人遭受了肾衰竭，从而需要肾脏移植。目前，美国等待肾脏移植的列表上大约有10万人在上面。一种也用在其他器官上的老的想法是已故捐赠人――当某个人去世并且是一个注册了的器官捐赠人，他们的器官可以移植给别人。肾脏的一个特殊特征是健康的人有两个肾，而如果只有一个的话也可以活得很好。这就使得在世的器官捐赠人成为可能，例如有需要的患者的一个家庭成员。

不幸的是，有一个在世的肾脏捐赠人并不总是足够的——有时候一个患者-捐赠人对是不兼容(incompatible)的，意味着捐赠人的肾很可能无法在患者身上正常工作。血型和组织类型是不兼容的主要原因。举例来说，一个有O型血的患者只能接受从一个有相同血型的捐赠者那里来的肾，而同样的，一个AB血型的捐赠人只能捐给一个AB血型的患者。

假设患者P1和他的捐赠人D1不兼容是因为他们的血型分别为A和B。假设P2和D2的情况刚好相反，血型分别为B和A（图1）。尽管(P1,D1)从未见过(P2,D2)，交换捐赠人看上去是一个相当好的想法——P1能够从D2那里拿到肾而P2从D1那里。这被成为一个肾交换(kidney exchange)。

图1：一次肾交换。

在本世纪初，发生过一些基于自组织方式的肾交换。这种孤立的成功，使得对于一个全国性的肾交换的需求更加明确，其中不兼容的患者-捐赠人对可以注册并和其他人匹配。这样的交换应该如何设计？这样的一个交换目标是使得肾交换市场越大从而使得更多的匹配成为可能。

全国性的肾交换在过去10年的中间开始涌现。我们会讨论一些关于这些交换的早期设计想法，以及目前的挑战。这些交换和它们底层的算法非常成功，实现了每年数以千计的成功的肾交换。

目前器官捐赠的报酬在美国是非法的（在除了伊朗的其他国家也是）。肾交换是合法的。因此肾交换是没有金钱的机制设计的理想应用，而无论怎样的激励问题是相关的（而且确实有一些这样的问题）。猜测例如未来10年后，会不会有一个肾脏的金钱市场出现在任何西方国家是有趣的。（伊朗没有肾脏的等待名单。）

想法#1：使用最优交易循环算法

这一部分和下一部分会涉及Roth, Sonmez和Unver[1,2]的两篇相对早期的论文，这两篇论文对于一个激励相容的全国性肾交换会长成什么样产生了具有影响力的头脑风暴。在第一篇论文[1]中，主要涉及在作者与医生大量交谈之前的工作，主要是以上一讲中的最优交易循环算法作为起点。在它的最基本形式中，建立了房屋问题中的代理人-原始房屋对和肾交换问题中的患者-捐赠人对——一个代理人的原始房屋代表了患者不兼容的在世捐赠人。房屋问题假设了每个代理人对于房屋有一个总的排序；在肾交换中，可以很自然地根据捐赠人的肾能够被成功地移植给患者的估计概率对他们进行排序（基于血型、组织类型等）。

应用TTCA的目标是找到类似图2中的环，其中患者-捐赠人对如图1所示，每个患者指向另一个捐赠人作为他更喜欢的捐赠人。根据这个环重新分配捐赠人是之前确认过的希望看到的肾交换。更一般地，捐赠人被分配给患者使得每个人都变得尽可能地最好（在上一讲中讨论过的意义上）。

图2：最优交易循环算法的一个好的案例。

实际的肾交换在几个方面更加复杂。我们首先讨论TTCA途径可以容纳的一个扩展，然后是激发重新定义这个问题的两个挑战。除了不兼容的患者-捐赠人对，[1]中TTCA的扩展处理了没有在世捐赠人的患者（没有原始房屋的代理人）和已故的捐赠人（没有原始拥有者的房屋）。这种新算法根据TTCA中的环进行分配，也根据合适的链路进行。只要链路以合适的方式选择，算法仍然保持DSIC——因此没有患者（或患者的医生）能够通过谎报信息来增加成功移植的估计概率。这个扩展在之前的另一个领域中被大量使用：分配宿舍给学生，当存在在住者（已经有房间但想升级的学生），空的房间（例如，毕业了的学生的房间）和现在没有房间的学生（例如，新学生）的混合时[3]。

TTCA算法的下一个问题是肾交换中的交易破坏者：重新分配遵循的环可以任意长。举例而言，在TTCA的第一轮中，有可能对应于被偏爱的捐赠人的弧组成了一个患者-捐赠人对的汉密尔顿环（见图3）。

图3：最优交易循环算法的一个不好的案例。

为什么长环是问题？首先考虑一个长度为2的环（图2）。注意到这已经涉及到四场手术——两个用于取出捐赠人的肾，而另两个用来将它们植入到患者中。进一步地，这四个手术必须同时发生。原因是动机：在图1所示的例子中，如果给P1和D2的手术先发生，那么有D1会反悔他要把肾捐给P2的承诺的风险。一个问题是P1不公平地“免费”得到了一个肾，而更严重的是P2变得比以前更糟糕，并且由于他的捐赠人D2已经捐掉了肾，P2再也无法参与肾交换。由于这个风险，没有人愿意在肾交换中尝试非同时的手术。现在顺序的手术以另一种稍微不一样的方式进行。举例而言，有一些利他的在世捐赠人，尽管他们私下里不认识谁需要肾脏，他们也有兴趣捐出一个肾。一个利他的在世捐赠人可以成为重新分配的链路的起点。长达30的链也被实施过了[4]，而在这个尺度上手术必须是顺序的。尽管顺序手术的第一个问题（“免费”获得一个肾）在这个场景中还存在，但是更加严重的第二个问题（失去你自己的在世捐赠人）不可能在这种由利他的在世捐赠人开始的链路中发生。同时手术的约束——每一个手术需要各自的手术间、手术团队等等——激励我们将重新分配的环控制得越小越好。

我们关于TTCA途径的最后一个批评是将偏好建模成对于在世捐赠人集合的总的排序是过度的：从经验上讲，患者并不关心他们得到哪一个肾，只要他和他们是兼容的。因此对于捐赠人的二元偏好更合适。

想法#2：利用一个匹配算法

第二种途径[2]，由二元偏好和短的重新分配的环这两个目标所激发，是使用匹配(matchings)。回顾下一个无向图$(V,E)$的匹配是一个边的自己$F \subseteq E$使得$F$中没有两条边共享一个端点。

肾交换中的图包含一个顶点集$V$，对应不兼容的患者-捐赠人对（每一对对应一个顶点）。顶点(P1,D1)和(P2,D2)存在一条无向边当且仅当P1和D2是兼容的且P2和D1是兼容的。因此，图1中的例子对应了图4中最简单的无向图。我们定义这个图上匹配的最优解有最大的基数——也就是说，我们希望安排尽可能多的兼容的肾脏移植。通过约束这个图上匹配的可行集，我们限制为了成对的肾交换，因此如图1中那样“只”有4个同时的手术。最近，3条边的交换，对应于由3个患者-捐赠人对组成的有向环（D2与P1、D3与P2、D1与P3相互兼容），变得越来越常见。原因是3边交换从逻辑上是可行的，并且允许它们的话会大大增加可以被救下的患者的数量。从经验上看，4或更多对的交换并不会帮助匹配更多患者，因此它们通常不会被实施。

图4：应用一个匹配算法。

我们关于代理人的模型中，每个顶点$i$有一个邻近边的真的集合$E_i$，并且能够向机制上报任何子集$F_i \subseteq E_i$。提出的肾交换能够被患者以任何理由拒绝，因此一种实施谎报的方法是拒绝$E_i \setminus F_i$中的交换。一个患者关心的全部事情是与一个兼容的捐赠人匹配。我们的机制设计目标是计算一个最优解（例如，一个最大匹配）并满足DSIC，意味着对所有代理人，上报全部的边的集合是占优策略。

根据我们的设计目标，机制必须有如下形式：

(1) 从每个代理人$i$处收集一个上报$F_i$。

(2) 形成边的集合$E=\{(i,j):(i,j) \in F_i \cap F_j\}$。也就是说，当且仅当两边都同意交换时，加入边$(i,j)$。

(3) 返回图$G=(V,E)$的最大基数匹配，其中$V$是（已知的）患者-捐赠人对的集合。

机制还没有被完全制定，因为在第(3)步中最大匹配有多种选择。制定正确的平局决胜规则对于获取DSIC很重要。从两种意义上看图的最大匹配不是唯一的。首先，边的不同集合可以被用来匹配相同的顶点集，见图5。既然一个顶点并不关心它跟谁匹配，只要它被匹配上了，没有理由在匹配相同顶点集的不同匹配间进行区分。更重要的是，不同的最大基数匹配可以匹配不同的子集。举例而言，在图6所示的星图中，顶点1在每一个最大匹配中，但是只有一个辐上的顶点可以被选中。我们应该选哪一个返回呢？

图5：不同的匹配包含了相同的顶点集。

图6：不同的最大匹配会匹配上不同的顶点子集。

我们的解决方案是在机制开始时给顶点进行优先级排序。不失一般性地，假设顶点$1,2,\dots, n$是从高优先级到低优先级排序。这种方法的好处之一在于大部分医院已经依赖于类似的优先级方案来管理它们的患者。等待名单中的患者的优先级由很多因素决定，例如他在等待名单中等待的时间，找到一个兼容的肾的难度等等。然后，我们可以如下实施步骤(3):

• 令$M_0$代表$G$中最大匹配的集合。
• 对于$i=1,2,\dots,n$：
  • 令$Z_i$代表$M_{i-1}$中匹配了顶点$i$的匹配结果。
  • 如果$Z_i \ne \emptyset$，令$M_i = Z_i$。
  • 否则，令$M_i = M_{i-1}$。
• 返回$M_n$中的任一个匹配。

也就是说，在每一轮$i$中，我们寻找是否有一个最大匹配既保留了之前已有的匹配，同时又能匹配上$i$。如果是的话，那么我们把对$i$的匹配也加入到最后的匹配中。如果之前的匹配阻止了在一个最大基数匹配中匹配$i$，那么我们跳过$i$并移动到下一个顶点。通过对$i$的递推，$M_i$是$G$上最大匹配的非空子集。$M_n$中的每一个匹配结果都匹配上了相同的顶点集——使得$Z_i$非空的顶点$i$——因此，步骤(3c)中匹配的选择是不重要的。

定理1.1. 对于边集的每一种收集结果$\{E_i\}_{i=1}^{n}$和顶点的每一种排序，上面的优先级匹配机制满足DSIC；没有代理人能够通过上报$E_i$的一个严格子集$F_i$而不是$E_i$使得从不匹配变为匹配。

我们将证明留给你；见练习。热心的读者应该去读[2]中关于选取的最大匹配随着对节点的选取的优先级排序而变化的更深入的探索。有一个通过Gallai-Edmonds分解的非常干净的答案，而它是匹配理论中刻画无向图中最大基数匹配结构的优美结果。

前沿的挑战

现在的研究集中在医院级别的激励问题，而不是在个体的患者-捐赠人的级别上。这个改变有很好的解释，因为许多患者-捐赠人对是通过医院上报给全国性的肾交换，而不是通过他们自身。医院的目标（匹配尽可能多它的患者）和社会的目标（从整体上尽可能多的匹配患者）并不是完美一致的。关键的激励问题最好是通过例子解释。

例子1.2（完全上报的需要） 假设有两个医院，每一个有3个患者（图7）。边代表了互相兼容的患者-捐赠人对，正如上面的匹配机制所示。每一个医院都有一系列患者-捐赠人可以内部进行匹配，而不需要上报到全国性的交换。在这个例子中，我们肯定不希望医院“贪心”地执行这些内部匹配——如果$H_1$在内部匹配1和2，只上报3去交换，而$H_2$在内部匹配了5和6，只上报4去交换，那么3和4不会被匹配，从而没有更多的匹配。作为对比，如果$H_1$和$H_2$都上报了他们的全部3对患者-捐赠人对给全国性的交换，那么1,2,3可以分别与4,5,6匹配，从而所有患者都得到了匹配。一般而言，目标是激励医院上报他们所有的患者-捐赠人对从而尽可能多地挽救生命。

图7：医院的完全上报能够比内部匹配得到更多的匹配结果。

例子1.3再次考虑两个医院，但是这次有7个患者（图8）。观察到，由于结点的数目为奇数，每一个匹配都会使得至少一个患者没有匹配。然而，如果$H_1$将患者2和3从交换中隐瞒起来（然而$H_2$真实上报），那么$H_1$保证了它的所有患者得到了匹配。上报了的图中唯一的最大匹配是匹配6和7（以及4和5）。同时$H_1$可以在内部匹配2和3。另一方面，如果$H_2$隐瞒了患者5和6而$H_1$真实上报，那么$H_2$的所有患者得到了匹配。在这种情况下，上报了的图中唯一的最大匹配是1和2及4和3，而$H_2$可以在内部匹配患者5和6。

要点在于社会与医院动机之间存在不可协调的矛盾：不可能存在一个DSIC机制可以一直在整张图上计算最大基数匹配。

医院有动机隐瞒患者-捐赠人对。

受例子1.3启发，修改的目标应该是计算一个近似最大基数匹配使得对于每一个参与的医院，它被匹配的患者的数量跟任意匹配、最大基数或其他情况，近似上一样大。想要理解这种扩展在多大程度上是可能的，无论是理论上还是实践中，都是一个活跃的研究话题[5,6]。

稳定匹配

稳定匹配是没有金钱的机制设计的经典例子。杀手级应用包括将医学院毕业生分配给医院以及学生给小学。接下来的模型和算法可以直接被用于这些和其他应用，只需要令人惊叹的一点点修改。

我们考虑两个集合$U$和$V$——“男士”和“女士”——每一个集合有$n$个结点。每一个集合对另一个集合的结点有一个完全的排序。例如，在图9中，男士对女士的排序完全一样，而女士对男士有非常不同的意见。

图9：一个稳定匹配的实例。

定义2.1 一个稳定匹配(stable matching)是一个完美的二部图匹配——也就是说，每一个结点都与另一个集合中的刚好一个结点匹配——使得没有“阻塞对(blocking pair)”，意味着：

(*) 如果$u \in U, v \in V$ 没有匹配在一起，那么要么$u$比起$v$更喜欢他在匹配中的配偶$v^\prime$或$v$比起$u$更喜欢她在匹配中的配偶$u^\prime$。

一个不满足条件()的完美匹配会有问题，因为阻塞对$u$和$v$会试图一起从匹配中逃走。这跟上一讲中在房屋分配问题中提到的核心分配的概念有一个清晰的相似性。如果一个匹配是不稳定的，那么它不在核心中——违背条件()的那一对$u,v$会通过从机制中退出获得更好的结果。不难证明核心分配——没有结点的子集可以退出并做得更好的匹配——正是稳定匹配。

我们接下来回讨论计算稳定婚姻的求婚算法。Gale和Shapley[7]正式定义了稳定匹配问题并给出了这个算法。令人不可思议的是，后来发现这正是1950年代以来在分配医护人员给医院的过程中使用的相同算法（今天也是这样）[8]!

求婚算法：

• 当存在一个没有匹配上的男人$u \in U$：
  • $u$向还没有拒绝过他的最喜欢的女士求婚。
  • 每一位女士只保留到目前为止她得到的最好请求（从她的角度）。

例子2.2 考虑图9中的实例。假设在第一轮中我们选择了男士C，他试探性地向他的第一选择D求婚。女士D接受了，因为她现在没有其他请求。如果我们在下一轮中选择了B，他也会向女士D求婚。因为女士D更喜欢B而不是C，她拒掉C而选择B。如果我们下一轮选择A，结果是类似的：D拒掉B而选择A。算法剩下部分的一种可能轨迹是：男士C现在向他的第二选择E求婚，B也会向E求婚，于是E拒掉C选择了B；最终，C向他最后的选择F求婚，而F也会接受他。

有一些关于这个算法和它的性质的评论。首先，它是非确定的，没有指明如何选择没有匹配上的男士。其次，注意到每位男士都是有系统地遍历他的偏好列表，从最高到最低。然后，一位女士的已经订婚了的男士在算法的过程中只会提高。第四点，算法保持了每位男士只会匹配给最多一位女士以及每位女士最多只会匹配给一位男士的不变性。

稳定匹配和求婚算法有一系列令人惊叹的优雅性质。我们从最基本的性质开始。

定理2.1 (稳定匹配的计算量). 求婚算法最多在$n^2$次迭代后终止并输出一个稳定匹配。

推论2.1 (稳定匹配的存在性). 对于男士和女士的每一种可能的偏好列表，存在至少一个稳定匹配。

我们强调推论2.1事前并不明显。实际上，稳定匹配问题的一些简单变形中解并不保证存在。

定理2.1的证明： 迭代次数的界限很容易证明。既然每位男士顺着自己的偏好列表进行求婚，永远不会向相同的女士求婚两次，因此他至多进行$n$次求婚。这也就产生了至多$n^2$次求婚（从而也限制了迭代次数）。

接下来，我们声称求婚算法总是以一个完美匹配终止。因为如果不是的话，某位男士一定已经被所有$n$个女士拒绝过。一位男士只会因为女士匹配上了更好的男士才会被拒绝。而且，一旦一位女士匹配上了男士，她在算法的剩余步骤中总是保持被匹配的状态。因此，所有的$n$位女士在算法结束时必须都被匹配了。但是这样的话应该所有$n$位男士也应该在算法结束时都被匹配，这就产生了一个矛盾。

最后，我们声称计算出的完美匹配是稳定的。想要看出来为什么，考虑没有匹配在一起的一位男士$u \in U$和一位女士$v \in V$。这种情况的发生可能有两个原因。第一种原因中，$u$从来没有向$v$求过婚。因为$u$是从顶部开始顺着他的列表求婚，这意味着$u$最终匹配上了一位他认为比$v$更好的女士。如果$u$确实在算法的某一个时间点上向$v$求过婚，那么肯定是$v$由于某位她更喜欢的男士而拒绝了$u$（无论是在$u$求婚时，或之后）。既然$v$匹配上的男士的队列在算法的流程中只会提高，她最终会匹配上一个比起$u$更喜欢的某位男士。#

我们在之前评论道求婚算法并没有指明在一次迭代中要如何从没有匹配的男士中进行选择。所有可能的选择会导致相同的稳定匹配吗？在图9中只有一个稳定匹配，因此在那个例子中答案是肯定的。然而，一般来说，可能会有不止一个稳定匹配。在图10中，男士和女士对于其他人的排序都不相同。在求婚算法计算出的匹配中，两位男士都得到了他们的第一选择，其中A和B分别匹配上了C和D。给女人她们的第一选择又会产生另一个稳定匹配。

图10：有多个稳定匹配的例子。

我们证明一个更强的结论来解决求婚算法的输出是否唯一的问题。对于一位男士$u \in U$，令$h(u)$代表在任意一个稳定匹配中$u$被匹配上的排名最高的女士（在$u$的偏好列表中）。

定理2.2 (男性最优的稳定匹配). 求婚算法计算出的稳定匹配将每位男士$u \in U$和对应的$h(u)$匹配在一起。

定理2.2立刻表明求婚算法的输出与每一轮中选择哪一位没有被匹配上的男士无关。它也暗示了存在一个“男性最优”的稳定匹配——每位男士同时得到他的“最好情况”的稳定匹配——没有必要在不同的男士之间进行权衡。一个前提是，没有理由去指望$h(u)$之间互不相同，从而能直接推导出一个完美匹配。

定理2.2的证明：令$R = \{(u,v)\}$代表在求婚算法的一个固定执行中$v$在某个时间点拒绝过$u$的那些对。

既然每位男士有系统地沿着他的偏好列表求婚，如果$u$在算法结束时匹配上了$v$，那么对于$u$比起$v$更喜欢的$v^\prime$有$(u, v^\prime) \in R$。因此，下面的声明会证明定理：对每一个$(u,v) \in R$，没有稳定的匹配将$u$和$v$匹配在一起。

我们通过对求婚算法的迭代进行归纳来证明这个声明。一开始，$R = \emptyset$，没有什么要证明。对于归纳的那一步，考虑求婚算法的某一次迭代，其中$v$拒绝了$u$而选择了$u^\prime$——因此$u, u^\prime$中的一个在这一轮中向$v$求过婚。

既然$u^\prime$系统地遵循他的偏好列表，对于每个$u^\prime$比起$v$更喜欢的$v^\prime$，都有$(u^\prime, v^\prime)$已经在当前拒绝掉的求婚集合$R$里。根据归纳假设，没有一个稳定的匹配可以将$u^\prime$和他比起$v$更喜欢的女士匹配在一起——在每一个稳定匹配中，$u^\prime$与$v$或一个更不喜欢的女士匹配。因为$v^\prime$比起$u$更喜欢$u^\prime$，并且$u^\prime$比起他可能在一个稳定匹配中匹配上的某人更喜欢$v$。因此，没有稳定匹配能够将$u$和$v$匹配在一起（否则，$u^\prime$，$v$会形成一个阻塞对）。#

可以发现求换算法从女士的角度而言产生了最坏可能的稳定匹配——算法将每个$v$与$v$在任意稳定匹配中匹配上的最低排名的男人$l(v) \in U$匹配在了一起。当然，你可以修改算法让女士进行求婚而男士进行拒绝，使得这两个性质刚好反过来。

假设结点的偏好列表是私人的——求婚算法满足DSIC吗？也就是说，一位男士或女士在谎报偏好的情况下会得到比真实上报偏好更好的配偶吗？正如计算出的稳定匹配的男性最优性质暗示的那样，求婚算法对于男士而言满足DSIC，但对于女士而言不满足。前一个性质并不容易证明（见问题集#3）而后一个可以通过简单的例子验证（见问题集#5）。

参考文献

[1] Alvin E Roth, Tayfun Sonmez, and M Utku Unver. Kidney exchange. The Quarterly Journal of Economics, pages 457-488, 2004.

[2] Alvin E Roth, Tayfun Sonmez, and M Utku Unver. Pairwise kidney exchange. Journal of Economic theory, 125(2):151-188, 2005.

[3] Atila Abdulkadiroglu and Tayfun Sonmez. House allocation with existing tenants. Journal of Economic Theory, 88(2):233-260, 1999.

[4] Kevin Sack. 60 lives, 30 kidneys, all linked. The New York Times, 18, 2012.

[5] Itai Ashlagi, Felix Fischer, Ian A Kash, and Ariel D Procaccia. Mix and match: A strategyproof mechanism for multi-hospital kidney exchange. Games and Economic Behavior, 2013.

[6] Panagiotis Toulis and David C Parkes. A random graph model of kidney exchanges: efficiency, individual-rationality and incentives. In Proceedings of the 12th ACM conference on Electronic commerce, pages 323-332. ACM, 2011.

[7] David Gale and Lloyd S Shapley. College admissions and the stability of marriage. American mathematical monthly, pages 9-15, 1962.

[8] Alvin E Roth. The evolution of the labor market for medical interns and residents: a case study in game theory. The Journal of Political Economy, pages 991-1016, 1984.