发帖
雷达卡
这个文中的算法，学界叫Deferred Acceptance(DA)算法，也叫Gale-Shapley算法。
首次出现在配对问题（matching problem）的奠基性论文里面。具体可以参考原文：
Gale, David and Lloyd S Shapley. "College Admissions and the Stability of Marriage." American Mathematical Monthly, (1962): 9-15.
看完版主的文章，随即想起配对问题当中的另外一个重要算法概念——Top trading cycle(TTC)算法。
TTC算法在国内的叫法还不太明确。有翻译成“首位交易循环”的。
这个算法首次出现在Shapley & Scarf(1974)一文当中。但两位作者当初在这个文章讨论的是房子交换问题（housingproblem），且两位作者论证的是在房子交换问题中总存在核（core）。而David Gale提了个简单的算法，而这个算法是属于核的。这个算法就是Top Tradingcycle算法。所以，也叫Gale's Top Trading Cycle algorithm。所以，如果Gale再多活四年，2012年的诺贝尔奖头一个人肯定是他了！
Shapley, Lloyd and Herbert Scarf. "On Cores and Indivisibility." Journal of mathematical economics 1, no. 1 (1974):23-37.
但这个TTC算法与上面的DA算法在应用上是有些微区分的。比如，DA算法更多用于two-sided配对问题，如上面的男女配对问题，以及劳动力市场里的企业和劳动者之间的配对，还有学生和学校之间的择校问题等等。而TTC算法更多应用于one-sided配对问题，也就是不可分割商品（indivisible good）的分配和交换问题，比如房屋分配问题。宿舍分配问题，器官移植问题，排课等等。
下面我们用房屋分配问题的一个例子来了解一下TTC算法是如何进行的。
（案例取自《SocialEconomics: A Brief Introduction to the Handbook》书里的第17章里，有兴趣的读者可以下载看看这本书。本书论坛里面有handbook of social economics vol1正式版）
假设，有16个人，每个人各自持有一栋房子。这16个人的集合为：
相对应的，每个人自己持有的房子为h1,h2,h3….来表示。
每个人对所有的房子都有自己的偏好顺序（包括自己的房子在内）
（从上至下偏好依次降低）
算法过程：
步骤1：每个人用箭头指向自己最喜欢的房子，房子则指向房屋主人。在这个图当中，必定至少存在一个循环（cycle），且没有任何两个循环会相交。在每个循环中，哪个人指向哪个房子，就把这个房子分配给指向这个房屋的人。
。。。
步骤k：在剩下的人当中，每个人用箭头指向剩下的房屋当中自己最喜欢的房屋，而房屋则依然指向房屋主人（注意，每一个步骤中房屋随着主人离场，且主人也是随着房屋离场，所以下一步骤中房屋留下来了，则主人必定也留下来，反之亦然）。同样，这个步骤中必定存在至少一个循环。把房屋分配给指向这个房屋的人之后，把所有循环去掉。
这些步骤一直进行到所有人和房屋分配完为止。
把上面的案例用图来解释这个算法过程。
步骤一：
步骤二：
步骤三：
步骤四：
步骤五：
这样，最后每个人分配得到的房屋结果为：
提升卡
置顶卡
沉默卡
变色卡
抢沙发
千斤顶
显身卡
京公网安备 11010802022788号
