秘书问题最优解

要]经典秘书问题是最优停止理论中的一个著名例子，属于一类序贯观察选择问题。其报酬函数仅与观察项的秩相关，而与观察项的实际值无关。现在一定假设条件下，将经典秘书问题推广，建立一个更有实际意义的模型。采用动态规划的方法得到该类模型的选择策略，为实际决策问题提供一种可供参考的方法。秘书问题是一类序贯观察与选择问题，描述了一种动态的信息搜索与决策过程。

[关键词]秘书问题；简易公式；最小概率

[前

言]已有解决秘书问题的方法，主要特征是以取样选项中的最大值作为标杆，其优点是能保证赢的概率最大，其不足是很少考虑决策者的有限理性与启发式偏见。提出了基于次大值标杆策略的设想，通过理论求解以及仿真实验的方法研究了该策略的特征与规律。结果发现：赢的概率随着标杆由最大值向次大值、第三大值等的变化而逐渐降低，且最优截止阀值也不断后移。

一、假设与最优停止规则[1]：

假设下列条件成立（只要左方构成条件的事件的概率大于零）

条件b）的直观意义是：如果已知第n个到达的姑娘的相对名次，则在此时刻以前的信息下引理：若若（1）式成立则最优停止规则是：其中sn可以归纳地计算出来：，对于预测她的绝对名次及拒聘与否，不起任何作用。根据如

（1）则

这里约定

，对空的指标集求和为零。所以最优停止规则是。

二、秘书问题的两个简单公式[2]：

我们知道秘书问题中有两个简易的计算公式。它是对n为有限情形的秘书问题给出两个简易计算公式。

情形1：设经理放过前k个申请者不予考虑，从第k+1个开始选择比前面都好的那位（如果有的话），记ak={放过前k位结果选到1号}

因此，对于n个申请者的情形，

，使选到最差的那位概率最小。

情形2。对于n个申请者由于经理每次招见一批人，他可以在同一批中选择最好的，如果最后一批的人数大于1，经理不可能招聘到1号申请者（最差的那位），因此我们只考虑最后一批人数为1的情形。

设这n个人随机地按d批进见经理，各批的人数分别为n1，n2，⋯，nd，nd=

，

最小.即经理应放掉第1位，才能1，，记。假设经理放过前k批不予考虑，从第k+1批开始选择比前面各批都好的那位（如果有的话），ak={放过前k批最后结果选到1号}，则有

公式2在上述条件下由此可计算的最优值。

[3]

。

三、次大值标杆策略的仿真实验

解决秘书问题的关键，并非决定去选择哪一个选项，而是决定何时停止取样观察选项，即何时停止搜索决策信息。但近些年研究发现，相比较最优解策略，人们往往停止搜索得太早或者搜索量太少[4]。这意味着决策者往往并没有遵循最优解策略去决策。下面我们做一个仿真实验来解决秘书问题的满意解。

实验内容是截止阀值与标杆交叉组合的截止阀法则。根据最优解策略的阀值37%以及现实生活中的经验值，我们测试了7个截止阀值r与2个标杆m的策略组合。它们分别是：截止阀值为选项集的10%、1/

3、37%、50%、06

18、2/

3、90%;标杆为取样选项集中的最大值（m=1）与次大值（m=2）。这样，本研究一共实验了14（7x2）个组合策略。

首先，与已有研究[4]类似，我们用数字的大小表示选项的优劣程度，数字越大意味着选项越优，否则越差。其次，采用序数集的随机排列来模拟选项被随机会见的情境。设选项集n=100，将

1、

2、……、100共一百个序数随机置乱作为测试集。在不同的截止阀值下，分别采用最大值与次大值标杆进行选择;而截止阀值与标杆的每种组合策略重复测试100次。然后计算即赢的次数（选中最大值100的次数），实验结果如表1所示。