秘書問題
秘書問題（英: secretary problem）は、最適停止問題の一種で、応用確率論、統計学、決定理論の分野で特に研究されている。結婚問題 (marriage problem)、スルターンの持参金問題 (sultan's dowry problem)、最良選択問題 (best choice problem) などともいう。具体的には、次のような問題である。
- 秘書を1人雇いたいとする。
- [math]n[/math] 人が応募してきている。[math]n[/math] という人数は既知である。
- 応募者には順位が付けられ、複数の応募者が同じ順位になることはない（1位からn位まで重複無く順位付けできる）。
- 無作為な順序で1人ずつ面接を行う。次に誰を面接するかは常に同じ確率である。
- 毎回の面接後、その応募者を採用するか否かを即座に決定する。
- その応募者を採用するか否かは、それまで面接した応募者の相対的順位にのみ基づいて決定する。
- 不採用にした応募者を後から採用することはできない。
- このような状況で、最良の応募者を選択することが問題の目的である。
応募者がそれまで面接したどの応募者よりもよい場合は「候補者」となる。問題の目的は1人の最良の応募者を選ぶことであるから、採用を考慮するのは候補者だけでよい。秘書問題が注目された理由の1つとして、この問題の最適ポリシーが驚くべき特徴を持っている点が挙げられる。特に [math]n[/math] が大きい場合、最適ポリシーでは最初の [math]n/e[/math] 人の応募者をスキップし（[math]e[/math] はネイピア数）、それ以降に面接した応募者がそれまでよりよいと判断したら採用する。[math]n[/math] が大きくなると最善の応募者を選択する確率は [math]1/e[/math] すなわち約 37% になる。応募者が100人でも100,000,000人であっても、最適ポリシーに従えば約 37% の確率で最善の応募者を選択できる。
Contents
最適ポリシーの導出
この問題の最適ポリシーを停止規則 (stopping rule) と呼ぶ。それに従うと、面接者は最初の [math]r-1[/math] 人の応募者をスキップし、その次の応募者が候補者（すなわち、それまで面接した中で最もよい応募者）なら採用する。任意の [math]r[/math] について最善の応募者を選択する確率は次の通りである。
- [math] P(r)=\sum_{j=r}^{n}\left(\frac{1}{n}\right)\left(\frac{r-1}{j-1}\right)=\left(\frac{r-1}{n}\right)\sum_{j=r}^{n}\left(\frac{1}{j-1}\right) [/math]
[math]n[/math] が無限大に近づくとして、[math]r/n[/math] の極限を [math]x[/math]、[math]j/n[/math] を [math]t[/math]、[math]1/n[/math] を [math]dt[/math] とすると、上記の総和は次の積分で近似できる。
- [math] P(r)=x \int_{x}^{1}\frac{1}{t}\,dt = -x \log(x) [/math]
[math]P(r)[/math] の [math]x[/math] についての導関数をとり、それを0として [math]x[/math] について解くと、最適な [math]x[/math] が [math]1/e[/math] であることがわかる。したがって最適な切捨て（スキップ）は [math]n[/math] が増大するにつれて [math]n/e[/math] に近づいていき、最善の応募者を選択する確率は [math]1/e[/math] に近づいていく。
[math]n[/math] が小さい場合、最適な [math]r[/math] は標準的な動的計画法の手法で得られる。最適なしきい値 [math]r[/math] と最善例を選択する確率 [math]P[/math] を小さい [math]n[/math] について以下の表で示す。
| [math]n[/math] | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| [math]r[/math] | 1 | 1 | 2 | 2 | 3 | 3 | 3 | 4 | 4 |
| [math]P[/math] | 1.000 | 0.500 | 0.500 | 0.458 | 0.433 | 0.428 | 0.414 | 0.410 | 0.406 |
最善を選択する確率は非常に急速に [math]1/e\approx 0.368[/math] に収束する。
別の解法
秘書問題や類似する問題の直接的解法として Odds algorithm がある。
ヒューリスティックの性能
Stein, Seale, and Rapoport (2003)[1]では、秘書問題を解く際に使われる心理学的に尤もらしいヒューリスティクスの成功確率を検討している。彼らが検討したヒューリスティクスは以下のようなものである。
- カットオフ規則(CR)
- 最初の[math]y[/math]人の応募者を採用しない。その後、最初の候補者（そこまでで1位の応募者）を採用する。これは、[math]y=r[/math] の CSP の最適ポリシーの特殊ケースである。
- 候補者カウント規則(CCR)
- [math]y[/math] 番目の候補者を選択する。最初の応募者をスキップするわけではない。単に候補者（それまでの1位）を数えるだけで、応募者の順序を深く考慮しているわけではない。
- 非候補者の次規則(SNCR)
- 非候補者（そこまでで1位でない応募者）が [math]y[/math] 人出現した後の最初の候補者を選択する。
これらにはいずれも [math]y[/math] というパラメータがある。英語版には [math]n=80[/math] のとき [math]y[/math] を変化させてそれぞれの最善選択確率を計算した図がある。それによると、CRが最も確率が高く、次が SNCR で、CCR が一番確率が低い。
バリエーション: 基本報酬問題
最善の応募者を選択するというのは厳密すぎると思われる場合もある。むしろ、ベストでなくとも、なるべくよい人を雇えればよいという考え方もある。したがって、ベストでなくてもなるべくよい人を選択するほうがよい場合も考えられる。基本報酬問題 (cardinal payoff problem) は、面接者が誰かを採用しないと報酬が得られないとする派生問題である。
この問題をモデル化するため、[math]n[/math]人の応募者それぞれに [math][0,1][/math] で一様分布する独立かつ同一の分布の確率変数 [math]X[/math] で表される値が対応しているとする。上述の問題と同様、面接者は応募者がそれまでで最善かどうかをその場で判断し、採用するか否かを決める。最後の応募者まで到達したら、その人を必ず採用することになる。話を単純化するため、面接者は応募者の相対順位を知らず、単に候補者かどうか（それまでの最善かどうか）だけを知るものとする。面接者はこのバージョンでは、採用した人の「価値」に応じて報酬を得る。例えば、採用された人の値が 0.8 なら、0.8 の報酬を受ける。面接者の目的は、採用者の期待値を最大化することである。
応募者の価値は [math][0,1][/math] に一様分布する互いに独立な同一分布であるため、[math]t[/math]番目の応募者が [math]x_{t}=\max\left\{x_{1},x_{2},\ldots,x_{t}\right\}[/math] となる場合の期待値は次のようになる。
- [math] E_{t}=E\left(X_{t}|I_{t}=1\right)=\frac{t}{t+1} [/math]
本来の秘書問題と同様、最適ポリシーにはしきい値があり、ここではそれを [math]c[/math] とする。面接者は [math]c[/math] 人目以降の候補者を採用すべきである。Bearden (2006)[2]によれば、[math]c[/math] は [math]\lfloor \sqrt n \rfloor[/math] または [math]\lceil \sqrt n \rceil[/math] である。実際、[math]n[/math] 人の候補者で [math]1\leq c \leq n[/math] の任意のしきい値について期待される報酬は次のようになる。
- [math] V_{n}(c)=\sum_{t=c}^{n-1}\left[\prod_{s=c}^{t-1}\left(\frac{s-1}{s}\right)\right]\left(\frac{1}{t+1}\right) +\left[\prod_{s=c}^{n-1}\left(\frac{s-1}{s}\right)\right]\frac{1}{2}={\frac {2cn-{c}^{2}+c-n}{2cn}} [/math]
[math] V_{n}(c)[/math] を [math]c[/math] について微分すると [math]\partial V / \partial c=\left(-{c}^{\,2}+n\right)/ \left(2{c}^{\,2}n\right)[/math] となる。[math]c[/math] の許容される値については常に [math]\partial^{\,2}V / \partial c^{\,2}\lt 0[/math] なので、[math]V[/math] は [math]c=\sqrt n[/math] のときに最大となることがわかる。[math]V[/math] は [math]c[/math] の凸関数なので、最適な整数のしきい値は [math]\lfloor \sqrt n \rfloor[/math] か [math]\lceil \sqrt n \rceil[/math] のどちらかとなる。したがって、本来の秘書問題に比べて基本報酬問題ではスキップする人数が少ないことが多い。なお、これは近似解ではなく、全ての [math]n[/math] について成り立つ。
その他のバリエーション
秘書問題には他にも様々なバリエーションがある。[3]
実験的研究
心理学や実験経済学では、秘書問題を実際の人間を使って実験し研究してきた[4][5][6]。多くの場合、人はあまりにも早く決定を下すという結果が示されている。これは対象を評価するコストがその理由の一部と考えられる。これを実世界に適用して考えてみると、人間は逐次的に判断を下す必要のある場面で十分に検討しない可能性があることを示唆している。例えば、車を運転していて給油しなければならない状況で、よく検討せずにガソリンスタンドを決める場合などが考えられる。すると、人はもっと慎重なら安いガソリンを給油できたかもしれない状況で、余分に出費している傾向があることになる。同じことは、例えばオンラインで安い航空チケットを探している場合などが考えられる。秘書問題などの問題についての実験的研究は behavioral operations research の領域とされる。
関連項目
脚注
- ↑ W. E. Stein, D. A. Seale, A. Rapoport. "Analysis of heuristic solutions to the best choice problem." European Journal of Operational Research, volume 151, pp.140-152.
- ↑ J. N. Bearden. "A new secretary problem with rank-based selection and cardinal payoffs." Journal of Mathematical Psychology, volume 50, pp.58-59. 2006.
- ↑ P. R. Freeman. "The secretary problem and its extensions: A review." International Statistical Review / Revue Internationale de Statistique, volume 51, pp. 189-206. 1983.
- ↑ J. N. Bearden, R. O. Murphy, Rapoport, A. "A multi-attribute extension of the secretary problem: Theory and experiments." Journal of Mathematical Psychology, volume 49, pp.410-425. 2005.
- ↑ J. N. Bearden, A. Rapoport, R. O. Murphy. "Sequential observation and selection with rank-dependent payoffs: An experimental test." Management Science, volume 52, pp. 1437-1449. 2006.
- ↑ D. A. Seale, A. Rapoport. "Sequential decision making with relative ranks: An experimental investigation of the 'secretary problem.'" Organizational Behavior and Human Decision Processes, volume 69, pp.221-236. 1997.
参考文献
(英語)
- F. Thomas Bruss Sum the odds to one and stop, Annals of Probability, Vol. 28. 1384-1391. (2000)
- T. S. Ferguson. "Who solved the secretary problem?" Statistical science, volume 4, pp.282-296. 1989.
(日本語)
- 穴太克則 タイミングの数理 - 最適停止問題 -, シリーズ【[現代人の数理】15, 朝倉書店 (2000), (CiNii書評)
外部リンク
- Online Utility to Calculate Optimal r
- Weisstein, Eric W. “Sultan's Dowry Problem”. MathWorld（英語）. Template:Cite webの呼び出しエラー：引数 accessdate は必須です。
- J. Neil Bearden's Home Page behavioral-or.org
- Optimal Stopping and Applications book by Thomas S. Ferguson
- Optimizing Your Wife