三、AER(2007)
既然肾脏交换的轮换大小有了限定，那么这个限定到底是多少就是一门学问了，大了太复杂，小了又会有很多的轮换不能进行，所以AER(2007)这篇文章就考察了，如果我们允许轮换中的人数最多是2人、3人或4人，分别能够解决多少患者呢？
首先，我们需要进一步剖析这个肾脏交换市场。上面我们已经提到，所谓的肾脏不适合，主要就是血型不适合和组织不适合，由于总共有四种血型（这里就先不考虑RH阴性的问题啦），“患者-捐献者”的组合一共就有16种。把这16种组合分成四组来考虑：
I. 血型一致： A-A B-B O-O AB-AB
II. 只看血型，捐献者可以给患者献血的：A-O B-O AB-O AB-A AB-B
III. 只看血型，患者可以给捐献者献血的：O-A O-B O-AB A-AB B-AB
IV. 相互都不能献血的：A-B B-A
前两组是血型适合的，这样的“患者-捐献者”组合进入市场，只能是因为组织不适合，而后两组则是血型不适合的。我们对比一下第二组和第三组，显然A-O和O-A从概率上来说应该是同一数量级的，但是由于A-O只有组织不适合的进入了市场，所以市场上的A-O组合一定远远少于O-A组合；其它的对应组合也是同理。
现在我们来做一些方便我们继续下一步的假设：
假设0：所有市场上的“患者-捐献者”组合，捐献者都不能把肾脏直接给患者，或是由于血型不适合，或是由于组织不适合。
之所以是假设0，因为这是市场的隐含前提，所以这篇论文并没有把这个列在自己的假设当中……
假设1：（大市场假设）任意一个患者和除了自己的捐献者之外的捐献者都没有组织不适合的问题。
因为市场足够大，我们可以假定每个患者总能在任意一个血型中找到充分多个和自己组织适合的捐献者，写成假设1这样只是进一步的简化了而已。
假设2：（长期假设）对于第三组的任意一个组合，经过配对之后一定都会剩下至少一对。
很容易验证，第三组的“患者-捐献者”组合想要进入轮换，一定会消耗掉一个第二组的组合，而第二组的组合本身是血型适合的，只有组织不适合的时候才会进入市场，因此第二组的数量远比第三组的数量要少，长期来看，最后第三组的组合一定都会剩下来。
假设3：统计数据显示市场上A-B的组合数比B-A的组合数更多。
这就是统计数据，没说的……
好了，接下来我们要做的就是血型连连看：
1) 当最多只能进行2个组合对换时，显然的，每个第二组的组合可以解救一个第三组的组合，最后第二组全部用完，剩下第三组的。
对于任意第一组的组合X-X，如果和Y-Z进行对换，则从血型上来说，Z能给X输血，X能给Y输血，故Z能给Y输血，即Y-Z是血型适合的，要么是第一组内部解决，要么Y-Z是第二组的。如果是前者，每次匹配掉两个X-X；如果是后者，X-X每消耗一个第二组的组合，相应的第三组就少一个组合被解决，这是一换一，没有意义。所以第一组的每个组合都选择内部两两配对，最后有落单的就落单。
对于任意第三组的组合X-Y，如果和Z-W进行对换，W能给X输血，X能给Y输血，Y能够Z输血，所以W能给Z输血，但显然W和Z是不同的（否则X和Y就相同了），所以能解决第三组的一定只有第二组，在消耗完第二组的之后，第三组剩下的都不能解决。
对于任意第四组的组合，不妨假定是A-B，要么就用B-A解决，要么就用第二组的B-O，AB-A或者AB-O解决，显然后者还是一换一，没有意义，所以所有的A-B和B-A内部组合解决掉，两个组合哪个多就剩哪个，根据假设3，A-B就会剩下来。
所以当最多只能进行2个组合对换时，解决掉的组合数是：
N2=2*N(II)+2*N(B-A)+2*([N(A-A)/2]+[N(B-B)/2]+[N(O-O)/2]+[N(AB-AB)/2])
后面括号里的是下取整。
简单的解释一下，每个第二组的组合解决了两个组合，A-B和B-A中较少的那个（B-A）每次解决了两个组合，而第一组每种组合都内部解决了所有成对的。
2) 当最多只能进行3个组合轮换时，我们来看看，多出了哪些新选择：
首先，所有的X-X组合可以被塞进任意的对换中去了，所以X-X不会再有落单的组合了。
其次，AB-O这个组合可以通过和O-A A-AB或者O-B B-AB组成轮换，一次性解救两个第三组组合
第三，多出来的A-B组合，可以构成A-B B-O O-A或者A-B B-AB AB-A这样的轮换，从而被解救。
因此，此时能够解决的组合数变为：
N3=2*N(II)+2*N(B-A)+N(I)+N(AB-O)+min{N(A-B)-N(B-A),N(B-O)+N(AB-A)}
还是解释一下，首先每个第二组的组合至少解决了两个组合，但AB-O还能多解决一个第三组的组合；B-A每次解决两个组合没有变；第一组所有的组合都解决了，不用考虑落单了；最后，多出来的A-B可以加塞到B-O和AB-A的队伍中，就看是加塞的和被加塞的哪个更少一点了。
做个减法，我们有
N3-N2=k+N(AB-O)+min{N(A-B)-N(B-A),N(B-O)+N(AB-A)}
这里面的k就是第一组中落单的数量，最小是0最大是4。
3) 当最多只能进行4个组合轮换时，新增加的选择是，A-B可以构成A-B B-AB AB-O O-A这样的轮换，所以A-B可以靠加塞进AB-O来解救了，其它所有组合都没有新增成员。
N4=2*N(II)+2*N(B-A)+N(I)+N(AB-O)+min{N(A-B)-N(B-A),N(B-O)+N(AB-A)+N(AB-O)}
所以
N4-N3<=N(AB-O)
可以看出，N4-N3显然小于N3-N2，从成本收益的角度考虑，选择最多允许3个组合进行轮换应当是最佳选择。模拟的结果也是如此，人口总数为100的模拟中，只能两人对换时，解救的患者期望为49.708人，允许三人轮换上升到59.714人，允许四人轮换上升到60.354人，而不加限定的结果是60.39人，从两人到三人提高了10个百分点，而三人到四人只提高了0.6个百分点。
这里留一个小问题，为什么我们只考虑到四人就结束了？是因为我们发现三人到四人的提升空间已经很小了，后面越来越小不用考虑？还是因为之前说的现实情况限定了最多只能同时进行八台手术进行私人兑换？抑或是作者其实先做了模拟实验发现四人轮换的结果已经和没有限定很接近了所以就只讨论到四人？这个问题我们留到下一讲介绍肝脏交换市场的时候一并来解决。
（2015.07.03 @ 微信公众号 @ 《第五讲：Kidney Exchange 肾脏交换（二）》）
