秘書問題

秘書問題（英: secretary problem）は、最適停止問題の一種で、応用確率論、統計学、決定理論の分野で特に研究されている。結婚問題 (marriage problem)、スルターンの持参金問題 (sultan's dowry problem)、最良選択問題 (best choice problem) などともいう。具体的には、次のような問題である。

  1. 秘書を1人雇いたいとする。
  2. n {\displaystyle n} 人が応募してきている。 n {\displaystyle n} という人数は既知である。
  3. 応募者には順位が付けられ、複数の応募者が同じ順位になることはない（1位からn位まで重複無く順位付けできる）。
  4. 無作為な順序で1人ずつ面接を行う。次に誰を面接するかは常に同じ確率である。
  5. 毎回の面接後、その応募者を採用するか否かを即座に決定する。
  6. その応募者を採用するか否かは、それまで面接した応募者の相対的順位にのみ基づいて決定する。
  7. 不採用にした応募者を後から採用することはできない。
  8. このような状況で、最良の応募者を選択することが問題の目的である。

応募者がそれまで面接したどの応募者よりもよい場合は「候補者」となる。問題の目的は1人の最良の応募者を選ぶことであるから、採用を考慮するのは候補者だけでよい。秘書問題が注目された理由の1つとして、この問題の最適ポリシーが驚くべき特徴を持っている点が挙げられる。特に n {\displaystyle n} が大きい場合、最適ポリシーでは最初の n / e {\displaystyle n/e} 人の応募者をスキップし（ e {\displaystyle e} はネイピア数）、それ以降に面接した応募者がそれまでよりよいと判断したら採用する。 n {\displaystyle n} が大きくなると最善の応募者を選択する確率は 1 / e {\displaystyle 1/e} すなわち約 37% になる。応募者が100人でも100,000,000人であっても、最適ポリシーに従えば約 37% の確率で最善の応募者を選択できる。

最適ポリシーの導出

この問題の最適ポリシーを最適停止規則 (optimal stopping rule) と呼ぶ。それは『面接者は最初の r {\displaystyle r} 人の応募者をスキップし、その後にきた最初の候補者（すなわち、それまで面接した中で最もよい応募者）を採用する』というものであることが知られている。 （ここで用いられる r {\displaystyle r} の値を閾値と呼び、上記のような規則を閾値戦略と呼ぶことが多い） 任意の r ∈ { 1 , 2 , … , n } {\displaystyle r\in \{1,2,\ldots ,n\}} について最良の応募者を選択する確率は次の通りである。

最良の応募者は k + 1 {\displaystyle k+1} 人目であるとする。 最良の応募者が、 { r + 1 , r + 2 , … , n } {\displaystyle \{r+1,r+2,\ldots ,n\}} 人目にいる場合だけ、成功する（最良の応募者を選択する）可能性がある。（すなわち r ≤ k ≤ n − 1 {\displaystyle r\leq k\leq n-1} の場合だけ考えれば良い） 最良の応募者が， r + 1 , r + 2 , … , n {\displaystyle r+1,r+2,\ldots ,n} 人目にいる場合それぞれについて （これらの事象の起きる確率は全て 1 / n {\displaystyle 1/n} ）、 以下のように考える。 最良の応募者を選択できるのは、 1 , 2 , … , k {\displaystyle 1,2,\ldots ,k} 人目の中で最も良い応募者が 1 , 2 , … , r {\displaystyle 1,2,\ldots ,r} 人目の中にいるときであり、 その事象の生起確率は r / k {\displaystyle r/k} . ゆえに成功確率は

P ( r ) = ∑ k = r n − 1 ( ( 1 n ) ( r k ) ) {\displaystyle P(r)=\sum _{k=r}^{n-1}\left(\left({\frac {1}{n}}\right)\left({\frac {r}{k}}\right)\right)}
= ( r n ) ( 1 r + 1 r + 1 + ⋯ + 1 n − 1 ) {\displaystyle =\left({\frac {r}{n}}\right)\left({\frac {1}{r}}+{\frac {1}{r+1}}+\cdots +{\frac {1}{n-1}}\right)}
≃ ( r n ) ( log ⁡ n − log ⁡ r ) = − ( r n ) log ⁡ ( r n ) {\displaystyle \simeq \left({\frac {r}{n}}\right)(\log n-\log r)=-\left({\frac {r}{n}}\right)\log \left({\frac {r}{n}}\right)}
≤ 1 e ≃ 0.3679 {\displaystyle \leq {\frac {1}{e}}\simeq 0.3679}

となる。 上記最後の不等式は、関数 y = − x log ⁡ x {\displaystyle y=-x\log x} が上に凸な関数であり、 x = 1 e {\displaystyle x={\frac {1}{e}}} において最大値 y = 1 e {\displaystyle y={\frac {1}{e}}} を取ることから得られる結果である。

n {\displaystyle n} が小さい場合、最適な r {\displaystyle r} は標準的な動的計画法の手法で得られる。 n {\displaystyle n} が無限大に近づくと、最適な r {\displaystyle r} は n / e {\displaystyle n/e} に近づいていき、最良の応募者を選択する確率は 1 / e {\displaystyle 1/e} に近づいていく。

n {\displaystyle n} が小さい場合、最適な r {\displaystyle r} と最良の応募者を選択する確率 P {\displaystyle P} を小さい n {\displaystyle n} について以下の表で示す。

n {\displaystyle n} 1 2 3 4 5 6 7 8 9 10 50
r {\displaystyle r} 1 1 2 2 3 3 3 4 4 4 19
P {\displaystyle P} 1.000 0.500 0.500 0.458 0.433 0.428 0.414 0.410 0.406 0.40 0.37

最善を選択する確率は 1 / e ≈ 0.3679 {\displaystyle 1/e\approx 0.3679} に収束する。

別の解法

秘書問題や類似する問題の直接的解法として Odds algorithm がある。

ヒューリスティックの性能

Stein, Seale, and Rapoport (2003)[1]では、秘書問題を解く際に使われる心理学的にもっともらしいヒューリスティクスの成功確率を検討している。彼らが検討したヒューリスティクスは以下のようなものである。

カットオフ規則(CR)
最初の y {\displaystyle y} 人の応募者を採用しない。その後、最初の候補者（そこまでで1位の応募者）を採用する。これは、 y = r {\displaystyle y=r} の CSP の最適ポリシーの特殊ケースである。
候補者カウント規則(CCR)
y {\displaystyle y} 番目の候補者を選択する。最初の応募者をスキップするわけではない。単に候補者（それまでの1位）を数えるだけで、応募者の順序を深く考慮しているわけではない。
非候補者の次規則(SNCR)
非候補者（そこまでで1位でない応募者）が y {\displaystyle y} 人出現した後の最初の候補者を選択する。

これらにはいずれも y {\displaystyle y} というパラメータがある。英語版には n = 80 {\displaystyle n=80} のとき y {\displaystyle y} を変化させてそれぞれの最善選択確率を計算した図がある。それによると、CRが最も確率が高く、次が SNCR で、CCR が一番確率が低い。

バリエーション: 基本報酬問題

最善の応募者を選択するというのは厳密すぎると思われる場合もある。むしろ、ベストでなくとも、なるべくよい人を雇えればよいという考え方もある。したがって、ベストでなくてもなるべくよい人を選択するほうがよい場合も考えられる。基本報酬問題 (cardinal payoff problem) は、面接者が誰かを採用しないと報酬が得られないとする派生問題である。

この問題をモデル化するため、 n {\displaystyle n} 人の応募者それぞれに [ 0 , 1 ] {\displaystyle [0,1]} で一様分布する独立かつ同一の分布の確率変数 X {\displaystyle X} で表される値が対応しているとする。上述の問題と同様、面接者は応募者がそれまでで最善かどうかをその場で判断し、採用するか否かを決める。最後の応募者まで到達したら、その人を必ず採用することになる。話を単純化するため、面接者は応募者の相対順位を知らず、単に候補者かどうか（それまでの最善かどうか）だけを知るものとする。面接者はこのバージョンでは、採用した人の「価値」に応じて報酬を得る。例えば、採用された人の値が 0.8 なら、0.8 の報酬を受ける。面接者の目的は、採用者の期待値を最大化することである。

応募者の価値は [ 0 , 1 ] {\displaystyle [0,1]} に一様分布する互いに独立な同一分布であるため、 t {\displaystyle t} 番目の応募者が x t = max { x 1 , x 2 , … , x t } {\displaystyle x_{t}=\max \left\{x_{1},x_{2},\ldots ,x_{t}\right\}} となる場合の期待値は次のようになる。

E t = E ( X t | I t = 1 ) = t t + 1 {\displaystyle E_{t}=E\left(X_{t}|I_{t}=1\right)={\frac {t}{t+1}}}

本来の秘書問題と同様、最適ポリシーにはしきい値があり、ここではそれを c {\displaystyle c} とする。面接者は c {\displaystyle c} 人目以降の候補者を採用すべきである。Bearden (2006)[2]によれば、 c {\displaystyle c} は ⌊ n ⌋ {\displaystyle \lfloor {\sqrt {n}}\rfloor } または ⌈ n ⌉ {\displaystyle \lceil {\sqrt {n}}\rceil } である。実際、 n {\displaystyle n} 人の候補者で 1 ≤ c ≤ n {\displaystyle 1\leq c\leq n} の任意のしきい値について期待される報酬は次のようになる。

V n ( c ) = ∑ t = c n − 1 [ ∏ s = c t − 1 ( s − 1 s ) ] ( 1 t + 1 ) + [ ∏ s = c n − 1 ( s − 1 s ) ] 1 2 = 2 c n − c 2 + c − n 2 c n {\displaystyle 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}}}

