1700494446
算法之美：指导工作与生活的算法 [:1700494107]
1700494447
算法之美：指导工作与生活的算法 卖房子的时机
1700494448
1700494449
只需修改经典秘书问题的两个特征，就可以从浪漫的爱情跳进不浪漫的房地产领域。在前文中，我们说过租公寓的过程属于最优停止问题，但是真的拥有房产之后，你仍然难免要与最优停止问题打交道。
1700494450
1700494451
假设你想卖房子。在咨询了几个房地产中介之后，你将粉刷一新、带有园林景观的房子推向市场，然后静等有意者上门。每个看房人提出有意购买时，你基本上都要做出决定，要么接受，要么拒绝。但是，拒绝是有代价的，因为在下一个有意购买者上门之前，你需要再支付一周（甚至一个月）的抵押贷款，而且下一个购买者的报价未必更高。
1700494452
1700494453
卖房子与全信息博弈比较相似。我们知道有意者愿意付出的具体金额，不仅可以看出谁报出的价格更高，而且可以看出彼此之间的具体差额。此外，我们还掌握有关房地产市场行情的更多信息，至少可以对预计的报价变化幅度做一个大致的预测。（有了这样的预测，就相当于掌握了上述打字测试中的信息。）两者之间的差别在于目标不同。卖房子时，我们的目标其实不是得到最有利的报价，而是通过整个过程最终获取尽可能多的钱。由于等待是有代价的，是要付出真金白银的，因此当前的有利报价比几个月之后略高一点儿的报价更有吸引力。
1700494454
1700494455
掌握了这些信息之后，我们就可以省略确定阈值所需的观望阶段，直接确定一个阈值。然后，我们可以忽略所有低于这个阈值的报价，直接接受第一个高于阈值的报价。诚然，如果在某个时间之前不把房子出手，我们有限的积蓄就会消耗殆尽，或者我们只想考虑数量有限的几个报价，对随后的报价不感兴趣，那么在快要达到极限时，我们当然应该降低标准。（购房者喜欢找“积极的”卖主，原因就在这里。）但是，如果没有被这两种情况逼到墙角，那么我们就可以通过成本效益分析，确定是否应该继续观望。
1700494456
1700494457
接下来，我们分析一种非常简单的情况：假设我们清楚报价金额的变化幅度，并且在这个变化范围内各种报价出现的可能性是相同的。只要报价不会中断（我们的积蓄也不会花完），我们就可以单纯地考虑我们对收获或损失的期望值，以决定是否继续等待更有利的交易。如果拒绝当前的报价，预计出现更有利报价的可能性是多少？该报价与当前报价之间的差，乘以该报价出现的可能性，乘积是否大于继续等待的成本呢？数学计算的结果清楚地表明，停止价格是等待成本的一个显函数。
1700494458
1700494459
无论你出售的是价值高达数百万美元的豪宅，还是摇摇欲坠的棚屋，对这个数学结果都不会有任何影响。你唯一需要关心的是你可能接收到的最高报价与最低报价之间的差值。输入几个具体数字，就可以看出这个算法可以提供给我们大量清楚明了的指导意见。例如，假设我们预计报价金额在400000~500000美元之间。首先，如果等待成本非常低，那么在挑选买主时我们几乎无须有任何顾忌。如果等待下一个报价的成本仅为1美元，那么为了赚取尽可能多的钱，我们可以一直等到有人愿意支付499552.79美元时才出手。少一分钱，我们都不会卖给他。如果每次等待需要付出2000美元的代价，那我们就应该等待480000美元这个报价。如果面对的是一个不景气的市场，每次等待需要耗费10000美元时，那么只要报价高于455279美元，我们就应该立刻出手。最后，假设等待成本为预计报价范围的一半（在本例中，报价变化幅度的一半就是50000美元）或更高时，那么观望对我们来说不会有任何好处，最有利的做法是直接接受第一个报价，然后立刻成交。人在屋檐下，不得不低头。
1700494460
1700494461
在这个问题中，阈值完全取决于搜寻成本，这也是这类问题需要注意的关键要点。下一个报价令人心动的可能性（以及搜寻成本）都不会发生任何变化，因此，无论运气如何，我们在搜寻过程中都无须降低最优停止价格。一旦确定最优停止价格之后（即使这是我们在将房子推向市场之前做出的决定），我们就再也不要有任何动摇。
1700494462
1700494463
1700494464
1700494465
1700494466
卖房子问题的最优停止阈值
1700494467
1700494468
威斯康星大学麦迪逊分校的优化专家劳拉·阿尔伯特·麦克莱回忆说，她在卖房子时，就用到了最优停止问题的相关知识。她说：“我们收到的第一个报价就非常高，但是他们希望我们比预计的搬离日期早一个月搬走。这个代价太大了。这时候，又有人报出了一个有竞争性的报价……但是我们一直不为所动，直到最后有人报出了令我们满意的报价为止。”对很多卖家而言，建议他们拒绝一两个优厚的报价都会让他们神经紧张，如果随后的报价比不上前者，那么他们就会更加紧张。但是，麦克莱很冷静，坚守立场没有动摇。她承认：“如果我不知道数学计算的结果，就很难坚持下来。”
1700494469
1700494470
在任何情况下，只要你可以得到一系列报价，而寻找或等待下一个报价需要付出一定成本时，就可以应用上述准则。因此，除了卖房子，在很多情况下我们都可以考虑这条准则。例如，经济学家利用这个算法构建的找工作模型，可以轻而易举地解释失业工人与空缺岗位并存这个看似矛盾的事实。
1700494471
1700494472
事实上，最优停止问题的这些变种还有一个更令人吃惊的特性。前面说过，在开普勒寻觅爱情的过程中，可以“复活”之前被自己拒绝的机会是一个非常重要的条件。但是，在卖房子或者找工作时，即使我们可以重新考虑之前的报价或工作邀请，即使我们可以肯定那个报价或工作邀请仍然有效，我们也绝不应该重新考虑它。如果之前它没有达到阈值的要求，那么现在它也不会高于阈值。在拒绝那个报价或工作邀请之后，我们的付出已经成为已支付成本。因此，不要妥协，不要试图亡羊补牢。坚持住，不要回头！
1700494473
1700494474
1700494475
1700494476
1700494477
算法之美：指导工作与生活的算法 [:1700494108]
1700494478
算法之美：指导工作与生活的算法 最优停车位置
1700494479
1700494480
克拉克·克尔，加州大学伯克利分校校长（1958—1967年）
1700494481
1700494482
我发现，大学校园里有三个主要的行政管理问题：学生关心性爱，校友关心体育，教职员工关心停车问题。
1700494483
1700494484
最优停止问题经常出现的另一个领域与汽车驾驶有关（在这个领域，回头同样是不明智的）。在某些早期文献中，秘书问题的主角是驾车者，而汽车只进不退的基本设定把驾车旅行中的所有决策过程（包括寻找饭店、寻找浴室，以及最令城市驾车者头疼的寻找停车位等过程）全部变成了停止问题。要讨论进出停车场的问题，加州大学洛杉矶分校著名的城市规划教授、被《洛杉矶时报》称作“停车场摇滚明星”的唐纳德·舒普显然是最合适的人选。我们从加州北部出发，驾车前往学校拜访舒普。我们告诉舒普，我们为这段行程预留了大量时间，让他不要担心我们会因为意外的交通情况而无法按时抵达。舒普回答说：“说到针对‘意外的交通情况’制订计划，我认为你们应该考虑的是预计的交通情况。”舒普的知名度或许大多归功于他的著作《免费停车的高昂代价》，此外他还做了大量工作，推动人们讨论、了解驾车旅行的真实情况。
1700494485
1700494486
我们真应该同情那位可怜的驾驶员。根据舒普的模型，理想的停车位应该在停车位“标价”、行走所需时间及造成的麻烦、寻找停车位所需时间（随着目的地、一天中的时间不同而发生显著变化）以及整个过程所消耗的汽油等方面实现优化并达成精确平衡。因为车内乘客人数不同，上述等式会发生变化，因为乘客可以分担停车费用，但是无法分担搜寻时间，也无法分担步行的时间与麻烦。与此同时，驾驶者还需要考虑到的一个问题是：停车位最多的地方可能也是停车需求最大的地方。停车问题含有博弈论的成分，因为在你算计道路上其他驾车者的时候，他们也在算计你。[1]话虽如此，停车难题大多归根于一个数字，即停车位占用率——目前被占用的所有停车位占总停车位的比例。如果占用率很低，找到一个好的停车位并非难事；如果占用率很高，想为你的车找到一席之地就不是那么容易了。
1700494487
1700494488
舒普认为，停车的很多难题都归因于城市政策，因为这些政策导致停车位占用率极高。如果某个地方的停车费用非常低（更糟糕的是，有的甚至免费），就会刺激人们把车停在那里，而不是停到稍远的位置，然后步行。于是，大家都想在那儿停车，但是大多数人发现那里已经停满了车，因此他们只好开着车四处巡游，试图找到一个停车位，结果既浪费时间，又浪费汽油。
1700494489
1700494490
舒普建议的解决办法是安装数字停车计时器，根据停车需求自动调整价格。（旧金山市区已经采用了这种计时器。）在设定价格时，需要先设定一个目标占用率。舒普认为，这个目标值应该在85%左右（对于路边停车率接近100%的大多数大城市而言，这个占用率已经非常低了）。舒普指出，当停车位占用率从90%升至95%时，尽管仅多停了5%的车，但是大家寻找停车位的时间就会翻一番。
1700494491
1700494492
一旦意识到停车其实是一个最优停止问题，你就会发现占用率对停车策略有着关键的影响。行驶在大街上，每次看到一个空车位时，我们都必须做出决定：是停到这个车位上，还是试试运气，再往前开一点儿？
1700494493
1700494494
假设你行驶在一条无限长的道路上，路边车位均匀分布，而你的目标是把车停到尽可能接近目的地的车位上，以便少走几步路。那么你应该采用摸清情况再行动准则。为了实现最优停止这个目标，在距离目的地一定路程之外，即使看到空车位也不要停车；一旦进入一定距离之内，就应该从观望阶段转变为行动阶段，看到空车位后立刻停车。这段距离的长短，取决于停车位可能被占用的百分比，即停车位占用率。下表列出了与某些有代表性的停车位占用率相对应的转变距离。
1700494495