这个文中的算法,学界叫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个人的集合为:
player set