秘書問題

秘書問題（）は、最適停止問題の一種で、応用確率論、統計学、決定理論の分野で特に研究されている。結婚問題 (marriage problem)、スルターンの持参金問題 (sultan's dowry problem)、最良選択問題 (best choice problem) などともいう。具体的には、次のような問題である。
応募者がそれまで面接したどの応募者よりもよい場合は「候補者」となる。問題の目的は1人の最良の応募者を選ぶことであるから、採用を考慮するのは候補者だけでよい。秘書問題が注目された理由の1つとして、この問題の最適ポリシーが驚くべき特徴を持っている点が挙げられる。特に formula_1 が大きい場合、最適ポリシーでは最初の formula_4 人の応募者をスキップし（formula_5 はネイピア数）、それ以降に面接した応募者がそれまでよりよいと判断したら採用する。formula_1 が大きくなると最善の応募者を選択する確率は formula_7 すなわち約 37% になる。応募者が100人でも100,000,000人であっても、最適ポリシーに従えば約 37% の確率で最善の応募者を選択できる。
最適ポリシーの導出.
この問題の最適ポリシーを最適停止規則 (optimal stopping rule) と呼ぶ。それは『面接者は最初の formula_8 人の応募者をスキップし、その後にきた最初の候補者（すなわち、それまで面接した中で最もよい応募者）を採用する』というものであることが知られている。
（ここで用いられるformula_8の値を閾値と呼び、上記のような規則を閾値戦略と呼ぶことが多い）
任意の formula_10 について最良の応募者を選択する確率は次の通りである。
最良の応募者はformula_11人目であるとする。 
最良の応募者が、formula_12人目にいる場合だけ、成功する（最良の応募者を選択する）可能性がある。（すなわち formula_13 の場合だけ考えれば良い）
最良の応募者が，
formula_14人目にいる場合それぞれについて
（これらの事象の起きる確率は全てformula_15 ）、
以下のように考える。
最良の応募者を選択できるのは、formula_16人目の中で最も良い応募者がformula_17人目の中にいるときであり、
その事象の生起確率はformula_18. 
ゆえに成功確率は
となる。
上記最後の不等式は、関数formula_23が上に凸な関数であり、
formula_24において最大値 formula_25
を取ることから得られる結果である。
formula_1 が小さい場合、最適な formula_8 は標準的な動的計画法の手法で得られる。
formula_1 が無限大に近づくと、最適なformula_8は formula_4 に近づいていき、最良の応募者を選択する確率は formula_7 に近づいていく。
formula_1 が小さい場合、最適な formula_8 と最良の応募者を選択する確率 formula_34 を小さい formula_1 について以下の表で示す。
最善を選択する確率は formula_36 に収束する。
別の解法.
秘書問題や類似する問題の直接的解法として がある。
ヒューリスティックの性能.
Stein, Seale, and Rapoport (2003)では、秘書問題を解く際に使われる心理学的にもっともらしいヒューリスティクスの成功確率を検討している。彼らが検討したヒューリスティクスは以下のようなものである。
これらにはいずれも formula_37 というパラメータがある。英語版には formula_42 のとき formula_37 を変化させてそれぞれの最善選択確率を計算した図がある。それによると、CRが最も確率が高く、次が SNCR で、CCR が一番確率が低い。
バリエーション: 基本報酬問題.
最善の応募者を選択するというのは厳密すぎると思われる場合もある。むしろ、ベストでなくとも、なるべくよい人を雇えればよいという考え方もある。したがって、ベストでなくてもなるべくよい人を選択するほうがよい場合も考えられる。基本報酬問題 (cardinal payoff problem) は、面接者が誰かを採用しないと報酬が得られないとする派生問題である。
この問題をモデル化するため、formula_1人の応募者それぞれに formula_45 で一様分布する独立かつ同一の分布の確率変数 formula_46 で表される値が対応しているとする。上述の問題と同様、面接者は応募者がそれまでで最善かどうかをその場で判断し、採用するか否かを決める。最後の応募者まで到達したら、その人を必ず採用することになる。話を単純化するため、面接者は応募者の相対順位を知らず、単に候補者かどうか（それまでの最善かどうか）だけを知るものとする。面接者はこのバージョンでは、採用した人の「価値」に応じて報酬を得る。例えば、採用された人の値が 0.8 なら、0.8 の報酬を受ける。面接者の目的は、採用者の期待値を最大化することである。
応募者の価値は formula_45 に一様分布する互いに独立な同一分布であるため、formula_48番目の応募者が formula_49 となる場合の期待値は次のようになる。
本来の秘書問題と同様、最適ポリシーにはしきい値があり、ここではそれを formula_51 とする。面接者は formula_51 人目以降の候補者を採用すべきである。Bearden (2006)によれば、formula_51 は formula_54 または formula_55 である。実際、formula_1 人の候補者で formula_57 の任意のしきい値について期待される報酬は次のようになる。
formula_59 を formula_51 について微分すると formula_61 となる。formula_51 の許容される値については常に formula_63 なので、formula_64 は formula_65 のときに最大となることがわかる。formula_64 は formula_51 の凸関数なので、最適な整数のしきい値は formula_54 か formula_55 のどちらかとなる。したがって、本来の秘書問題に比べて基本報酬問題ではスキップする人数が少ないことが多い。なお、これは近似解ではなく、全ての formula_1 について成り立つ。
その他のバリエーション.
秘書問題には他にも様々なバリエーションがある。
実験的研究.
心理学や実験経済学では、秘書問題を実際の人間を使って実験し研究してきた。多くの場合、人はあまりにも早く決定を下すという結果が示されている。これは対象を評価するコストがその理由の一部と考えられる。これを実世界に適用して考えてみると、人間は逐次的に判断を下す必要のある場面で十分に検討しない可能性があることを示唆している。例えば、車を運転していて給油しなければならない状況で、よく検討せずにガソリンスタンドを決める場合などが考えられる。すると、人はもっと慎重なら安いガソリンを給油できたかもしれない状況で、余分に出費している傾向があることになる。同じことは、例えばオンラインで安い航空チケットを探している場合などが考えられる。秘書問題などの問題についての実験的研究は の領域とされる。