秘书问题的博弈论分析_标题算法之美--秘书问题:要招聘一名秘书,有 n 个人依次来面试。每面试一个人,

一、秘书问题的提出

    我们采用博弈论和概率的方法对秘书问题进行分析，首先总结秘书问题的大概脉络，我们先看秘书问题是如何问提问的，内容是什么，求解什么。

秘书问题（类似名称有相亲问题、止步问题、见好就收问题、苏丹的嫁妆问题、挑剔的求婚者问题等)内容是这样的：要聘请一名秘书，有n人来面试。每次面试一人，面试过后便要即时决定聘不聘他，如果当时决定不聘他，他便不会回来。面试时总能清楚了解求职者的适合程度，并能和之前的每个人作比较。问凭什么策略，才使选得到最适合担任秘书的人的机率最大？　

二、秘书问题的解题策略

基本解决策略如下：对于某些整数r，其中1≤r<n。先面试首r人，都不聘请他们，在之后的n-r人中，如果任何一人比之前面试的人都更佳，便聘请他。r的最佳值应该是r≈n/e≈0.368n。其中e是自然对数的底。基于这个r值得到最佳选项（如例中的“秘书”）的成功率是1 / e （大约 36.8%）。

三、博弈论和概率原理

秘书问题的最优解是一个停止规则。在这个规则里，面试官会拒绝头 r - 1 个应聘者（令他们中的最佳人选为 应聘者 M），然后选出第一个比 M 好的应聘者。可见最优策略包含于这个系列的策略中。对于任意的截断值 r，最佳人选被选中的概率是：

求和符号内概率的计算是基于：如果应聘者 i 是（所有应聘者中的）最佳人选，他被选中当且仅当头 i - 1 个应聘者中的最佳人选处在头 r - 1 个被拒绝的应聘者中。令 n 趋近无穷大，把 x 表示为 r/n 的极限，令 t 为 i/n，dt 为 1/n，总和可以近似为如下积分：

令

 P(x) 对 x 的导数为 0，解出 x，我们得到最优的 x 等于 1/e。从而，当 n 增大时，最优截断值趋近于 n/e 最佳人选被选中的概率为 1/e。

对于较小的 n 值， 最优的 r 也可以通过动态规划方法得到。下表给出了一些最优的 r 值：

四、秘书问题的变化

此问题的变化包括：　　

（1）选择者可选多于一人；

（2）求职者的数目未知；

（3）求职者之间的关系可影响选择；

（4）被拒绝的求职者有一定机率能被叫回来；

（5）选择者满足于次好的人。

（本文大部分内容都整理自网络）