现在我们回归一下现实，由于我的禀赋只有房子没有钱，我只能靠卖了自己的房子得到的钱去买新房子，所以新房子价格最多和我持有的房子一样贵；另一方面，在所有我买的起的房子中，新房子必须是我最喜欢的房子，否则我完全可以去买更喜欢的房子。假定我们找到了核中的一个匹配，然后又找到了一个对应的价格安排（这个价格安排也叫做Competitive Price）满足上述要求，这就称为Walrasian Equilibrium（瓦尔拉斯均衡……？感觉很少看见这个译名的说……），学过公财的同学可能在福利经济学第一定理中看到过这个名字，这个均衡的经济学意义是，在一定的价格安排下，每个人最大化自己福利的决策恰好使市场出清。Shapley & Scarf在1974年的论文中证明了，每个房屋市场都存在Walrasian Equilibrium，其中的匹配就是上面提到的TTC给出的匹配，而价格是如下决定的：第一轮的所有房子价格定为N-1，第二轮定为N-2，依此类推。
自然而然的一个问题就是，这样的均衡是唯一的吗？从价格的角度讲，实际上只要每一轮的房子价格比后一轮更贵就可以了，甚至如果在一轮中存在多个Top Trading Cycle，因而分成了几轮才都安排完，这些Cycle中的房子其实都可以定为相同的价格。但是说来说去，我们讨论的都是TTC给出的这个匹配，从匹配的角度来说，Walrasian Equilibrium是唯一的吗？
其实我这么问的时候大家应该已经猜出答案了，TTC其实是核中唯一的匹配，这个定理是由Roth和Postlewaite给出的。显然这个定理的一半已经证完了，TTC肯定是在核中的；要证的另一半就是，在核中的匹配一定是TTC，这个也很容易，如果核中还有不同于TTC的某个匹配，我们称它为新匹配，然后我们用核的定义来验证一下：首先，我们把在TTC中第一轮拿到房子的人拉出来组成一个联盟，因为他们在TTC中拿到的都是他们最喜欢的房子，如果新匹配不能给他们TTC中的房子，那么这个联盟的人总能通过互相交换禀赋的房子达到TTC然后better off，矛盾出现了，好吧，那么新匹配给这帮人的房子就得跟TTC一样；然后把这些人和他们的房子拿走，把TTC第二轮拿到房子的人拉出来，新匹配又得给他们和TTC一样的房子；然后再拿走，第三轮……依此类推，最后我们发现，新匹配每一轮给的房子都跟TTC一样，说好的不同于TTC的匹配呢！矛盾，好吧，核中除了TTC还是TTC，不可能有别的匹配了。
没想到TTC这个简单粗暴的算法竟然是这个问题的唯一解吧（此处应有“我伙惊”……），但是这么个简单粗暴法很难不让人想到我们的老朋友Boston Mechanism，而BM最大的问题之一就是，它不满足strategy-proof。但核中的独苗匹配TTC显然是身经百战，见得多了，所以TTC竟然满足strategy-proof也没有那么令人惊讶了吧……
再结合之前关于TTC是核中唯一匹配的结论，Ma(1994)”Strategy-Proofness and the Strict Core in a Market with Indivisibilities “给出了定理，即满足IR、帕累托最优和strategy-proof的匹配只有TTC给出的匹配。不过我感觉其实这只是个填坑的工作，因为TTC给出的匹配是唯一满足IR和帕累托最优的匹配之前已经证明过了，而TTC匹配满足strategy-proof是1982年Roth论文的结论，那我们已经知道满足IR和帕累托最优的只有TTC了，而TTC又满足strategy-proof，这个定理难道不是显然的嘛……
Roth的证明还是很赞的，我们来扒一扒，相关论文是Roth(1982)”Incentive compatibility in a market with indivisible goods”。
假定有一个人i打算谎报自己对房子的偏好，而且在他没有谎报的时候，他在第k轮拿到房子x，在他谎报的时候，他在第k’轮拿到房子x’。
如果k比k’要小或者k等于k’，那么在第k轮开始之前，x和x’都还在没拿走的房子里，这时候i最喜欢的房子就是x，谎报拿到的房子x’一不会比x更好（可以就是x），这时候他没有谎报的激励。
如果k比k’要大，那么在第k’轮的时候，说了谎的i一定处在某个Top Trading Cycle当中，他拿的房子x’原本的主人是j0，然后j0拿了j1，j1拿了j2，直到最后jn拿了i自己禀赋的房子。
那么如果i没有说谎，在进行到第k’轮的时候，这个Top Trading Cycle并不存在，只缺了最后一环也就是i拿了j0的房子。而在从第k’轮到第k-1轮的过程当中，j0有可能处在某个Top Trading Cycle当中，从而把房子x’给了别人吗？不可能，我们可以倒过来看，因为i还在市场上，所以jn最喜欢的房子一直在市场上，他肯定始终指着i，所以他肯定没有出现在某个Cycle里，否则i就会进入这个Cycle，从而在第k轮前就拿到房子，这和我们的假定矛盾；同理，jn-1也始终指着jn，所以他也没有出现在某个Cycle里，否则就又把i带进这个Cycle了，然后倒推回j0，他在第k轮之前，一定没有进入任何一个Cycle。
这意味着，如果i说谎了，他拿到了x’这套房子，而如果i没有说谎，在到了第k轮的时候，x’这套房子（以及它的主人j0）仍然留在市场上，这时候i选择了他最喜欢的房子x并得到了这套房子，显然x至少和x’一样好，所以i还是没有激励谎报。
所以无论如何，i都没有谎报的激励，也就证明了TTC是strategy-proof的。
（2015.06.26 @ 微信公众号 @ 《第四讲：Housing Market 房屋市场（下）》）
