数学帮你找到最佳伴侣

/ @峰哥何峰 /
1.
我们大概都经历过这种情况, 你对班上几位女生(或者男生) 有意思, 但是不知道他们是否对你有意. 让情况更复杂的是, 你对这些女孩子们的兴趣不是平等的. 如果可能, 你希望能够跟你首选的姑娘约会, 不行的话, 你希望能够约到排名第二的, 并以此类推. 使情况进一步复杂的是, 不光你对姑娘们感兴趣, 班上的其他男生也对姑娘们感兴趣, 但是你也不知道他们心中的排名.
如果你是一位善意的班主任, 希望帮孩子们解决这个配对的难题, 你应该怎么做呢? (提示: 一些数学算法的知识会对你有用.)
2.
配对自古就是人们热衷, 但又没有好的办法解决的难题. 随之应运而生的有月老, 红娘, 婚姻介绍所, 以及现在的婚恋网站, 电视相亲等. 这个难题凸显在婚恋市场, 但是不局限于此, 国外大学申请, 找工作等等众多的人类行为中都能遇到它.
这个难题甚至自成一个学术领域, 在经济学上隶属于 market design (市场设计) 的研究, 因为市场就是要把最合适的买家和卖家配对. 2012年获得诺贝尔经济学奖的美国经济学家 Alvin Roth 就专门研究这个领域[1]. 他不仅仅在学术研究上有建树, 更是把学术研究的成果付诸于实际应用. 他曾经改造了美国纽约市初中升高中的申请系统[2], 一年中, 使得没有被分配到学校的初中毕业生的数量下降了90%. 他所使用的, 就是 deferred acceptance algorithm (推迟接受算法). 这个算法是怎么工作的呢?
3.
我们还是以开篇的那个例子来说明. 传统的做法 (被称为 immediate acceptance, 即”立即接受法”), 是大家都去追自己最心仪的女生. 而这个女生面对几位追求者, 要立刻做个决定. 被拒绝的男生们调整一下心情, 再去追求心中的 No. 2. 以此类推. (当然, 这模型是非常简化了的.)
这样做法有一个严重的问题: 当你被你的No. 1 拒绝后, 再去追求你的 No. 2 的时候, 你心中的No.2 可能已经在第一轮中选择了其他人. 但坑爹的是, 有可能你正是你心中No.2 心中的No.1, 但是她并不知道. 所以她在第一轮中, 因为没有被你追求, 而屈就他人. 比及你在第一轮中表白失败, 再去找你的No.2 时, 已然晚矣.
形容的有点混乱哈. 我从新描述一下. 假设班上三男 (分别是A, B, C), 三女 (分别是x, y, z), 见下图:
                
                
他们心中对异性的排名见图二.
                
                
第一轮中, 男生们向心中的No. 1女示好, 即A, B 两男向心中最喜欢的x女示好, 而C男向y女示好.
                
                
如果采用immediate acceptance, 此轮之后的结果是, x-A, y-C 两对结成情侣. 注意, y 女虽然心中首选是B男, 但是由于B男在此轮中正在追逐x女, 无奈下y女屈就于唯一来献殷勤的C男. 比及第二轮开始时, 唯一还 available 的就是z女了.
                
                
最后的结果是 x-A, y-C, z-B 三对恋人. 注意: y女和B男两人都更愿意离开自己的现任伴侣而彼此在一起. 这种不稳定的状态就是很多文学影视作品的来源哈. 在数学上, 这也恰恰被称为是”不稳定”(unstable)的组合. 顾名思义, 我们希望能够有种算法, 给我们的结果是所有配对都是稳定的.
4.
作为班主任的你, 这时候就会想到(如果你学习了比如 Gale 和 Shapley 这篇刊登于1962年1月美国数学月刊的经典论文的话[3]), 你就会想到这是一个呼唤你采用 deferred acceptance algorithm 的课题. 你会让同学们这么做:
每个男生在第一轮中向自己心中的No. 1 示爱. 但是各位姑娘们不用立即决定(所以该方法名称中有”deferred”一词), 而是先hold 住了. 在第二轮中, 每个男生再向心中的 No. 2 示爱. 从第二轮开始, 每位姑娘们只保留自己到现在为止所收获的最心仪的男生(但是不用答应他, 只hold在心理), 而拒绝其他所有人. 而被拒绝的男生(也就是现在尚没有人hold着你的男生) 则继续在下一轮中向心中排名的下一个姑娘表白. 以此类推, 一轮轮继续下去, 直到所有想示爱的男生都示完为止. 此时, 每个手中有 offer 的姑娘, 可以选择接受.
以上就是 deferred acceptance algorithm 的做法. 大家算一下, 就会发现, 在我们这个简单的例子中, 最后的结果是 x-A, y-B, z-C 三组恋人终成眷侣. 而这是一个 stable 的结果. 所有6人中, 你不可能找到一男一女符合以下条件: 他们都更愿意抛弃已有的伴侣而与彼此在一起.
                
                
5.
Deferred acceptance algorithm 能够从数学上证明是一定会产生 stable 配对的算法. 这使它成为一个重要的工具, 因为这类的配对问题在现实生活中太常见了. 申请过美国大学的同学们都知道, 美国大学的申请和录取, 也是一个寻求最佳配对的问题. 不同的是, 婚恋中的配对是一对一, 而大学的录取是一对多 (可以用一个类似 deferred acceptance algorithm 的算法解决).
配对问题在医疗中也有应用. Roth 的一大贡献就是在美国建立了肾脏移植交换所 (kidney exchange). 他的算法使原来没有机会得到肾脏移植手术的病人能够有机会接受手术[4].
数学是个越学越觉得神奇的东西. 治病救人, 成人之美.
最后，给大家3道思考题，从易到难分别是：
1）deferred acceptance algorithm 是一定会结束的吗？换句话说，是否这个过程会无止境的进行下去？
2）如果所有配对都是稳定组合，我们把这结果叫做稳定结果。请问，稳定结果一定是唯一的么？（注：deferred acceptance algorithm 是一个 deterministic 算法，所以用这个结果演算出来的结果当然是唯一的。但是除此之外，是否有其他的，没有找到的稳定结果呢？）
3）在以 deferred acceptance algorithm 寻找恋人的过程中，是作为男生（即发offer的一方）好，还是女生（接受offer的一方）好呢？还是无所谓呢？（提示：如果对问题二的回答是“唯一的”，当然就无所谓了。）
(本文属于豆列 神奇的数学)
======
[1] Stanford visiting professor Alvin Roth wins Nobel Memorial Prize in Economics, Stanford News, Oct 15, 2012
http://news.stanford.edu/news/2012/october/nobel-economics-roth-101512.html
[2] The visible hand, Stanford Magazine, Jan/Feb. 2013
http://alumni.stanford.edu/get/page/magazine/article/?article_id=58692
[3] College Admissions and the Stability of Marriage, Gale & Shapley, The American Mathematical Monthly Vol 69, No. 1 (Jan., 1962), 9-15
[4] Algorithm meets altruism, Stanford Magazine, Jan/Feb. 2013
http://alumni.stanford.edu/get/page/magazine/article/?article_id=58809