在第二讲的时候提到了所谓的单边市场，也就是一边是人，一边是物的市场。这样的市场，最简单的例子莫过于房屋交易市场。
在这个市场上，每个进入市场的人都有自己的禀赋(endowment)，也就是一套房子（总不能让人在市场上交易不成功回去连住的地方都没有吧>_<），然后互相交易。每个人对市场上的所有房子有一个偏好，但是房子不会挑人，随便谁住都可以。
这时候，什么样的匹配是稳定的呢？因为房子不会挑人，也就等同于人对于房子来说是无差异(indifferent)的，而Pairwise Stability中的私奔需要双方都喜欢对方胜过现在的匹配对象，所以我们不能再用PS作为稳定的条件了。
但是，直观上，有一种显然的不稳定的情况：比如说现在有两套房子，一套在海边一套在山里，住在海边房子里的人喜欢爬山，住在山里房子里的人喜欢冲浪，双方对于对方的房子的评价都比自己的房子要高，假定两套房子其他方面都差不多，这时候让他们两个人交换，那么两个人都会得到更好的房子。当然，这个情况可以构造得更复杂，比如说一个城市里的三套房子，分别临近水果店、电玩城和游泳馆，结果房子的住户偏偏讨厌自己临近的这家店，水果店旁的住户喜欢打电玩，电玩城旁的住户喜欢游泳，游泳馆旁的住户喜欢吃水果，那好，三个人轮换一下，正好每个人都得到一个更好的房子。
我们把市场上的一部分人（以及他们的房子）捆绑在一起，称为联盟(Coalition)。在这个市场上的所有匹配中，存在有一种特殊的匹配，无论怎样选择联盟，这个联盟中的人都不能够通过互相交换自己的禀赋房子，使得至少一个人得到的房子比这种匹配给出的更好，这种匹配构成的集合被称为核(Core)。实际上，在双边市场上，所有的稳定匹配也构成了核：无论你选择哪些男生和女生，都不能够通过在他们内部重新匹配，使得每个人都得到更好的配偶。这些稳定匹配满足两个条件，分别是个体理性(Individual Rationality)和配对稳定(Pairwise Stability)。而在单边市场上，核中的匹配同样需要满足两个条件，分别是个体理性和帕累托最优(Pareto Efficient)，证明很简单就不再赘述啦。（或者也可以留作课后习题哈哈~）
那么有没有一种方便的办法，像DA那样，只要我们给出有哪些人，有哪些房子，每个人对于房子的偏好，就能够得到一个在核中的匹配呢？答案当然是有的，而这个算法是由DA的提出者之一Gale提出的（虽然1974年提出这个算法的论文是Shapley和Scarf写的），名为Top Trading Cycle Algorithm（中文大概是叫首位交易循环算法，不过好复杂啊还是叫TTC算法好了反正你们都懂得╮(╯▽╰)╭）。
顺便扒一句，其实在匹配理论这一块，Gale和Shapley这两个数学家（主要是数学家吧……像1962年介绍DA的论文和1974年介绍TTC的论文都是发在数学期刊上的）是最有资格拿诺奖的，但是直到20世纪90年代，诺奖才慢慢开始转向博弈论的领域，而稳定匹配理论的获奖一直等到了2012年，若不是Gale老先生于2008年仙逝，他一定有机会分享这份荣誉。Roth作为将匹配理论从数学领域打入经济学领域的第一人，获奖倒也算是实至名归。Shapley获奖并不奇怪，比较奇怪的反而是他并没有因为在合作博弈方面的贡献获奖（比如Shapley Value，这个应该是合作博弈耳熟能详的名词吧）。
TTC算法的流程非常简单粗暴：第一轮，每个人都指向自己最喜欢的那套房子，如果构成了一个圈（A指向B的房子，B指向C的房子，C指向D的房子，等等等等，最后一个人指向A的房子），那么这些人就换房子，然后这些人带着房子离开市场。
第二轮，所有还在市场上的人，都指向所有还在市场上的房子中最喜欢的那套房子，如果构成了一个圈，同样的，换房子，离开市场。
然后第三轮，第四轮，直到所有人都离开市场。
等下，好像刚才说的是……“如果”？如果不构成一个圈呢？
当然是一定可以构成圈的啦否则我还在这里说个什么鬼……证明如下：假设没有圈，任取一个人A，A不能指向自己，一定指另一个人B；B不能指A和自己，所以只能再指另一个人C；这样进行下去，最后所有人都被指到了，而最后那个人又不能指已经指过的人，否则就会有圈，出现矛盾，假设不成立。
算法论述完毕，再来看看这个算法的结果是不是在核中。假定我们划了一批人构成了联盟，首先看这个联盟当中那些在第一轮就拿到房子的人，显然他们拿到的是最喜欢的房子，不会选择和其他人换；然后是第二轮，他们没法和第一轮的人换（因为第一轮的人不愿意跟他们换），也不会和其他人换（因为拿到的是所有第一轮的人没拿的房子里最喜欢的房子）；然后是第三轮，第四轮，依此类推。结果是联盟中的人都不能通过换房子得到更好的房子。
（2015.06.23 @ 微信公众号 @ 《第四讲：Housing Market 房屋市场（上）》）
