原标题：最优停止理论：如何选择停止观望的时机？（文后留言送书）本文节选自《算法之美：指导工作与生活的算法》中信出版集团，2018年05月出版约翰尼斯·开普勒所有的基督徒都会在结婚请柬的最前面郑重宣布，他们走进婚姻的殿堂是遵从上帝的特别安排。但是，我要站在哲学的角度，详细地探讨这个问题......简·奥斯汀，《爱玛》如果你觉得马丁先生是最优秀的人选，如果你觉得与他相处最为融洽，那么你还犹豫什么呢?对于在中学时代就建立了恋爱关系的大一新生而言，感恩节就是一个严峻的考验:因为回家度过短短4天的假期之后，很多恋人就劳燕分飞了。大学辅导员把这个普遍现象称作“放弃火鸡”。大一新生布莱恩就面临着这个问题。他中学时的女友在另外一所大学，天各一方的两个人不仅需要解决空间距离造成的麻烦，还需要认真思考一个问题:他们两人之间的感情到底有多深?他们从来没有考虑过这个具有哲学深度的问题。由于没有类似的感情可以参考，他们无从回答这个问题。于是，焦虑不安的布莱恩找到辅导员，向她寻求帮助。辅导员知道这是新生经常遭遇的一个典型难题，所以她用一种极其冷淡的语气给出了自己的建议:“先收集一些数据吧。”显而易见，在连续性单配偶的生活方式中，人们不可避免地会遇到一个非常重要的问题:接触多少人之后，才可以确定自己的理想伴侣?如果在收集数据的过程中与自己的“真命天子”失之交臂，那该怎么办?这似乎成了感情问题上无解的“第22条军规”。我们知道，这个令大一新生忧心忡忡、牢骚满腹的“第22条军规”其实就是数学界的“最优停止问题”，它的答案其实很简单，就是37%。当然，前提条件是你愿意在爱情问题上做出各种假设。秘书问题在所有最优停止问题中，最大的难点不在于选择哪一种可选方案，而是确定自己需要考虑多少种可选方案。这些问题往往会引发不同的后果，不仅陷入爱河的人和需要租房的人必须慎重考虑，司机、房主、入室行窃者等也常常面临同样的抉择。“37%法则”源于所谓的“秘书问题”——最优停止问题中最著名的一类难题。秘书问题的情境与我们前面考虑过的租房难题十分相似。假设一堆人申请一个秘书岗位，而你是面试官，你的目标是从这堆申请人中遴选出最佳人选。你不知道如何给每一名申请人评分，但是可以轻松地判断哪一名申请人更加优秀。(用数学语言来表述，就是说你只能看到序数，即申请人相互比较的排名，但是无法看到基数，即在一般性评分标准下的得分。)你按照随机顺序，每次面试一名申请人。你随时可以决定将这份工作交给其中一人，而对方只能接受，于是面试工作就此结束。但是，一旦你否决其中一名申请人，就不能改变主意再回头选择他。普遍认为，秘书问题第一次出现在出版物中是在1960年2月，那一期的《科学美国人》杂志在马丁·伽德纳最喜欢的栏目——“趣味数学”专栏中刊登了几个难题，其中之一就是秘书问题，不过当时没有明确地提到“秘书”这个词。但是，这个问题到底从何而来，这是一个非常神秘的谜。除了一些推测以外，初期的调查没有任何确凿的结论。随后，我们风尘仆仆地赶到斯坦福大学，查阅伽德纳的文书档案。伽德纳在20世纪中期留下来的那一盒盒书信，出乎意料地把我们的调查变成了侦探工作。阅读书信有点儿像偷听别人打电话，你只能听到通话一方所说的话，因此需要推断另一方到底说了什么。从这些回信看，大约50年前，伽德纳本人似乎正在调查秘书问题的来源。但是，看完这些书信，我们更是一头雾水了。哈佛大学数学家弗雷德里克·莫斯特勒回忆说，1955年，他听同事安德烈·格里森提到过这个问题，而格里森又是从其他人那里听说的。阿尔伯塔大学的里奥·莫泽在信中说，他曾经在波音公司R.E.加斯克尔的“笔记”中看到过这个问题，而加斯克尔本人则说他是从一位同事那里听说这个问题的。罗格斯大学的罗杰·平克汉姆称，他是1955年从杜克大学数学家J.舍恩菲尔德那里第一次听说秘书问题的，他还说:“我记得，他说他是从密歇根大学的某个人那里听说的。”几乎可以肯定，“密歇根大学的某个人”其实就是梅里尔·弗拉德。尽管在数学界以外几乎没有人知道弗拉德，但是他对计算机科学的影响很难被忽略。他把“旅行商问题”(我们将在第8章深入讨论)变成了一个广为人知的内容，还设计了“囚徒的困境”，甚至“软件”一词也可能是他造出来的。1958年，他成了已知的第一个发现37%法则的人，同时他宣称，他从1949年就开始考虑这个问题了。但是，在说到最初来源时，弗拉德本人提到了另外几名数学家。秘书问题是一个近乎完美的数学难题:问题本身表述简单，解题难度非常高，答案简洁明了，而影响力又足以让人产生浓厚的兴趣。因此，通过人们的口口相传，这个问题以燎原之势在20世纪50年代的数学界迅速蔓延开来。1960年，在伽德纳专栏的推波助澜之下，它又大大地激发了普通大众的想象力。至20世纪80年代，秘书问题已经变成了一个研究分支，无数人撰文讨论这个问题及与其相关的变体。至于这个问题是如何与秘书产生联系的，这是一个非常有意思的过程——每种文化的社会偏爱都会对社会的形式系统产生影响。例如，在我们的心中国际象棋是中世纪欧洲人的象征，但是实际上国际象棋起源于8世纪的印度。15世纪，粗暴的“欧洲化”过程把沙阿(即国王)变成了王，维齐尔(即高官)变成了王后，而大象则成了基督教主教的形象。最优停止问题同样有多种不同化身，每种化身都是当时关注热点的某种反映。19世纪，最优停止问题的典型形式是巴洛克彩票和女性挑选求婚者的行为;20世纪初，常见的表现形式是驾车度假的人挑选宾馆、男性选择约会对象;在官僚作风盛行、男性占主导地位的20世纪中叶，最典型的最优停止问题是讨论男性老板如何挑选女性助手的问题。第一次明确提出“秘书问题”的是发表于1964年的一篇论文，自此之后，这个名称就再也没有发生变化。37%从何而来?在选择秘书时，遴选程序停止过早或者过晚都会导致不理想的结果。停止过早，最优秀的申请人还没有得到亮相的机会;停止过晚，就说明你在为一位根本不存在的更优秀的申请人保留这份工作。要取得最理想的结果，显然需要在两者之间找到最合适的平衡点，在甄选时既不可迟迟不决，又不可草草收手。如果找到最优秀申请人是你追求的唯一目标，那么在整个面试过程中，只要不是已有申请人当中的最优秀人选，你都不会接受。但是，仅仅达到“目前最佳”这个条件，还不足以说服面试官。比如说，第一名申请人毫无疑问就符合这个条件。一般而言，我们有理由相信，随着面试程序不断进行下去，出现“目前最佳”申请人的概率将不断下降。例如，第二名申请人是截至目前最优秀申请人的可能性是50%，第五名的可能性只有1/5，第六名的可能性只有1/6，以此类推。因此，随着面试工作的深入，目前为止最优秀申请人一旦出现，必然会令人眼前一亮(别忘了，根据定义，这名申请人比之前所有申请人都更加优秀)，不过，这种可能性在不断降低。所以说，看到第一个目前最优秀申请人就欣然接受(也就是说，面试第一名申请人之后就结束面试程序)，显然是过于草率了。在一共有100名申请人时，也不能因为第二名申请人比第一名申请人更优秀就迫不及待地选择他，因为这种做法同样有些操之过急。那么，我们到底该怎么办?凭直觉，我们可以找到几种应对的办法。例如，当第三次(或者第四次)出现胜过前面所有的申请人时，就把工作机会交给他。或者，在连续多个申请人都不理想的情况下，一旦出现一名目前为止最优秀的人选，就毫不犹豫地接受他。但是，事实证明，所有这些相对来说似乎有道理的策略都算不上是最明智的做法。事实上，效果最佳的做法是接受所谓的“摸清情况再行动准则”(look-then-leaprule):事先设定一个“观察”期，在这段时间里，无论人选多么优秀，都不要接受他(也就是说，你的任务就是考察目标，收集数据)。“观察”期结束之后，就进入了“行动”期。此时，一旦出现令之前最优秀申请人相形见绌的人选，就立即出手，再也不要犹豫了。考虑申请人数极少时的秘书问题，“摸清情况再行动准则”就会自动显露出来。如果只有一名申请人，这个问题就非常简单——接受她的申请!如果有两名申请人，无论你如何选择，你成功选到优秀人选的概率都是50%。你可以接受第一名申请人(此时，她是半程最优秀申请人)，或者拒绝她，而拒绝第一名申请人就意味着接受第二名申请人(她也是半程最优秀申请人)。如果有第三名申请人，情况就一下子变得有意思了。如果随机选择一名申请人，得到理想结果的概率是1/3，也就是33%。有两名申请人时，我们没有办法取得比碰运气更好的结果。那么，在有三名申请人时，会怎么样?事实证明，我们可以取得更理想的结果，而其中的关键就在第二场面试。在面试第一名申请人时，我们没有任何信息——她肯定是目前最优秀的申请人。在面试第三名申请人时，我们没有任何能动性——我们只能将工作机会交给这名申请人，因为我们已经拒绝了其他人的申请。但是，在面试第二名申请人时，我们既掌握了一些信息，又有一定的能动性——我们知道她与第一名申请人相比孰优孰劣，同时我们既可以接受她，也可以拒绝她。如果她比第一名申请人优秀，我们接受她，反之就拒绝她，那么会产生什么样的结果?事实上，在有三名申请人时，这是最理想的方案。令人吃惊的是，在有三名申请人时采用这个方法，与有两名申请人时选择半程最优秀人选的方法相比，效果不相上下。在有4名申请人时，穷举所有可能的情况之后就会发现，我们仍然应该在面试第二名申请人时采取行动;如果一共有5名申请人，我们应该等到面试第三名申请人时才采取行动。随着申请人数不断增加，观察与行动之间的分界线正好处在全部申请人37%的位置，从而得出了37%法则:在考察前37%a的申请人时，不要接受任何人的申请;然后，只要任何一名申请人比前面所有人选都优秀，就要毫不犹豫地选择他。事实证明，利用这种最优方案，我们选中最优秀申请人的概率为37%。方案本身与出现理想结果的概率正好相等，这是这类问题表现出来的令人奇怪的数学对称性。上表列出了申请人数不同时的秘书问题最优解决方案。从中可以看出，随着申请人数不断增加，取得理想结果的概率(以及从观察期切换到行动期的时间点)在37%左右。采用最理想的方案也会有63%的失败率，这是一个令人警醒的事实。在面对秘书问题时，即使我们采取了最理想的行动方案，在大多数情况下也会遭遇失败，也就是说，大多数情况下我们都无法选中所有人选当中最优秀的那名申请人。对于把爱情视为寻觅“真命天子”的人来说，这确实是一个坏消息。不过，也不完全都是坏消息。直觉告诉我们，随着申请人数的不断增加，选中最优秀申请人的可能性将稳步下降。例如，如果采用随机选择的方式，在申请人总数为100时，我们得到理想结果的可能性是1%，在总人数为100万时，可能性就会降到0.0001%。但是，令人意想不到的是，秘书问题的计算结果不会发生变化。如果采用最优停止理论，在100人当中选中最优秀申请人的可能性是37%。而总人数是100万时，无论你相信与否，你得到理想结果的可能性仍然是37%。因此，申请人总数越多，最优算法理论就越有价值。的确，在大多数情况下，大海捞针都会无功而返，但是，无论“海洋”多么辽阔，最优停止理论都是最理想的工具。情场上的出手时机托马斯·马尔萨斯两性之间的情欲几乎不会随着时代的变迁而发生改变。在代数学上，我们可以称之为给定量。芭芭拉·布什夺走我的初吻的男人后来成了我的丈夫。我把这些告诉孩子们时，他们的反应十分强烈。卡内基–梅隆大学的运筹学教授迈克尔·特里克也曾经为寻觅真爱而苦恼，当时他还是一名研究生。他回忆说:“我突然想起来，人们研究过这个问题，这不就是秘书问题吗?我身边有一个空缺，现在有若干人提出了申请，而我的目标就是从中选出最优秀的申请者。”于是，他进行了量化分析。他不知道他一辈子可以结识多少名女性，但是37%法则有一定的灵活性，既可以表示申请者的人数，也可以表示遴选过程持续的时间。假设遴选过程从18岁开始，至40岁结束，那么根据37%法则，在26.1岁时他就应该结束观察期，随时果断出手。碰巧的是，当时的特里克正好处于这个年龄。因此，当他发现某一名女性比之前所有约会对象都优秀的时候，他知道机会来了，于是他果断行动。他说:“我不知道她会不会是完美的妻子(模型的各种假设都无法帮助我做出这个判断)，但是毫无疑问，她符合算法为这个步骤开出的所有条件。于是，我向她求婚了。”“结果，她拒绝了我的求婚。”至少从17世纪开始，爱情问题就已经让数学家头疼了。现代人知道约翰尼斯·开普勒这个名字，或许是因为他发现行星轨道是椭圆形的，此外他还是“哥白尼革命”的重要成员，与伽利略、牛顿等人一起，颠覆了人类对自己在宇宙中所处位置的认知。不过，开普勒也不是不食人间烟火。1611年，在他的第一任妻子离世后，渴盼重建家庭的开普勒开始了漫长而艰苦的求爱经历，前后一共交往了11名女性。在前4名交往对象中，开普勒最喜欢第4个(“因为她身材高挑，英姿飒爽”)，但是他没有就此打住。开普勒回忆说:“如果不是爱情和理智把第5名女性强推给我，我应该已经安定下来了。但是，这名女性对我的爱，她的谦恭忠诚、勤俭持家以及她对继子继女的爱，一下子征服了我。”他接着说道:“不过，我仍然我行我素，继续与其他女性交往。”亲朋好友继续为开普勒牵线搭桥，开普勒也没有拒绝，不过兴致不是很高，因为他的心仍然被第5名交往对象占据着。在一共交往了11名女性之后，开普勒决定收手了。他回忆说:“就在我准备前往雷根斯堡的时候，我回过头来去找第5名交往对象并向她求婚，结果她同意了。”于是，开普勒和苏珊娜·罗伊特林格举行了婚礼。除了第一次婚姻留给他的几个孩子之外，开普勒和罗伊特林格又生了6个孩子。据说，开普勒之后的家庭生活十分幸福美满。开普勒和特里克在寻觅爱情上的亲身经历告诉我们(两者的结局正好相反)，秘书问题把情况想得过于简单了。在经典的秘书问题中，申请者肯定希望得到那份工作，像特里克那样遭遇拒绝的情况绝不会发生。此外，申请者一旦被否决之后，就不可以“复活”，因此开普勒采取的策略是行不通的。在秘书问题首次被提出后的几十年时间里，人们研究了各种各样的情境，并结合不同的条件提出了若干最优停止策略。例如，针对可能遭到拒绝的问题，他们提出了一个简单明了的数学答案:尽早向多名对象伸出橄榄枝。假如遭到拒绝的可能性是50%，那么得出37%法则的那个数学分析过程就会告诉你，遴选过程完成1/4后就应该随时准备求婚了。如果遭到拒绝，那么在发现下一个最佳人选时要再次求婚，直到求婚成功为止。运用这个策略，获得成功(即向所有人选中的最佳人选求婚并被接纳)的总概率仍然可以达到25%。根据自己的标准寻觅爱情本身就有难度，再加上遭到拒绝这个不利条件，25%的成功概率可以算是一个还不错的结果了。开普勒把自己没有及时出手的原因归咎于“不安现状、心存疑虑”。他在一封信中向自己的知己好友哀叹:“难道非得四处碰壁，所有欲望都落空之后，我的心才会平静下来，接受命运的摆布吗?”在这种情况下，最优停止理论同样可以起到一定的安慰作用。事实证明，不安现状和心存疑虑并不是道德沦丧或者心理退化的标志，而是在合适情境下捕捉二次机会的最有效策略的一个组成部分。如果可以复活之前被放弃的人选，最优算法就会对我们所熟悉的摸清情况再行动准则做一个小的调整:推迟表态时间，制订备用计划。例如，我们假设即时求婚肯定会被接受，而迟滞求婚则有一半的可能遭到拒绝。根据数学分析，我们在观察前61%的人选时都不应该表态，等到剩余39%的人选中出现目前最优秀人选时再出手。如果考察完了所有人选之后仍然没有找到合适对象(开普勒当时就面临这种情况)，就回过头，在你淘汰的人选当中选择最优秀的那个。在这种情况下，策略与结果之间再次表现出对称性，在允许二次选择这个条件下，你最终选中最优秀人选的概率仍然是61%。正因为现实与经典秘书问题有所不同，所以开普勒最终还是找到了自己的幸福。事实上，经典问题发生的那个小变化也没有导致特里克愿望落空。在遭到拒绝之后，特里克读完大学并在德国找了一份工作。特里克回忆说:“我在酒吧里遇到一位漂亮的姑娘，我们一见钟情，三周后就同居了。后来，我邀请她去美国‘暂住一段时间’。”姑娘接受了邀请。6年后，他们举行了婚礼。掌握候选对象的完整信息经典秘书问题的前提条件是，即时表态一定会被接受，而迟滞表态肯定会遭到拒绝，但是我们在前面讨论的第一组变量(拒绝与复活)则颠覆了这个前提。在这种情况下，最有效的应对办法没有任何变化，仍然是:不要急于表态，观察一段时间后及时出手。不过，秘书问题的一个更重要的前提，可能会引起我们的异议。在秘书问题中，除了可以相互比较之外，我们对这些申请者一无所知。对于优秀人员应该具有哪些特点，我们无法参考任何客观标准或者已有标准，而且在比较这些申请者时，我们只能知道孰优孰劣，但是无法了解彼此之间的确切差距。正因为如此，“观望”阶段是不可避免的。在前期阶段，我们冒着与优秀人选失之交臂的危险，不断调整我们的期望值与权衡标准。数学家把这种最优停止问题称作“无信息博弈”。这种情境可能与大多数寻租公寓、寻觅伴侣和招聘秘书的情况有天壤之别。假设我们可以参考某种客观标准。例如，安排所有秘书参加打字考试，然后像美国高考(SAT)、研究生入学考试(GRE)或者法学院入学考试(LSAT)那样按照百分制统计成绩。也就是说，根据得分，我们可以知道每名申请者的打字水平在所有人选中的位置。如果申请者得了51分，则表示她的打字水平略高于平均水平，如果得了75分，则表示她的水平高于3/4的申请者，以此类推。假设所有申请者可以代表全体人口样本，而且所有数据没有受到任何倾向性或者自选择的影响。同时，假设打字速度是我们判断申请者是否合适的唯一条件。此时，情况就完全不同了，因为我们拥有数学家所谓的“全信息”。1966年的那篇秘书问题研讨会论文指出:“不需要根据积累的经验设定判断标准。有时，我们可以立刻做出一个有益的选择。”换言之，即使得95分的申请者第一个接受评判，我们也可以信心满满地立刻与她签约。当然，前提是我们认为所有申请者中没有得96分的。问题来了。如果我们的目标是找到最适合这份工作的优秀人选，那么我们仍然需要小心斟酌，因为其余的申请者当中可能还有更加优秀的人选。不过，既然我们掌握了全信息，就可以直接计算这种可能性到底有多大。例如，下一个申请者得到96分或者更高分的可能性一定是1/20。因此，是否立刻停止的决定取决于还剩下多少申请者没有接受面试。全信息的意义在于我们无须观望就可以直接出手。此时，我们可以运用阈值准则，一旦发现某位申请者的分数高于某个值，就立刻接受她，而不需要先考察一批候选人并确定阈值。但是，我们需要密切关注可供选择的人还有多少。数学计算表明，如果还有很多人等待面试，那么你就不应该接受当前正在面试的那名申请者，即使她非常优秀，因为你有可能找到一个更优秀的人选。但是，随着可供选择的人数不断减少，你就应该做好准备，随时准备与优于平均水平的申请者确立雇佣关系。有一句我们都比较熟悉(尽管不是那么鼓舞人心)的话说得好:面对花哨的包装，还是降低你的期待吧。我们还可以找到另外一句话，用以说明与之相反的情况:天涯何处无芳草，何必单恋一枝花!重要的是，无论是哪种情况，数学都可以告诉我们临界点到底在哪儿。在这种情况下，最简单的方法是从后往前，反过来理解这些数字的含义。如果你一直面试到最后一名申请者，那么你就别无选择，只能接受他。如果你一直在观望，那么在面试倒数第二名申请者时你需要考虑的问题就变成了:他的分数是否高于50呢?如果是，就雇用她;如果不是，那么你可以考虑把宝押在最后一名申请者身上，因为她的分数高于50的可能性是50%。同理，如果倒数第三名申请者的高于69，倒数第四名的分数高于78，以此类推，那么你就应该立刻选择这名申请者。也就是说，剩余的申请者越多，在评判时就应该越挑剔。无论如何，你都不应该选择低于平均水平的申请者，除非你已经别无选择。(此外，既然你一定要在这些申请者当中挑出最优秀的，那么如果某名申请者不是目前为止最优秀的人选，就一定不要雇用他。)在这种全信息版本的秘书问题中，选中最优秀申请者的可能性是58%。这个概率远谈不上十拿九稳，但是已经大大优于无信息博弈中根据37%法则得到的37%的成功率。如果你掌握了所有信息，那么即使申请人数非常多，你多半也会取得成功。因此，全信息博弈往往会产生令人意想不到，有时甚至会让人感到奇怪的结果。如果追求的目标是金钱，而不是爱情，则成功的可能性更高。在根据某种客观标准(例如收入排名情况)评判合作伙伴时，可供使用的信息比较多。如果评判标准是模糊不清的情感反应(“爱情”)，则可能需要我们根据经验以及比较结果不断做出调整，同时可供使用的信息也相对较少。当然，选择对象的“资产净值”与我们权衡的标准不一定一致。任何标准，只要可以全面反映申请者与其他人对比的情况，就会导致我们弃用摸清情况再行动准则，转而采用阈值准则，同时我们成功找出最优秀申请者的可能性也会大大增加。此外，人们还经常修改秘书问题的其他前提条件，使之与现实生活中寻觅爱情(或挑选秘书)等难题更为相似，结果形成了更多的秘书问题变种。不过，最优停止问题给我们的启发不仅限于约会与招聘这两个方面。事实上，在租房子、找停车位、见好就收的时机选择等问题中，我们同样需要面对一个又一个的可选方案，做出最有利的选择。从一定程度上说，这些问题已经得到了解决。卖房子的时机只需修改经典秘书问题的两个特征，就可以从浪漫的爱情跳进不浪漫的房地产领域。在前文中，我们说过租公寓的过程属于最优停止问题，但是真的拥有房产之后，你仍然难免要与最优停止问题打交道。假设你想卖房子。在咨询了几个房地产中介之后，你将粉刷一新、带有园林景观的房子推向市场，然后静等有意者上门。每个看房人提出有意购买时，你基本上都要做出决定，要么接受，要么拒绝。但是，拒绝是有代价的，因为在下一个有意购买者上门之前，你需要再支付一周(甚至一个月)的抵押贷款，而且下一个购买者的报价未必更高。卖房子与全信息博弈比较相似。我们知道有意者愿意付出的具体金额，不仅可以看出谁报出的价格更高，而且可以看出彼此之间的具体差额。此外，我们还掌握有关房地产市场行情的更多信息，至少可以对预计的报价变化幅度做一个大致的预测。(有了这样的预测，就相当于掌握了上述打字测试中的信息。)两者之间的差别在于目标不同。卖房子时，我们的目标其实不是得到最有利的报价，而是通过整个过程最终获取尽可能多的钱。由于等待是有代价的，是要付出真金白银的，因此当前的有利报价比几个月之后略高一点儿的报价更有吸引力。掌握了这些信息之后，我们就可以省略确定阈值所需的观望阶段，直接确定一个阈值。然后，我们可以忽略所有低于这个阈值的报价，直接接受第一个高于阈值的报价。诚然，如果在某个时间之前不把房子出手，我们有限的积蓄就会消耗殆尽，或者我们只想考虑数量有限的几个报价，对随后的报价不感兴趣，那么在快要达到极限时，我们当然应该降低标准。(购房者喜欢找“积极的”卖主，原因就在这里。)但是，如果没有被这两种情况逼到墙角，那么我们就可以通过成本效益分析，确定是否应该继续观望。接下来，我们分析一种非常简单的情况:假设我们清楚报价金额的变化幅度，并且在这个变化范围内各种报价出现的可能性是相同的。只要报价不会中断(我们的积蓄也不会花完)，我们就可以单纯地考虑我们对收获或损失的期望值，以决定是否继续等待更有利的交易。如果拒绝当前的报价，预计出现更有利报价的可能性是多少?该报价与当前报价之间的差，乘以该报价出现的可能性，乘积是否大于继续等待的成本呢?数学计算的结果清楚地表明，停止价格是等待成本的一个显函数。无论你出售的是价值高达数百万美元的豪宅，还是摇摇欲坠的棚屋，对这个数学结果都不会有任何影响。你唯一需要关心的是你可能接收到的最高报价与最低报价之间的差值。输入几个具体数字，就可以看出这个算法可以提供给我们大量清楚明了的指导意见。例如，假设我们预计报价金额在400000~500000美元之间。首先，如果等待成本非常低，那么在挑选买主时我们几乎无须有任何顾忌。如果等待下一个报价的成本仅为1美元，那么为了赚取尽可能多的钱，我们可以一直等到有人愿意支付499552.79美元时才出手。少一分钱，我们都不会卖给他。如果每次等待需要付出2000美元的代价，那我们就应该等待480000美元这个报价。如果面对的是一个不景气的市场，每次等待需要耗费10000美元时，那么只要报价高于455279美元，我们就应该立刻出手。最后，假设等待成本为预计报价范围的一半(在本例中，报价变化幅度的一半就是50000美元)或更高时，那么观望对我们来说不会有任何好处，最有利的做法是直接接受第一个报价，然后立刻成交。人在屋檐下，不得不低头。在这个问题中，阈值完全取决于搜寻成本，这也是这类问题需要注意的关键要点。下一个报价令人心动的可能性(以及搜寻成本)都不会发生任何变化，因此，无论运气如何，我们在搜寻过程中都无须降低最优停止价格。一旦确定最优停止价格之后(即使这是我们在将房子推向市场之前做出的决定)，我们就再也不要有任何动摇。威斯康星大学麦迪逊分校的优化专家劳拉·阿尔伯特·麦克莱回忆说，她在卖房子时，就用到了最优停止问题的相关知识。她说:“我们收到的第一个报价就非常高，但是他们希望我们比预计的搬离日期早一个月搬走。这个代价太大了。这时候，又有人报出了一个有竞争性的报价......但是我们一直不为所动，直到最后有人报出了令我们满意的报价为止。”对很多卖家而言，建议他们拒绝一两个优厚的报价都会让他们神经紧张，如果随后的报价比不上前者，那么他们就会更加紧张。但是，麦克莱很冷静，坚守立场没有动摇。她承认:“如果我不知道数学计算的结果，就很难坚持下来。”在任何情况下，只要你可以得到一系列报价，而寻找或等待下一个报价需要付出一定成本时，就可以应用上述准则。因此，除了卖房子，在很多情况下我们都可以考虑这条准则。例如，经济学家利用这个算法构建的找工作模型，可以轻而易举地解释失业工人与空缺岗位并存这个看似矛盾的事实。事实上，最优停止问题的这些变种还有一个更令人吃惊的特性。前面说过，在开普勒寻觅爱情的过程中，可以“复活”之前被自己拒绝的机会是一个非常重要的条件。但是，在卖房子或者找工作时，即使我们可以重新考虑之前的报价或工作邀请，即使我们可以肯定那个报价或工作邀请仍然有效，我们也绝不应该重新考虑它。如果之前它没有达到阈值的要求，那么现在它也不会高于阈值。在拒绝那个报价或工作邀请之后，我们的付出已经成为已支付成本。因此，不要妥协，不要试图亡羊补牢。坚持住，不要回头!最优停车位置克拉克·克尔，加州大学伯克利分校校长(1958—1967年)我发现，大学校园里有三个主要的行政管理问题:学生关心性爱，校友关心体育，教职员工关心停车问题。最优停止问题经常出现的另一个领域与汽车驾驶有关(在这个领域，回头同样是不明智的)。在某些早期文献中，秘书问题的主角是驾车者，而汽车只进不退的基本设定把驾车旅行中的所有决策过程(包括寻找饭店、寻找浴室，以及最令城市驾车者头疼的寻找停车位等过程)全部变成了停止问题。要讨论进出停车场的问题，加州大学洛杉矶分校著名的城市规划教授、被《洛杉矶时报》称作“停车场摇滚明星”的唐纳德·舒普显然是最合适的人选。我们从加州北部出发，驾车前往学校拜访舒普。我们告诉舒普，我们为这段行程预留了大量时间，让他不要担心我们会因为意外的交通情况而无法按时抵达。舒普回答说:“说到针对‘意外的交通情况’制订计划，我认为你们应该考虑的是预计的交通情况。”舒普的知名度或许大多归功于他的著作《免费停车的高昂代价》，此外他还做了大量工作，推动人们讨论、了解驾车旅行的真实情况。我们真应该同情那位可怜的驾驶员。根据舒普的模型，理想的停车位应该在停车位“标价”、行走所需时间及造成的麻烦、寻找停车位所需时间(随着目的地、一天中的时间不同而发生显著变化)以及整个过程所消耗的汽油等方面实现优化并达成精确平衡。因为车内乘客人数不同，上述等式会发生变化，因为乘客可以分担停车费用，但是无法分担搜寻时间，也无法分担步行的时间与麻烦。与此同时，驾驶者还需要考虑到的一个问题是:停车位最多的地方可能也是停车需求最大的地方。停车问题含有博弈论的成分，因为在你算计道路上其他驾车者的时候，他们也在算计你。话虽如此，停车难题大多归根于一个数字，即停车位占用率——目前被占用的所有停车位占总停车位的比例。如果占用率很低，找到一个好的停车位并非难事;如果占用率很高，想为你的车找到一席之地就不是那么容易了。舒普认为，停车的很多难题都归因于城市政策，因为这些政策导致停车位占用率极高。如果某个地方的停车费用非常低(更糟糕的是，有的甚至免费)，就会刺激人们把车停在那里，而不是停到稍远的位置，然后步行。于是，大家都想在那儿停车，但是大多数人发现那里已经停满了车，因此他们只好开着车四处巡游，试图找到一个停车位，结果既浪费时间，又浪费汽油。舒普建议的解决办法是安装数字停车计时器，根据停车需求自动调整价格。(旧金山市区已经采用了这种计时器。)在设定价格时，需要先设定一个目标占用率。舒普认为，这个目标值应该在85%左右(对于路边停车率接近100%的大多数大城市而言，这个占用率已经非常低了)。舒普指出，当停车位占用率从90%升至95%时，尽管仅多停了5%的车，但是大家寻找停车位的时间就会翻一番。一旦意识到停车其实是一个最优停止问题，你就会发现占用率对停车策略有着关键的影响。行驶在大街上，每次看到一个空车位时，我们都必须做出决定:是停到这个车位上，还是试试运气，再往前开一点儿?假设你行驶在一条无限长的道路上，路边车位均匀分布，而你的目标是把车停到尽可能接近目的地的车位上，以便少走几步路。那么你应该采用摸清情况再行动准则。为了实现最优停止这个目标，在距离目的地一定路程之外，即使看到空车位也不要停车;一旦进入一定距离之内，就应该从观望阶段转变为行动阶段，看到空车位后立刻停车。这段距离的长短，取决于停车位可能被占用的百分比，即停车位占用率。下表列出了与某些有代表性的停车位占用率相对应的转变距离。如果这条无限长的街道与大城市一样，停车位占用率高达99%，只有1%的停车位是空闲的，那么在距离目的地大约70个停车位(略多于1/4英里a)处开始，只要看到空车位，就应该停车。但是，如果舒普的办法奏效，将占用率降低到85%左右，那么在距离目的地半个街区之前，你都无须着急停车。我们行驶的道路大多不是笔直的，也不会是无限长的。因此，同其他最优停止问题一样，研究人员也在上述基本情况的基础上做出了各种调整。例如，他们考虑了若干不同情况，包括允许驾驶者调头、距离目的地越近停车位越少、驾驶者与目的地相同的其他驾驶者形成竞争关系等。但是，无论该问题的参数发生哪些变化，增加空闲停车位的数量都可以使我们的生活更加方便。从某种意义上讲，这是提示市政府的政策制定者:停车问题不是单纯靠增加资源(停车位)并最大化利用资源(占用)就可以解决的。停车还是一个进程(是一个最优停止问题)，消耗注意力、时间、汽油，还会导致污染和拥堵等后果。合适的政策可以彻底解决这个问题。而且，适宜居住的街区周围有空的停车位，可能是街区运行良好的一个标志，这正好与我们的直觉相反。我们问舒普，他在洛杉矶车流中穿行，前往加州大学洛杉矶分校上班的时候，他的研究是否可以为他提供优化方案。作为一名全世界顶尖的停车问题专家，他是否有什么秘密武器。舒普还真的拥有一个秘密武器:“我骑车上下班。”见好就收的时机1997年，鲍里斯·别列佐夫斯基因拥有大约30亿美元的财产，被《福布斯》杂志确认为俄罗斯首富。仅仅10年前，他还是苏联科学院的一名数学家，靠工资度日。他利用在研究过程中建立的业界关系，创建了一家公司，帮助外国汽车制造商与苏联汽车制造商AvtoVAZ沟通交流。随后，他的公司变成了AvtoVAZ汽车的大型经销商，同时还通过分期付款的方法，利用卢布的恶性通货膨胀牟利。他还利用与AvtoVAZ的合作关系套取资金，用来购买这家汽车制造商及俄罗斯公共电视台、西伯利亚石油公司的部分股份。最终，他赚得了几十亿美元的身家，成为寡头阶层的新成员。随后，他开始参与政治。1996年，他支持鲍里斯·叶利钦连任;1999年，他又支持弗拉基米尔·普京成为叶利钦的继任者。但是，后来别列佐夫斯基的政治态度开始转变。普京当选总统之后不久，别列佐夫斯基公开反对普京提出的旨在扩大总统权限的宪政改革。他在公开场合不断批评普京，导致他与普京的关系开始恶化。2000年10月，在有人请普京就别列佐夫斯基对他的批评发表评论时，普京说:“政府手持大棒，只需一下，就能击碎其脑壳。目前我们还没有动用大棒......一旦我们真的动怒，就将毫不犹豫地砸下去。”当年11月，别列佐夫斯基就离开了俄罗斯，再也没有回来。流亡到英国之后，别列佐夫斯基继续批评普京。别列佐夫斯基如何做出离开俄罗斯的决定?是否可以通过数学方法考虑“见好就收”这条建议?多年前，别列佐夫斯基本人就是一名数学家，而且他研究的正好就是最优停止问题，他创作的第一本书(当然也是他的唯一一本书)全部关于秘书问题，因此他当时可能也考虑了这个问题。人们在分析见好就收这个问题时，为它披上了好几种伪装，但是最适合别列佐夫斯基这种情况的可能应该是“窃贼问题”(向俄罗斯寡头表示歉意)。在窃贼问题中，窃贼可以实施一系列盗窃活动。他们的每次盗窃都会有收获，并且每次都有机会带着战利品顺利脱身。但是，一旦被抓住，他们就会失去之前的所有收获。窃贼希望收获最大，那么什么样的算法可以给他提供合理建议呢?窃贼问题有解，对于盗窃题材的电影剧本而言不是好消息。当盗窃团队诱惑一位已经金盆洗手的老手，希望他复出并干最后一票的时候，这位狡猾的窃贼只需要认真分析那些数字就知道该怎么做了。凭直觉也可以得出结果。实施盗窃的次数应该大致等于顺利脱身的可能性除以被抓的可能性的值。如果你是一名有经验的窃贼，每次盗窃成功的可能性为90%(损失全部身家的可能性为10%)，那么在盗窃9次(90÷10=9)之后，你就应该洗手不干了。如果是一名笨手笨脚、成功率只有一半的生手，情况会怎么样?第一次去偷盗时，你本来就身无分文，因此无须担心有任何损失，但是之后就不要再去碰运气了。尽管别列佐夫斯基是最优停止问题方面的专家，但是他的结局仍然十分凄惨。2013年3月，一名保镖在他位于伯克郡的住所里发现了他的尸体。他死在锁着的浴室里，脖子上系着绳子。官方在尸检之后宣布他死于自杀。由于他在一系列高调的诉讼案中输给了俄罗斯对手，也失去大笔财富，因此他走上了上吊自尽这条不归路。或许他抽身而退的时间还应该更早一些，在积累几千万美元的财富之后就应该收手，而且不能介入政治。但是，遗憾的是，那不是他的做事风格。他在数学界的一位朋友里奥尼德·博古斯瓦夫斯基，曾经讲过别列佐夫斯基的一件往事。当时，他和别列佐夫斯基都还是年轻的研究员。他们前往莫斯科附近，准备进行湖上滑水活动。但是，他们计划使用的那条船出了故障。戴维·霍夫曼在他的《寡头》一书中有这样一段文字:朋友们都跑上沙滩，点起了篝火，只有博古斯瓦夫斯基和别列佐夫斯基向船坞走去，准备修理那台发动机......三个小时之后，他们已经把发动机拆装了一遍，但是发动机仍然无法工作。尽管已经错过了聚会的大多数活动，但是别列佐夫斯基仍然坚持说，他们一定要继续尝试修理发动机。博古斯瓦夫斯基回忆说:“我们想尽办法，试图修好那台发动机。”别列佐夫斯基从来不会轻言放弃。令人吃惊的是，在最优停止的文献资料中也曾提到过不放弃(而且是永不放弃)。有的时序决策问题似乎没有最优停止准则，尽管从我们前面讨论的大量问题看，似乎不应该出现这种情况。“要么三倍，要么赔光”的博弈游戏就是一个简单的例子。假设你带着1美元去玩这个游戏。游戏规则对轮次没有限制，但是要求你每次都要押上所有的钱，你有50%的机会赢回三倍的钱，另外50%的机会全部赔光。那么你应该参与多少轮呢?尽管这个问题非常简单，但它没有合适的最优停止准则，因为每参加一轮游戏，你的平均收益都会略有增加。从1美元开始，你有一半机会赢回3美元，一半机会收回0美元，平均而言，第一轮结束之后，你装进口袋的现金期望值是1.5美元。那么，如果你在第一轮游戏中运气不错的话，第二轮游戏的两个可能结果就会将你刚刚赢回来的3美元变成9美元或者0美元，也就是说，第二轮的平均收益是4.5美元。数学计算结果表明，你应该一直玩下去。但是，果真如此的话，你最终必将输光所有的钱。可见，有的问题有解，反而会有损无益。随时准备停止斯蒂芬·格雷列特我的生命只有一次。因此，如果我能做点儿善事，或者可以向人们表示善意，让我现在就做吧!别让我拖延，别让我疏忽，因为我没有第二次生命!安妮·迪拉德用掉这个下午吧。你不可能把它带走。我们在前文讨论了人们在生活中遭遇停止问题的具体实例，很显然，我们大多数人每天都会遭遇这类问题，只不过表现形式各不相同。生活中最优停止问题无处不在，有时与秘书有关，有时又与未婚夫(或未婚妻)、公寓有关。因此我们难免会想到一个问题:进化、教育或者直觉到底能不能为我们提供最有效的策略?乍一看，答案似乎是否定的。十几项研究已经得出了相同的结果，人们往往在更优秀申请者还没亮相之前就已经草草停止。为了更深入地了解这些研究成果，我们拜访了加州大学河滨分校的阿姆农·拉波波特。他在实验室里从事最优停止实验工作已有40多年了。20世纪90年代，拉波波特与达里尔·希尔合作，完成了一项与经典秘书问题关系密切的研究。在这项研究中，人们需要无数次面对秘书问题，每次申请者的人数为40或者80。结果，人们找到最优秀申请者的总成功率相当不错，大约为31%，与最理想的37%相去不远。大多数人都遵循了摸清情况再行动准则，但是有超过4/5的人出现了出手过早的情况。拉波波特告诉我们，他本人在生活中遇到最优停止问题时，都会想到这个现象。例如，在寻租公寓时，他竭力控制自己希望迅速交易的冲动。他说:“尽管我天生是一个急性子，看到第一个公寓就想租下来，但是我还是竭力控制自己。”但是，这种不耐烦的表现说明经典秘书问题忽略了另外一个需要考虑的因素——时间。别忘了，在你寻觅秘书的全过程中，你没有秘书可用。此外，你把时间都花在面试上，自己的工作就无法完成了。在实验室里解决秘书问题时，停止时机的选择往往过早，原因可能就在于这种成本。希尔和拉波波特认为，如果我们假设面试每名申请者的成本等于发现最优秀秘书所产生价值的1%，那么最优策略就会与实验中人们从观望阶段转变为行动阶段的时间选择正好一致。令人难以理解的是，在希尔和拉波波特的研究中，寻觅是不需要付出任何成本的。那么，人们在实验室中的行为为什么与寻觅需要付出成本时一致呢?这是因为人们认为时间成本一定是存在的，而且时间成本是在人们的真实生活中产生的，与实验如何设计没有关系。因此，寻觅活动的“内在”时间成本(在最优停止模型中通常没有得到体现)也许可以解释人类做出的决策通常与模型的描述之间存在差异的原因。研究最优停止的科研人员尼尔·比尔登指出:“在寻觅工作持续了一段时间之后，我们人类通常就会感到厌烦，即使理性的人也难以避免。但是，模型很难精确地反映出这个变化。”不过，这并不意味着最优停止问题的重要性有所降低。事实上，它的重要性不降反升，因为时间的流逝会把所有决策活动变成最优停止问题。最优停止问题的权威教科书开宗明义地指出:“最优停止理论关注的是如何选择时机以执行特定行动的问题。”很难想出一种更好的方法，可以简明扼要地描述人类所面临的状况。显然，我们需要判断何时应该买进股票，何时应该将这些股票卖出，我们还要决定何时应该打开我们已经封藏了一段时间的葡萄酒，何时应该打断某人，何时应该亲吻某人。这样看来，秘书问题最基本同时也最令人难以置信的前提条件——严格的连续性，即有进无退的单向行进，正好是时间自身属性的一个体现。就此而言，最优停止问题的这个显性前提正好就是使其充满活力的隐性前提。这个前提迫使我们基于还没亲眼看到的可能结果做出决定，迫使我们在采取最优策略之后仍然愿意接受非常高的失败率。我们永远没有二次选择的机会。我们有可能得到类似的选择机会，但是绝不会得到完全相同的选择机会。犹豫不决(不作为)与行为一样不可改变。困在单行线上的驾车者与空间的相互关系就是我们与第四维度的关系:我们的生命真的只有一次。直觉告诉我们，合理的决策需要穷举所有选择，逐一权衡，然后从中找出效果最好的那个选择。但是实际上，在钟表嘀嘀嗒嗒的声音中，决策活动(或者更具一般性的思维活动)的其他方面都淡化了，进一步凸显出停止时机选择的重要性。∑编辑|Gemini粉丝福利送书！想获得此书，文章底部留言，留言点赞前五名的粉丝（24小时计），免费获得此书！责任编辑：