算法制胜，会心一击
2017-02-01
Optimal Stopping
如果你是一位美女，面容姣好，身材高挑，在京有房，工作体面，从容优雅，众人追慕。总之，就是婚恋市场的抢手货，你妈妈肯定不需要去朝阳公园为你摆地摊。那么，你会如何选择自己的结婚对象呢？是和初恋走入婚姻殿堂？还是等着骑白马的王子直到剩龄？是听从某个早晨冥想之后脑海里蹦出来那个名字？还是遵从你姥姥托梦为你指定的孙婿？
这些做法都各有特色，但本质上是一样的：它们都是某种形式的随机挑选。如果这辈子可能遇到十位追求者，那么以上方法选到最优结婚对象的概率都是十分之一。
数学家已经对这个问题，或者这类问题做了充分的研究，他们把这类问题命名为 Optimal Stopping。这类问题除了寻找爱人，还包括求职，买房，卖房，停车等。可以说人生充满了这类问题。这类问题当然有共同的特点：它们都关注在何时执行某个动作。婚恋中，这个动作是求婚，或者接受求婚。房屋交易中，这个动作是接受报价。在动作做出之后，结果就已经确定了。现实生活中也许无法，或者难以验证这个结果是否是最优的。但我们知道结果的好与坏，只由你做出动作的时机所决定。
这像极了，游戏中关键时刻的“会心一击”。那么，在现实生活中，何时使出这“会心一击”呢？算法给出了部分答案。
The Secretary Problem
最早出现被具体定义的 Optimal Stopping 问题是秘书问题：在一定数目的候选人中选择最好的秘书。他们一个接一个来面试，在每次面试结束时就要决定是否录用面试者，任何时候都无法反悔之前的决定。
这是 Optimal Stopping 问题的最简模型。对这个问题的答案是37%。策略是“Look-Then-Leap”：对前37%的候选者只观察不录取，在37%之后，遇到比之前候选者都优秀的人就录取他。这个算法能保证录取到最优秘书的概率为37%。有趣的是，这个概率和 Look 和 Leap 的分界线37%形成了对称。另一个有趣的点是，这个算法能保证，即使有海量候选者，录取到最优候选者的概率仍然为37%。如果，有一千名候选者，随机选择录取到最优的概率是0.1%，而 Look-Then-Leap 算法是对抗海量候选的最佳武器，因为它保证了你无论如何都有多于三分之一的概率得到最佳解。
所以，越是追求者甚众的人，就越应该了解这个算法。
所以，和大学的男女朋友分手未尝不是件好事。因为从算法的最优解来看，这阶段的恋爱关系其实都应该用于试手。他/她们只是你用于建立未来婚恋对象评价标准的样本而已。
Lover’s Leap
现实生活中，男性寻找婚姻伴侣是一个和 The Secretary Problem 类似的问题。但在婚姻伴侣模型中，有两点不一样：
- 求婚是有可能被拒绝的；
- 某些条件下，可以回头找前任。
在求婚可以被拒绝的条件下，找到最佳伴侣的策略有所改变。假设每个恋人拒绝和接受求婚的概率都是50%。这种情况下，就需要早一点结束观察期。不是经过37%，而是25%就跳入选择期。这个策略下，找到最佳伴侣的概率是25%。有趣的是，25%的观察期和成功概率25%，仍然是一组对称。
这里可以详细点，为还没有跳入婚姻的朋友提供更详细的指导：37%或25%可以是候选者的数量，也可以是寻找时间。这个模型下，使用时间会容易一些。如果，你进大学18岁开始谈恋爱，并打算40岁之前结婚。那么，作为女神，37%的观察期是26.14岁。这和一般认为的女性最佳婚姻年龄很一致；如果，你是平凡的男子，有一半的概率被拒绝，25%的观察期是指23.5岁。很遗憾，由于条件所限，你无忧无虑的时间比女神要短，你需要早几年进入为幸福婚姻努力的艰难时期。
如果，可以回头找前任，当然前任也不可能无限等待你。那么让我们假设，立刻求婚100%被接受，吃回头草的求婚有50%的可能性被拒绝。这种情况下的策略是：观察更多候选人，在61%的时间之后才跳入选择期。剩下的39%的时间内，如果出现了比观察期优秀的候选人，就求婚；如果尝试了所有的候选人，仍然没有下决定，就吃回头草，向所有候选者中最优秀者求婚。这时你有50%的概率被前任拒绝。但是，整个算法的整体成功概率是61%。有趣的是，这仍然和观察期61%形成了对称。
所以，如果你的条件较差，很容易被拒绝，就应该早一点求婚，多求几次婚；如果你条件很好，有超多备胎，而且备胎们都相当坚定，那就可以放心多看看，实在运气不好，在备胎里挑一个也是不错的选择。
Full Information
全面的信息是指，我们在判断时有一个标准，可以得知对象在全部样本中的位置。在典型秘书问题中，我们只能知道面试者在候选者池中的相对位置。如果，我们要找一位英语翻译，我们要求候选人提供托福成绩，并以托福成绩作为判断其是否是最佳的唯一标准。那么，我们每面试一位候选者，都知道她在所有托福考试者中的位置。如果她的托福成绩超过了80分，我们不看其他人的成绩，就能知道她还不错；如果超过了100分，那她就相当优秀了，无论何时遇见她，你都有很大概率应该录取她。
由于拥有了全面信息，我们可以省略 Look-Then-Leap 中的 Look 阶段。Look 本质就是牺牲掉一定数量的候选者，以建立选择标准。如果，这种标准已经存在，策略就可以转为 Threshold Rule：候选者位于高于某个比例的位置，就马上录取他。这个位置随候选池里的候选者数量而变化。如果候选池很大，那么门槛就应该高，如果候选池小，门槛就应该低。这个门槛可以被精确定义：如果候选池中还有两名候选者，那么倒数第二名候选者位于前50%的位置，才应该录取他；如果还有三名候选者，录取门槛就变为67%；如果，还有100名候选者，那录取门槛就变为99%。
这个方法最终录取到最佳候选者的概率是58%，大于经典秘书问题的37%。所以，对于雇主，对于选择者而言，拥有全面信息将带来更大的优势。
我们在进入恋爱的年龄时，都已经有了一些人生经验，比如看过一些爱情电影。我们其实已经一定程度上知道什么是最佳伴侣了。当然，电影通常比较艺术，平凡的我们通常无法企及。但明星们为我们树立了最佳标准，我们在此基础上，根据自身情况打一些折扣就可以形成适合自己的标准了。
所以，无论何时，遇到一个邻家版林志玲时，你都无需考虑任何算法问题了。
When to Sell
卖房也是一个 Optimal Stopping 问题。这个问题的最优解，取决于对房屋的估价范围，以及等待成本。
通常物业的价格是可以被评估的。例如，我们认为北京北四环亚运村一套100平两居价格为750万到800万。如果，我们的等待成本是10万。这个成本可能是物业费，房屋的维护费，更多情况下是我们得到房款后的机会成本。业主急售的房子价格可以更低的原因也是他的等待成本很高。那么策略是这样：第一份报价如果低于790万，业主就不应该接受；第二份报价如果低于780万，业主就应该继续等待。直到符合条件的报价出现。
当然，在北京，有些情况很诡异，市场很疯狂时的等待成本是负的。也就是，第二报价应该高于第一份报价，业主才应该接受。
这种策略通常难以得到执行。因为，拒绝早期的好报价，对业主而言通常很困难。特别是随之而来的报价都不是特别好的时候。是艰难地遵循算法，还是让自己的心里好受一些？这通常也是一个两难的选择。
When to Park
停车问题并不是一个简单的资源供给问题。如果能更深刻地将其理解为一个 Optimal Stopping 问题，将有助于解决北京的停车难问题。
寻找停车位的问题可以简化为这样一个模型：我们在一条路上向前驶向目的地，无法回头。路两旁有停车位，我们需要找到离目的地最近的空车位，以使我们步行距离最短。这其实就是一个 Optimal Stopping 问题。途中我们每遇到的一个空车位，都需要考虑一下是否停车。当然，直觉的做法其实也是 Look-Then-Leap 策略：在离目的地很远的地方我们不会认证考虑停车。直到离目的地足够近了，我们才会越来越认真地考虑是否应该停车了。那么，何时开始认真考虑停车呢？最优解符合直觉，这取决于目的地的空车位比例。如果目的地空车位比率低，那么离目的地很远的地方就应该考虑停车了。如果目的地空车位比率很高，那么我们可以在离目的地近一些地方才考虑停车。
算法显示，越多的空车位，生活会变得更美好了。这某种程度上提醒了公共政策制定者，停车问题并不是简单地使停车位被最大程度的被利用。停车是一个过程，它需要消耗注意力，时间，燃油，会制造污染和阻塞。免费的车位，通常是巨大刺激。人们争相前来停车，这使得这片区域一直处于无车位状态。前来停车的人通常要巡航很久才能找到车位。这消耗了燃油，造成了污染，道路也变得更拥堵。正确的方法应该通盘考虑所有这些问题。所以，也许有些违反直觉，在拥挤的中心城区出现空车位可能会是一个好信号。
When to Quit
《绝命毒师》是一部我挺喜欢的美剧。老白的故事从头到尾都是一个 Optimal Stopping 问题。我们看到故事的开头时，就知道这会是一个悲剧。人生有很多这样的情况：知道这是一条不归路，为何却仍然会执著地走下去呢？
看了这个模型，也许我们会对此有更深刻的理解：有一张赌大小的赌桌，每次你都需要 All in。如果赢了，你将获得三倍返还；如果输了，你将输掉所有的钱。第一次下注1元：赢，得3元；输，剩0元。那么你可以期望第一局之后，你的口袋里在平均概率上会有1.5元。第二次下注3元：赢，得9元；输，剩0元。那么你可以期望第二局之后，你的口袋里平均会有4.5元。如此计算下去，概率上你口袋里的钱是一直增长的。数学告诉你应该永远玩下去。但我们都知道，总有一天你会输得一无所有。
这其实就是老白的悲剧。有些问题，避免其实比试图解决它更好。
How to Live By
当然，我们的生活纷繁复杂，人们对幸福的定义千差万别。算法并不可能考虑到生活的各种困境，不可能考虑到人的各种心理。但算法能提供一些普遍意义上的指导。比如，你可能不会，或者无法完全按 Optimal Stopping 的算法来寻找伴侣。但算法告诉你，最优的选择通常需要你在耐心寻找和坚定选择之间达成微妙平衡。算法也告诉了你一些追寻幸福婚姻的大原则：年轻时应该多尝试，遇到爱情不要回避，勇敢拥抱爱情的美好。如果遇人不淑，就应当机立断地离开，勇敢往前走；年龄大了就应该慎重，遇到合适的伴侣就应该坚定走入婚姻。
我见过相恋十年，和初恋走入婚姻的朋友，婚后也简单温馨，幸福快乐；我也见过浪子回头，年轻时放荡四方，年纪大了遇到了平淡的女孩，千山万水之后的恬静平和也是一种幸福。人们对于幸福和美好都有自己的感受。算法很难定义每个人的幸福。每个人都有自己的节奏，在人生每个阶段情感的需求也并不相同。这些算法也难以抽象。
所以，确实没有必要机械地遵循算法。理解算法的精神，在大方向上指导人生，这已经大幅度提高你得到幸福的机会了。但如果遇到命中注定的时刻，你就是被击中了，已经无法用理性判断眼前这个人是否就是你一生的伴侣。这时，这一刻否是最优解已经不再重要。因为，人生这种时刻并不多，遇到这一刻本身已是一种幸运。那么，就无需恐惧，勇敢面对，遵循内心，会心一击。
后记
这篇文章其实是《Algorithms to Live By》的读书笔记。这是第一篇，我希望能多写几篇。我喜欢这本书，希望能认真读完。笔记都是自己的理解，如有谬误，还请指正。