V n ( c ) {\displaystyle V_{n}(c)} を c {\displaystyle c} について微分すると ∂ V / ∂ c = ( − c 2 + n ) / ( 2 c 2 n ) {\displaystyle \partial V/\partial c=\left(-{c}^{\,2}+n\right)/\left(2{c}^{\,2}n\right)} となる。 c {\displaystyle c} の許容される値については常に ∂ 2 V / ∂ c 2 < 0 {\displaystyle \partial ^{\,2}V/\partial c^{\,2}<0} なので、 V {\displaystyle V} は c = n {\displaystyle c={\sqrt {n}}} のときに最大となることがわかる。 V {\displaystyle V} は c {\displaystyle c} の凸関数なので、最適な整数のしきい値は ⌊ n ⌋ {\displaystyle \lfloor {\sqrt {n}}\rfloor } か ⌈ n ⌉ {\displaystyle \lceil {\sqrt {n}}\rceil } のどちらかとなる。したがって、本来の秘書問題に比べて基本報酬問題ではスキップする人数が少ないことが多い。なお、これは近似解ではなく、全ての n {\displaystyle n} について成り立つ。

その他のバリエーション

秘書問題には他にも様々なバリエーションがある。[3]

実験的研究

心理学や実験経済学では、秘書問題を実際の人間を使って実験し研究してきた[4][5][6]。多くの場合、人はあまりにも早く決定を下すという結果が示されている。これは対象を評価するコストがその理由の一部と考えられる。これを実世界に適用して考えてみると、人間は逐次的に判断を下す必要のある場面で十分に検討しない可能性があることを示唆している。例えば、車を運転していて給油しなければならない状況で、よく検討せずにガソリンスタンドを決める場合などが考えられる。すると、人はもっと慎重なら安いガソリンを給油できたかもしれない状況で、余分に出費している傾向があることになる。同じことは、例えばオンラインで安い航空チケットを探している場合などが考えられる。秘書問題などの問題についての実験的研究は behavioral operations research の領域とされる。

脚注

  1. ^ 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.
  2. ^ J. N. Bearden. "A new secretary problem with rank-based selection and cardinal payoffs." Journal of Mathematical Psychology, volume 50, pp.58-59. 2006.
  3. ^ P. R. Freeman. "The secretary problem and its extensions: A review." International Statistical Review / Revue Internationale de Statistique, volume 51, pp. 189-206. 1983.
  4. ^ 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.
  5. ^ 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.
  6. ^ 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.wolfram.com (英語).
  • J. Neil Bearden's Home Page behavioral-or.org
  • Optimal Stopping and Applications book by Thomas S. Ferguson
  • Optimizing Your Wife
典拠管理データベース: 国立図書館 ウィキデータを編集
  • イスラエル
  • アメリカ