Secretary Problem -- 最佳停止时间

Posted on Edited on

进行和X君吃饭时他举了苏格拉底稻田里捡麦穗的问题，和我聊到爱情就像捡麦穗，准备给我灌鸡汤。我就想到了此前写过的博文，近期刚好更新一下版本。

"37%法则"的意思是，100个应聘者，先面试前37个，且这37无论多优秀都不取，此后的面试只要遇到一个更优秀的，就立刻录取，停止面试，最后找到最佳候选人的的成功率也为37%。这也可以用作相亲，恋爱等领域…这刚好对应了苏格拉底的麦穗问题，是找到最优解的策略。

缘起

我是在读阮一峰的博客[1]的时候看到的这一问题，但据说毕导[2]的视频也涉及过这一问题，于是在重写前刷了一下大概视频。这两者均不够深入，主要涉及经典形式的秘书问题，毕导加了一些数值模拟，考虑了拒绝率等等，但是还是差了点意思。我主要扩展几个我认为会有启发的形式，包括最大化期望和最大化前三优，这相较于经典形式和真正的决策场景更贴合。

最大化找到最优候选人的概率(秘书问题的经典版本)

这个问题有一些假设：

  • 不能吃回头草，错过了就不重新回去找
  • 面试对象完全随机，且邀约不会被拒绝

这里放一个Raghav Ramesh[3]的推导，我就不自己打了。这个版本的答案是面试前1/e，也就是约37%，此后一旦更好就接受。

最大化候选人的期望

我们其实不那么极端，并不是要一定最好。因为按照寻找最优的策略，第二和最后一名是等权重的，我们很可能为了37%的最优血本无归，找到最坏的结果。一个简单的想法是找到期望最大的策略。这个推导我还是沿用Raghav Ramesh的课件。最佳策略是Sqrt(n)-1，在面试总人数大约大于8.39时，行动应该早于37%。

最大化找到前三优的策略

我有赌的成分，所以我还会关注如何寻找前三优的决策。考虑前三优，应该分别在c1 = 33.67%，c2 = 58.68% 和 c3 = 77.46% 接受比样本第1、2、3优的候选人更好的面试者。具体推导可以看 Quine, M. P. and Law的文章[4]。我从Simon Demers[5]的综述抄了一段结论。

  1. (https://www.ruanyifeng.com/blog/2023/01/weekly-issue-23 ↩︎

  2. 【单身狗速进！如何科学有效地脱单？-哔哩哔哩】 https://www.bilibili.com/video/BV1uJ411D7AW/?share_source=copy_web&vd_source=dda0c9ede99c98f35bd4496be7b4f8b9 ↩︎

  3. https://stanford.edu/~rezab/amdm/notes/lecture8.pdf ↩︎

  4. Quine, M. P. and Law, J. S. (1996). Exact Results for a Secretary Problem. Journal of Applied Probability, 33(3):630–639. DOI: 10.2307/3215345. ↩︎

  5. https://arxiv.org/abs/1810.11557 ↩︎