新浪博客

秘书问题的博弈论分析

2013-01-07 10:38阅读：

http://blog.sina.cn/dpool/blog/u/1081658582

一、秘书问题的提出
我们采用博弈论和概率的方法对秘书问题进行分析，首先总结秘书问题的大概脉络，我们先看秘书问题是如何问提问的，内容是什么，求解什么。
秘书问题（类似名称有相亲问题、止步问题、见好就收问题、苏丹的嫁妆问题、挑剔的求婚者问题等)内容是这样的：要聘请一名秘书，有n人来面试。每次面试一人，面试过后便要即时决定聘不聘他，如果当时决定不聘他，他便不会回来。面试时总能清楚了解求职者的适合程度，并能和之前的每个人作比较。问凭什么策略，才使选得到最适合担任秘书的人的机率最大？　
二、秘书问题的解题策略
基本解决策略如下：对于某些整数r，其中1≤r。先面试首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 值：
n
 1
 2
 3
 4
 5
 6
 7
 8
 9
r
 1
 1
 2
 2
 3
 3
 3
 4
 4
P
 1.000
 0.500
 0.500
 0.458
 0.433
 0.428
 0.414
 0.410
 0.406


四、秘书问题的变化
此问题的变化包括：　　
（1）选择者可选多于一人；
（2）求职者的数目未知；
（3）求职者之间的关系可影响选择；
（4）被拒绝的求职者有一定机率能被叫回来；
（5）选择者满足于次好的人。

我的更多文章

下载客户端阅读体验更佳

APP专享