秘書問題

秘書問題は、応用確率論、統計学、意思決定理論の分野で広く研究されている最適停止理論^[1]^[2]が関与するシナリオを示している。これは結婚問題、スルタンの持参金問題、うるさい求婚者問題、グーゴルゲーム、最良選択問題とも呼ばれる。その解は37%ルール^[3]としても知られている。

問題の基本的な形式は次のとおりです。あるポジションに応募した順位付け可能な候補者の中から最善の秘書を雇いたいと考えている管理者を想像してください。応募者はランダムな順序で 1 人ずつ面接されます。面接後すぐに、各応募者に関する決定を下す必要があります。一度不採用になった応募者を呼び戻すことはできません。面接中に、管理者は、それまでに面接したすべての応募者の中で応募者を順位付けするのに十分な情報を得ますが、まだ見ていない応募者の質については認識していません。問題は、最善の応募者を選択する確率を最大化する最適な戦略 (停止規則) に関するものです。決定を最後に延期できる場合は、実行中の最大値 (およびそれを達成した人) を追跡し、最後に全体の最大値を選択するという単純な最大値選択アルゴリズムで解決できます。難しいのは、決定をすぐに下さなければならないことです。 $n$

これまでに知られている最も短く厳密な証明は、オッズアルゴリズムによって提供されています。これは、最適な勝利確率は常に少なくとも(ここでeは自然対数の底) であり、後者はより広い一般性においても成り立つことを意味します。最適な停止規則は、面接した最初の応募者を常に拒否し、それまでに面接したどの応募者よりも優秀な最初の応募者で停止する (または、最後の応募者まで続けられる) ことを規定しています。この戦略は停止規則と呼ばれることもあります。なぜなら、この戦略を使用して最適な応募者で停止する確率は、の中程度の値に対して既に約だからです。秘書問題がこれほど注目を集めている理由の 1 つは、この問題の最適なポリシー (停止規則) が単純であり、応募者が 1 億人であろうと 1 億人であろうと、約 37% の確率で 1 人の最適な候補者が選択されるためです。秘書問題は、探索と活用のジレンマです。 $1/e$ $\sim n/e$ $1/e$ $1/e$ $n$

処方

さまざまなバリエーションがありますが、基本的な問題は次のように述べられます。

埋めるべきポジションは 1 つだけです。
このポジションにはn 人の応募者がおり、 nの値はわかっています。
応募者全員をまとめて見れば、最高から最低まで明確に順位付けすることができます。
応募者はランダムな順序で順番に面接を受けますが、各順序は均等に確率が高くなります。
面接後、直ちに採用または不採用が決定され、その決定は取り消しできません。
応募者を受け入れるか拒否するかの決定は、これまで面接した応募者の相対的な順位のみに基づいて行われます。
一般解の目的は、グループ全体の中で最適な応募者を選択する確率を最大化することです。これは期待利得を最大化することと同じであり、最適な応募者の場合は利得が1、そうでない場合は利得が0と定義されます。

候補者とは、面接時に、それ以前に面接したすべての応募者よりも優れた応募者と定義されます。「スキップ」は「面接後すぐに不採用とする」という意味で用いられます。この問題の目的は、最も優れた応募者を一人選抜することであるため、採用の対象となるのは候補者のみです。この文脈における「候補者」は、順列におけるレコードの概念に相当します。

最適な政策を導出する

この問題に対する最適な方策は停止規則である。この規則では、面接官は最初のr − 1 人の応募者を拒否し（応募者Mをこれらのr − 1 人の応募者の中で最良の応募者とする）、その後、応募者M よりも優れた最初の応募者を選択する。最適な戦略はこの戦略のクラスにあることが示される。^[要出典]（これまでに見た中で最も優れた応募者ではない応募者を決して選んではならないことに注意。なぜなら、そのような応募者は全体として最良の応募者ではない可能性があるからである。）任意のカットオフrに対して、最良の応募者が選ばれる確率は

{\begin{aligned}P(r)&=\sum _{i=r}^{n}P\left({\text{applicant }}i{\text{ is selected}}\cap {\text{applicant }}i{\text{ is the best}}\right)\\&=\sum _{i=r}^{n}P\left({\text{applicant }}i{\text{ is selected}}|{\text{applicant }}i{\text{ is the best}}\right)\cdot P\left({\text{applicant }}i{\text{ is the best}}\right)\\&=\left[\sum _{i=1}^{r-1}0+\sum _{i=r}^{n}P\left(\left.{\begin{array}{l}{\text{the best of the first }}i-1{\text{ applicants}}\\{\text{is in the first }}r-1{\text{ applicants}}\end{array}}\right|{\text{applicant }}i{\text{ is the best}}\right)\right]\cdot {\frac {1}{n}}\\&=\left[\sum _{i=r}^{n}{\frac {r-1}{i-1}}\right]\cdot {\frac {1}{n}}\\&={\frac {r-1}{n}}\sum _{i=r}^{n}{\frac {1}{i-1}}.\end{aligned}}

r = 1の場合には和は定義されないが、この場合、唯一実行可能な方策は最初の応募者を選択することであり、したがってP (1) = 1/ nとなる。この和は、応募者iが最善の応募者である場合、最初のi − 1 人の応募者の中で最善の応募者が最初に拒否されたr − 1 人の応募者の中にいる場合にのみ、応募者iが選択されるということに注目することで得られる。n を無限大に近づけ、(r−1) / nの極限として書き、t を(i−1) / n、dt を1/ nとすると、和は次の積分で近似できる。 $x$

P(x)=x\int _{x}^{1}{\frac {1}{t}}\,dt=-x\ln(x)\;.

P ( x )をで微分し、それを 0 としてxについて解くと、最適なx は1/ eに等しいことがわかります。したがって、最適なカットオフはn が増加するにつれてn / eに近づき、最適な応募者が 1/ eの確率で選ばれます。 $x$

nの値が小さい場合、標準的な動的計画法によって最適なrを得ることもできます。最適な閾値rと、いくつかのnの値に対する最良の選択肢Pを選択する確率は、次の表に示されています。^{[注 1]}

古典的な秘書問題において最適な応募者を選択する確率はに収束します。 $1/e\approx 0.368$

代替解決策

この問題とそのいくつかの修正（最適性の証明を含む）は、オッズアルゴリズムによって簡単に解くことができ、このアルゴリズムは他の応用も可能である。このアルゴリズムによって解ける秘書問題への修正には、応募者の空き状況をランダムにすること、応募者が意思決定者の関心を引くためのより一般的な仮説、応募者に対するグループ面接、そしてランダムな数の応募者に対する特定のモデルなどが含まれる。^[要出典]

制限事項

秘書問題の解決は、早期応募者にはまったくチャンスがなく、そうでなければ来ない可能性があるため、応募者が採用された決定戦略について何も知らないと想定することが正当化される場合にのみ意味があります。

古典的な秘書問題の解法を応用する上での重要な欠点の一つは、応募者数を事前に把握しなければならないことですが、実際にはそう簡単にはいきません。この問題を克服する方法の一つは、応募者数を既知の分布を持つ確率変数と仮定することです(Presman and Sonin, 1972)。しかし、このモデルでは、最適解を求めるのは一般的に非常に困難です。さらに、最適な当選確率はもはや1/ e付近ではなく、通常はそれよりも低くなります。これは、応募者数がわからないことに対する「代償」があるという文脈で理解できます。しかし、このモデルではその代償は大きいものです。の分布の選択によっては、最適な当選確率はゼロに近づく可能性があります。この新たな問題に対処する方法を模索した結果、いわゆる1/e法則に基づく最適選択の法則を生み出す新たなモデルが生まれました。 $n$ $N$ $P(N=k)_{k=1,2,\cdots }$ $N$

ベストチョイスの1/e-law

このモデルの本質は、人生は連続的であり、現実世界の問題はリアルタイムで発生するという考えに基づいています。また、特定のイベント（例えば応募者の到着）が実際に発生する頻度（もし実際に発生するとすれば）を推定する方が、発生する特定のイベントの数の分布を推定するよりも容易です。この考えから、いわゆる統一アプローチ（1984）と呼ばれる以下のアプローチが生まれました。

このモデルは次のように定義されます。ある時間間隔において、順位付け可能な応募者の中から、応募者を選抜しなければなりません。目標は、異なる順位の到着順序はすべて等確率であるという仮定のもと、最良の応募者のみを選択する確率を最大化することです。すべての応募者の到着時間密度は同一ですが、互いに独立していると仮定し、対応する到着時間分布関数をとします。 $[0,T]$ $N$ $f$ $[0,T]$ $F$

F(t)=\int _{0}^{t}f(s)ds

、。

\,0\leq t\leq T

を、すべての応募者を時間まで待機して観察し、その後、可能であれば、時間経過後に、先行するすべての応募者よりも優れた最初の応募者を選択するという戦略を考えます。この戦略は1/e戦略と呼ばれ、以下の特性を持ちます。 $\tau$ $F(\tau )=1/e.$ $\tau$ $\tau$

1 /e戦略

（i）すべての成功確率が少なくとも1/eとなる。

N

(ii) は、知らない選択者にとってのミニマックス最適戦略である。

N

(iii) 応募者が少なくとも 1 人いる場合は、確率 1/e でまったく応募者を選択しません。

1984年にF・トーマス・ブルスによって証明された1/e法則は、驚くべきものでした。その理由は、未知の値に対するモデルにおいて、1/e程度の値はこれまで到達不可能と考えられていたのに対し、この1/eという値は成功確率の下限値として達成され、しかも、これはおそらくはるかに弱い仮説に基づくモデルにおいて達成されたからです（例えば、Math. Reviews 85:mを参照）。 $N$

しかし、(i)と(ii)を同時に達成し、さらに全ての>2に対して1/e戦略よりも確実に優れたパフォーマンスを発揮する戦略は他にも数多く存在します。簡単な例としては、少なくとも1人の応募者が時間前に到着していれば、時間後に最初の比較的優れた候補者を（可能であれば）選択し、そうでなければ時間後に2番目に比較的優れた候補者を（可能であれば）選択する戦略が挙げられます。^[4] $N$ $\tau$ $\tau$

1/e法則は、1/eという数の役割が似ていることから、前述の古典的な秘書問題の解法と混同されることがあります。しかし、1/e法則では、この役割はより一般的です。また、この結果は、申請者数が未知数の場合にも成立し、到着時間分布Fに基づくモデルは申請者にとって扱いやすいため、より強力です。

グーゴルのゲーム

「秘書問題を解いたのは誰か？」（ファーガソン、1989年）^[1] という記事では、秘書問題が初めて印刷物に登場したのはマーティン・ガードナーの1960年2月のサイエンティフィック・アメリカン誌の数学ゲームコラムであると主張している。

誰かに好きなだけ紙切れを取ってもらい、それぞれの紙切れに異なる正の数を書きます。書き込む数字は、1の小さな分数からグーゴル（ 1の後に100個のゼロが続く）の大きさ、あるいはそれ以上の数字まで様々です。これらの紙切れは裏向きにされ、テーブルの上でシャッフルされます。1枚ずつ紙切れを表向きにしていきます。一連の紙切れの中で最大の数字を推測したところで、紙切れをめくるのをやめます。戻って以前にめくった紙切れを取ることはできません。すべての紙切れをめくった場合は、当然最後にめくった紙切れを取らなければなりません。^[5]

ファーガソンは、秘書ゲームは二人の敵対するプレイヤーによるゼロサムゲームであり、未解決のままであると指摘した。^[1]このゲームでは、

情報を知っているプレイヤーのアリスは、カードに秘密裏に異なる数字を書きます。 $n$
止めるプレイヤーのボブは、実際の値を観察し、いつでもカードをめくるのを止めることができ、最後にめくったカードの数字が全体で最大であれば勝ちます。
ボブは可能な限り高い確率で最大の数字を推測したいのですが、アリスの目標はこの確率を可能な限り低く抑えることです。

基本的な秘書問題との違いは次の 2 つです。

アリスは必ずしも一様にランダムに数字を書く必要はありません。ボブを騙すために、任意の結合確率分布に従って数字を書くこともできます。
ボブはカードに書かれた実際の値を観察し、それを意思決定手順に使用することができます。

戦略分析

アリスはまずn個の数字を書き、それをシャッフルします。つまり、数字の順序は関係ありません。つまり、アリスの数字は交換可能な確率変数列でなければなりません。アリスの戦略は、最も難しい交換可能な確率変数列を選ぶことです。 $X_{1},X_{2},...,X_{n}$

ボブの戦略は、シーケンスの停止規則として形式化できます。 $\tau$ $X_{1},X_{2},...,X_{n}$

ボブに対する停止規則がの相対ランクのみに依存し、それらの数値には依存しない場合、その規則は相対ランク停止戦略であるという。言い換えれば、アリスが数字を選んだ後に誰かが密かに介入し、の各数字をその相対ランクに変更した（同点の場合はランダムにブレークする）かのようだ。たとえば、はまたはに等しい確率で変更される。これは、アリスがにおいて交換可能なランダム順列を行ったかのようである。ここで、における唯一の交換可能なランダム順列はにおけるすべての順列にわたる一様分布であるため、最適な相対ランク停止戦略は、上記に示した秘書問題に対する勝利確率がである最適な停止規則である。アリスの目標は、ボブが相対ランク停止戦略よりも良い結果を出せないようにすることである。 $\tau$ $X_{1},X_{2},...,X_{n}$ $X_{1},X_{2},...,X_{n}$ $0.2,0.3,0.3,0.1$ $2,3,4,1$ $2,4,3,1$ $\{1,2,...,n\}$ $\{1,2,...,n\}$ $\{1,2,...,n\}$ $Pr(X_{\tau }=\max _{i\in 1:n}X_{i})=\max _{r\in 1:n}{\frac {r-1}{n}}\sum _{i=r}^{n}{\frac {1}{i-1}}$

ゲームのルールにより、アリスの数列は交換可能でなければなりませんが、ゲームでうまくいくためには、アリスはそれを独立に選んではなりません。アリスが何らかの固定された分布から独立に数字をサンプリングすれば、ボブの成績が良くなります。これを直感的に理解するには、で、アリスが正規分布から両方の数字を独立に選ぶとします。すると、ボブが 1 つの数字をめくってが見えたら、2 番目の数字も自信を持ってめくることができ、ボブが 1 つの数字をめくってが見えたら、1 番目の数字を自信を持って選ぶことができます。アリスは、が正の相関関係にあるを選ぶことで、成績を良くすることができます。 $n=2$ $N(0,1)$ $-3$ $+3$ $X_{1},X_{2}$

したがって、完全な正式な声明は次のようになります。

任意の停止規則に対して、となるような、交換可能な確率変数のシーケンスは存在しますか? $X_{1},...,X_{n}$ $\tau$ $Pr(X_{\tau }=\max _{i\in 1:n}X_{i})\leq \max _{r\in 1:n}{\frac {r-1}{n}}\sum _{i=r}^{n}{\frac {1}{i-1}}$

解決

の場合、ボブが最適な相対ランク停止戦略を採用すると、ボブの勝ち確率は 1/2 になります。驚くべきことに、アリスにはミニマックス戦略がありません。これは、T. Cover ^[6]のパラドックスや2 つの封筒のパラドックスと密接に関連しています。具体的には、ボブは次の戦略を採用できます。乱数をサンプリングします。の場合はを選択し、それ以外の場合はを選択します。これで、ボブは 1/2 よりも確実に大きな確率で勝つことができます。アリスの数字が異なると仮定すると、の条件では、ボブは確率 1/2 で勝ちますが、の条件では、ボブは確率 1 で勝ちます。 $n=2$ $Y$ $X_{1}>Y$ $X_{1}$ $X_{2}$ $Y\not \in [\min(X_{1},X_{2}),\max(X_{1},X_{2})]$ $Y\in [\min(X_{1},X_{2}),\max(X_{1},X_{2})]$

確率がゼロでない限り、乱数は任意のランダム分布からサンプリングできることに注意してください。 $Y$ $Y\in [\min(X_{1},X_{2}),\max(X_{1},X_{2})]$

しかし、任意のに対して、アリスはボブの勝利確率が最大となるような交換可能なシーケンスを構築することができます。^[1] $\epsilon >0$ $X_{1},X_{2}$ $1/2+\epsilon$

しかし、の場合、答えはイエスです。アリスは、ボブが相対的な順位に基づいた古典的な停止戦略を使用するよりも良いプレイができないような方法で、乱数（従属確率変数）を選択できます。^[7] $n>2$

ヒューリスティックパフォーマンス

記事の残りの部分では、応募者数がわかっている場合の秘書問題について再度取り上げます。

スタイン、シール、ラポポート（2003）は、秘書問題で用いられる可能性のある、心理学的に妥当性のあるいくつかのヒューリスティックの期待成功確率を導出した。彼らが検討したヒューリスティックは以下の通りである。

カットオフルール（CR）：最初のy人の応募者を受け入れない。その後は、最初に出会った候補者（相対順位1の応募者）を選択する。このルールの特別なケースとして、 y = rとなる古典的な秘書問題における最適方策がある。
候補者カウントルール（CCR）：y番目に遭遇した候補者を選択します。このルールは必ずしも応募者を除外するわけではないことに注意してください。このルールは、観察された候補者の数のみを考慮し、意思決定者が応募者シーケンスのどの階層に位置するかは考慮しません。
連続非候補者ルール (SNCR): y 人の非候補者 (つまり、相対順位が 1 を超える応募者) を観察した後、最初に見つかった候補者を選択します。

各ヒューリスティックには単一のパラメータyがあります。右の図は、n = 80 の問題における各ヒューリスティックの期待成功確率をyの関数として示しています。

カーディナルペイオフバリアント

最優秀の応募者を一人だけ見つけるというのは、かなり厳格な目標のように思えるかもしれません。面接官は、最優秀の応募者を選ぶことだけにこだわるのではなく、価値の低い応募者よりも価値の高い応募者を採用したいと考えるでしょう。つまり、面接官は必ずしも最優秀ではない応募者を選ぶことで何らかの価値を見出し、その価値は選ばれた応募者の価値に応じて増大するのです。

この問題をモデル化するために、応募者の「真の」値は、 [0, 1]の一様分布から独立分布で抽出された確率変数Xであると仮定します。上記の古典的な問題と同様に、面接官は各応募者が現時点で最良（候補者）であるかどうかのみを観察し、各応募者をその場で承認または拒否し、最後の応募者に到達した場合は、その応募者を承認しなければなりません。（明確にするために、面接官は各応募者の実際の相対順位を知るわけではありません。面接官は、応募者が相対順位1であるかどうかのみを知ります。）ただし、このバージョンでは、報酬は選択された応募者の真の値によって決まります。例えば、面接官が真の値が0.8である応募者を選択した場合、面接官は0.8を獲得します。面接官の目的は、選択された応募者の期待値を最大化することです。 $n$

応募者の値は[0, 1]の一様分布からiid抽出されるため、t番目の応募者の期待値は次のように与えられる。 $x_{t}=\max \left\{x_{1},x_{2},\ldots ,x_{t}\right\}$

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

古典的問題と同様に、最適な方策は閾値によって与えられ、この問題ではこれをと表記し、面接官はそこから候補者を受け入れ始めるべきである。ベアデンはcがまたはであることを示した。^[8]（実際にはに最も近い方である。）これは、応募者に関する問題が与えられた場合、任意の閾値に対する期待利得が $c$ $\lfloor {\sqrt {n}}\rfloor$ $\lceil {\sqrt {n}}\rceil$ ${\sqrt {n}}$ $n$ $1\leq c\leq n$

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}}.

cについて微分すると、 $V_{n}(c)$

{\frac {\partial V}{\partial c}}={\frac {-{c}^{\,2}+n}{2{c}^{\,2}n}}.

部分情報逐次探索パラダイムにおける学習。数字は、探索の様々な時点における応募者の相対順位（これまでに確認された応募者総数m人のうち）に基づく期待値を示しています。期待値は、応募者の値が0から1の間で均一に分布している場合を基準に計算されます。相対順位情報により、面接官は応募者と比較するデータポイントが蓄積されるにつれて、より細かく応募者を評価することができます。

のすべての許容値に対してであるため、がで最大化されることがわかります。V はで凸であるため、最適な整数値の閾値はまたはでなければなりません。したがって、のほとんどの値に対して、面接官は、最良の応募者 1 人を選ぶことを目的とする従来のバージョンよりも、基数的報酬バージョンの方が早く応募者の受け入れを開始します。これは漸近的な結果ではないことに注意してください。これはすべてのに対して当てはまります。興味深いことに、秘書のそれぞれがからまで固定された異なる値を持つ場合、はで最大化され、以前と同じ凸性の主張が行われます。^[9]他の既知の分布については、動的計画法を使用して最適なプレイを計算できます。 $\partial ^{\,2}V/\partial c^{\,2}<0$ $c$ $V$ $c={\sqrt {n}}$ $c$ $\lfloor {\sqrt {n}}\rfloor$ $\lceil {\sqrt {n}}\rceil$ $n$ $n$ $n$ $1$ $n$ $V$ $c={\sqrt {n}}-1$

^{PalleyとKremer (2014) [10]}によって導入されたこの問題のより一般的な形式では、新しい応募者が到着するたびに、面接官は以前に観察されたすべての応募者に対する彼らの順位を観察すると仮定しています。このモデルは、面接官が検索プロセスを続けるにつれて、到着した新しい候補者を評価するために使用できる過去のデータポイントのセットを蓄積することによって学習するという概念と一致しています。このいわゆる部分情報モデルの利点は、相対的な順位情報を与えられた場合に達成された決定と結果を、面接官が各応募者の価値に関する完全な情報を与えられた場合に、対応する最適な決定と結果と直接比較できることです。応募者が既知の分布から独立して抽出され、面接官が選択された応募者の期待値を最大化しようとするこの完全情報問題は、もともとMoser (1956)、^[11] Sakaguchi (1961)、^[12]およびKarlin (1962)によって解決されました。

その他の変更

秘書問題には、シンプルでエレガントな解決法を持つバリエーションがいくつかあります。

1回の試行で2番目に良いものを選択する

一つの変種は、最良のものを選びたいという欲求を、次善のものを選びたいという欲求に置き換えるものである。^[13]^[14]^[15]この問題では、応募者が偶数人の場合の成功確率はちょうどである。この確率はnが無限大に近づくにつれて1/4に近づく。これは、最良のものを選ぶ方が次善のものを選ぶよりも簡単であるという事実を示している。 ${\frac {0.25n^{2}}{n(n-1)}}$

k回の試行で上位k個を選択する

k 回の試行で、n 人の候補者の中から最も優秀な k 人の秘書を選ぶ問題を考えてみましょう。

一般的に、最適な決定法は、まず候補を一つも選ばずに観察することから始め、次にそれらの最初の候補よりも優れた候補を全て選び、候補がなくなるまで続ける。が一定での場合、成功確率はに収束する。^[16] Vanderbei 1980によれば、の場合、成功確率はである。 $r=\left\lfloor {\frac {n}{ke^{1/k}}}\right\rfloor$ $r$ $k$ $n\to \infty$ ${\frac {1}{ek}}$ $k=n/2$ ${\frac {1}{n/2+1}}$

複数回試して最良のものを選ぶ

この変種では、プレイヤーは複数の選択肢を持ち、その中のどれかが最善であれば勝利する。この問題に対する最適な戦略は、閾値数（）の集合によって定義される戦略のクラスに属する。 $r$ $(a_{1},a_{2},...,a_{r})$ $a_{1}>a_{2}>\cdots >a_{r}$

具体的には、からまでラベル付けされた合格通知があるとします。各担当者はそれぞれ1通の通知を保持しています。あなたは候補者との面接を続け、すべての担当者が閲覧できる表に候補者をランク付けします。担当者は、からまでのすべての候補者の中で最初に成績が良かった候補者に合格通知を送ります。（送付されなかった合格通知は、標準的な秘書問題と同様に、デフォルトで最後の応募者に渡されます。）^[17] $r$ $1$ $r$ $r$ $i$ $1$ $a_{i}$

極限では、ある有理数に対して、各が成り立ちます。^[18] $n\rightarrow \infty$ $a_{i}\sim ne^{-k_{i}}$ $k_{i}$

勝利の確率

のとき、勝利の確率はに収束します。より一般的には、正の整数のとき、勝利の確率はに収束します。ここでです。^[18] $r=2$ $e^{-1}+e^{-{\frac {3}{2}}},(n\rightarrow \infty )$ $r$ $p_{1}+p_{2}+\cdots +p_{r}$ $p_{i}=\lim _{n\rightarrow \infty }{\frac {a_{i}}{n}}$

^[17]まで計算され、である。 $r=4$ $e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}$

Matsui & Ano 2016は一般的なアルゴリズムを示した。例えば、 $p_{5}=e^{-{\frac {4162637}{1474560}}}$

実験研究

実験心理学者と経済学者は、秘書問題の状況における実際の人々の意思決定行動を研究してきた。 ^[19]この研究は主に、人々が探索をすぐにやめてしまう傾向があることを示している。これは、少なくとも部分的には、候補を評価するコストによって説明できるかもしれない。現実世界の設定では、これは、意思決定の選択肢が順番に現れる問題に直面したとき、人々が十分に探索していないことを示唆しているのかもしれない。例えば、高速道路沿いのどのガソリンスタンドで給油するかを決めようとするとき、人々は十分に探索しないまま立ち止まるかもしれない。もしこれが本当なら、彼らは長く探索した場合よりもガソリンに多く支払う傾向があるだろう。人々がオンラインで航空券を検索するときにも同じことが当てはまるかもしれない。秘書問題のような問題に関する実験的研究は、行動オペレーションズ・リサーチと呼ばれることがある。

神経相関

^動物[20]^[21]と人間^[22]の両方を対象にした知覚意思決定課題における情報統合、つまり信念の表現に関する神経科学研究は相当な量行われているが、情報収集をやめるという決定がどのようになされるかについてはほとんどわかっていない。

研究者たちは、機能的MRIを用いて健康なボランティアを対象に秘書問題解決の神経基盤を研究した。^[23]マルコフ決定過程（MDP）を用いて、探索を続けることと現在の選択肢にコミットすることの価値を定量化した。選択肢を取るか断るかの決定は、頭頂葉および背外側前頭前野、さらに腹側線条体、前島皮質、前帯状皮質を活性化した。したがって、これまで証拠の統合と報酬表象に関与することが示唆されてきた脳領域は、選択にコミットする決定を引き起こす閾値通過を符号化している。

歴史

秘書問題は、1949年にメリル・M・フラッドによって提唱されたとみられ、同年に行った講演で「婚約者問題」と呼んだ。彼は1950年代にも何度かこの問題に触れ、例えば1958年5月9日のパーデュー大学での学会講演でも触れた。当時は何も出版されていなかったものの、最終的には民間伝承として広く知られるようになった。1958年、彼はレナード・ギルマンに手紙を送り、サミュエル・カーリンやJ・ロビンズを含む12人の友人にもコピーを送った。その中で、最適戦略の証明の概要が示され、R・パレルモによる付録が添付されていた。パレルモは、すべての戦略は「最初の候補を無条件に拒否し、次に優れた候補を受け入れる」という形式の戦略によって支配されることを証明した。^[24]

最初の発表は、マーティン・ガードナーによる1960年2月の『サイエンティフィック・アメリカン』誌上での発表だったようです。彼は、ジョン・H・フォックス・ジュニアとL・ジェラルド・マーニーからこの問題について聞いていました。彼らは1958年に独立して同等の問題を解き、「グーゴルのゲーム」と呼んでいました。フォックスとマーニーは最適解を知りませんでした。ガードナーはレオ・モーザーに助言を求め、モーザーは（J・R・パウンダーと共に）雑誌に掲載するための正しい解析を行いました。その後まもなく、数人の数学者がガードナーに手紙を書き、人づてに聞いた同等の問題を伝えました。これらの出来事はすべて、フラッドのオリジナルの研究に遡る可能性が高いと考えられます。^[25]

1/ e法則はF.トーマス・ブルスによるものです。^[26]

ファーガソンは膨大な参考文献を所蔵しており、同様の（しかし異なる）問題が1875年にアーサー・ケイリーによって検討されていたこと、さらにそれ以前にヨハネス・ケプラーによっても検討されていたことを指摘している。ケプラーは最初の妻の死後、1611年から1613年にかけて2年間かけて11人の結婚候補者を調査した。^[27]^[28]

組み合わせ論的一般化

秘書問題は、複数の異なる職種がある場合に一般化できます。この場合も、応募者はランダムな順序で現れます。応募者は到着時に、非負の数値の集合を提示します。各値は、応募者がいずれかの職種に対する資格を示します。管理者は、応募者を採用するかどうかを決定するだけでなく、採用する場合は、応募者をいずれかの職種に正式に割り当てる必要があります。目的は、資格の合計が可能な限り大きくなるような割り当てを見つけることです。この問題は、片側のノードがランダムな順序でオンラインになる、辺に重み付けされた二部グラフにおいて、最大重みマッチングを見つける問題と同じです。したがって、これはオンライン二部マッチング問題の特殊なケースです。 $n$ $n$

秘書問題に対する古典的なアルゴリズムを一般化することで、資格の期待値の合計が最適な（オフラインの）割り当てよりもわずか1倍小さい割り当てを得ることができます。 ^[29] $e$

参照

ウィキメディア・コモンズには、秘書問題に関連するメディアがあります。

注記

^ abcd Ferguson, Thomas S. (1989年8月). 「秘書問題を解決したのは誰か?」.統計科学. 4 (3): 282– 289. doi : 10.1214/ss/1177012493 .
^ ヒル、セオドア・P. (2009). 「いつ止めるべきかを知る」.アメリカン・サイエンティスト. 97 (2): 126– 133. doi :10.1511/2009.77.126. ISSN 1545-2786. S2CID 124798270.フランス語訳については、 Pour la Science （2009年） 7月号の表紙記事をご覧ください。
^ Thomson, Jonny (2022年4月21日). 「数学者は人生最大の決断に『37%ルール』を提案」Big Think . 2024年2月6日閲覧。
^ グネディン 2021.
^ ガードナー 1966.
^ Cover, Thomas M. (1987), Cover, Thomas M.; Gopinath, B. (eds.), "Pick the Largest Number" (PDF) , Open Problems in Communication and Computation , New York, NY: Springer, p. 152, doi :10.1007/978-1-4612-4808-8_43, ISBN 978-1-4612-4808-8、 2023年6月25日閲覧
^ グネディン 1994.
^ ベアデン 2006.
^ ジョーンズ、マクスウェル; ネネ、アドバイト (2024年8月20日). 「秘書問題のバリアント深掘り」
^ Palley, Asa B.; Kremer, Mirko (2014年7月8日). 「シーケンシャルサーチとランクフィードバックからの学習：理論と実験的証拠」 . Management Science . 60 (10): 2525– 2542. doi :10.1287/mnsc.2014.1902. ISSN 0025-1909.
^ モーザー、レオ (1956). 「ケーリーの問題について」.スクリプタ数学. 22 : 289–292 .
^ 坂口実 (1961年6月1日). 「いくつかの逐次サンプリング設計の動的計画法」.数理解析応用ジャーナル. 2 (3): 446– 466. doi : 10.1016/0022-247X(61)90023-3 . ISSN 0022-247X.
^ Rose, John S. (1982). 「ランダムシーケンスからの非極値候補の選択」. J. Optim. Theory Appl . 38 (2): 207– 219. doi :10.1007/BF00934083. ISSN 0022-3239. S2CID 121339045.
^ シャヨフスキ、クシシュトフ (1982)。「ランクaのオブジェクトの最適な選択」。マテマティカストソワナ。 Annales Societatis Mathematicae Polonae、シリーズ III。10 (19): 51–65。土井:10.14708/ma.v10i19.1533。ISSN 0137-2890。
^ ヴァンダーベイ、ロバート J. (2021 年 6 月 21 日)。「秘書問題のポスドクの変形」。Mathematica アプリカンダ。 Annales Societatis Mathematicae Polonae、シリーズ III。49 (1): 3–13 .土井:10.14708/ma.v49i1.7076。ISSN 2299-4009。
^ ギルダール＆デュデック 2009.
^ ab ギルバート & モステラー 1966.
^ ab 松井＆阿野 2016.
^ ベアデン、マーフィー、ラポポート（2006年）；ベアデン、ラポポート、マーフィー（2006年）；シールとラポポート（1997年）；パリーとクレマー（2014年）
^ Shadlen, MN; Newsome, WT (1996年1月23日). 「動きの知覚：見て、そして決定する」. Proceedings of the National Academy of Sciences . 93 (2): 628– 633. Bibcode :1996PNAS...93..628S. doi : 10.1073/pnas.93.2.628 . PMC 40102. PMID 8570606 .
^ Roitman, Jamie D.; Shadlen, Michael N. (2002年11月1日). 「複合視覚弁別反応時間課題における側頭内側野のニューロンの反応」. The Journal of Neuroscience . 22 (21): 9475– 9489. doi :10.1523/JNEUROSCI.22-21-09475.2002. PMC 6758024. PMID 12417672 .
^ Heekeren, Hauke R.; Marrett, Sean; Ungerleider, Leslie G. (2008年5月9日). 「人間の知覚的意思決定を媒介する神経システム」. Nature Reviews Neuroscience . 9 (6): 467– 479. doi :10.1038/nrn2374. PMID 18464792. S2CID 7416645.
^ Costa, VD; Averbeck, BB (2013年10月18日). 「最善選択問題における情報サンプリングの基盤となる前頭葉-頭頂葉および大脳辺縁系-線条体の活動」.大脳皮質. 25 (4): 972–982 . doi :10.1093/cercor/bht286. PMC 4366612. PMID 24142842 .
^ 1958年の洪水。
^ ガードナー 1966、問題3。
^ ブルス 1984.
^ ファーガソン 1989.
^ シーゲル、イーサン (2023年9月26日). 「天文学者ヨハネス・ケプラーは人生で最も難しい問題、結婚を解決した」. Big Think; Starts with a Bang . 2025年8月31日閲覧。ケプラーは、結婚相手を選ぶ際に、待つ時間が長すぎるのも、選ぶのが早すぎるのも、どちらも最適な結果にはつながらないことを認識していました。数学の力を用いて、彼はシンプルなルールを導き出しました。それは、結婚相手候補の最初の37%を拒否し、次に「最適な」相手を選ぶというものです。彼の解決策は今日でも通用します。
^ ケッセルハイム, トーマス; ラドケ, クラウス; トニス, アンドレアス; ヴォッキング, ベルトルド (2013). 「重み付き二部マッチングのための最適オンラインアルゴリズムと組み合わせオークションへの拡張」.アルゴリズム – ESA 2013.コンピュータサイエンス講義ノート. 第8125巻. pp. 589– 600. doi :10.1007/978-3-642-40450-4_50. ISBN 978-3-642-40449-8。

参考文献

ベアデン, JN (2006). 「ランクベース選択とカーディナルペイオフを用いた新しい秘書問題」.数理心理学ジャーナル. 50 : 58–9 . doi :10.1016/j.jmp.2005.11.003.
Bearden, JN; Murphy, RO; Rapoport, A. (2005). 「秘書問題の多属性拡張：理論と実験」. Journal of Mathematical Psychology . 49 (5): 410– 425. CiteSeerX 10.1.1.497.6468 . doi :10.1016/j.jmp.2005.08.002. S2CID 9186039.
ベアデン, J. ニール; ラポポート, アムノン; マーフィー, ライアン O. (2006年9月). 「順位依存的報酬を伴う逐次観察と選択：実験的研究」.マネジメントサイエンス. 52 (9): 1437– 1449. doi :10.1287/mnsc.1060.0535.
Bruss, F. Thomas (2000年6月). 「オッズを合計して1にしたら終わり」. The Annals of Probability . 28 (3): 1384–139 1. doi : 10.1214/aop/1019160340 .
Bruss, F. Thomas (2003年10月). 「最適停止のオッズ定理の境界に関するノート」. The Annals of Probability . 31 (4): 1859– 1961. doi : 10.1214/aop/1068646368 . hdl : 2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/181669 .
Bruss, F. Thomas (1984年8月). 「選択肢数が未知である最良選択問題への統一的アプローチ」. The Annals of Probability . 12 (3): 882– 889. doi : 10.1214/aop/1176993237 .
フラッド、メリル・R. (1958). 「最適戦略の証明」. マーティン・ガードナー文書集第1巻、ボックス5、フォルダー19. マーティン・ガードナーへの手紙. スタンフォード大学アーカイブ.
フリーマン, PR (1983). 「秘書問題とその拡張：レビュー」.国際統計評論. 51 (2): 189– 206. doi :10.2307/1402748. JSTOR 1402748.
ガードナー、マーティン (1966). 「3. サイエンティフィック・アメリカン誌からの新しい数学的転換」サイモン＆シュスター社。[1960年2月に発表された彼のオリジナルのコラムを追加コメント付きで再掲載]
ギルダール、ヨゲシュ、デュデック、グレゴリー (2009). 「最適なオンラインデータサンプリング、あるいは最高の秘書を雇う方法」. 2009 Canadian Conference on Computer and Robot Vision . pp. 292– 298. CiteSeerX 10.1.1.161.41 . doi :10.1109/CRV.2009.30. ISBN 978-1-4244-4211-9. S2CID 2742443。
ギルバート, J; モステラー, F (1966). 「数列の最大値の認識」アメリカ統計学会誌. 61 (313): 35– 73. doi :10.2307/2283044. JSTOR 2283044.
グネディン, A. (1994). 「グーゴルゲームの解法」Annals of Probability . 22 (3): 1588–1595 . doi : 10.1214/aop/1176988613 .
Gnedin, A. (2021). 「ランダム到着における最善選択問題：1/e戦略に打ち勝つ方法」.確率過程とその応用. 145 : 226–240 . doi :10.1016/j.spa.2021.12.008. S2CID 245449000.
ヒル、TP「止め時を知る」アメリカン・サイエンティスト誌、第97巻、126-133ページ（2009年）。（フランス語訳はPour la Science誌（2009年）7月号の表紙記事をご覧ください。）
ケテラール、ティモシー、トッド、ピーター・M. (2001). 「思考の枠組み：進化心理学におけるフレーム問題への解答としての生態学的合理性」.進化心理学における概念的課題. 認知システム研究. 第27巻. pp. 179– 211. doi :10.1007/978-94-010-0618-7_7. ISBN 978-94-010-3890-4。
松井剛; 阿野健 (2016). 「多重停止を伴うBrussのオッズ問題の下限値」.オペレーションズ・リサーチ数学. 41 (2): 700– 714. arXiv : 1204.5537 . doi :10.1287/moor.2015.0748. S2CID 31778896.
ミラー、ジェフリー・F. (2001). 『交配の心：性選択が人間性の進化をどう形作ったか』アンカー・ブックス. ISBN 978-0-385-49517-2。
サルデリス, ディミトリス A.; ヴァラハス, テオドロス M. (1999年3月). 「意思決定：黄金律」.アメリカ数学月刊誌. 106 (3): 215. doi :10.2307/2589677. JSTOR 2589677.
シール, DA; ラポポート, A. (1997). 「相対的順位を用いた逐次的意思決定：『秘書問題』の実験的研究」「組織行動と人間の意思決定プロセス.69 ( 3): 221–236.doi : 10.1006 /obhd.1997.2683.
Stein, WE; Seale, DA; Rapoport, A. (2003). 「最善選択問題に対するヒューリスティック解の分析」. European Journal of Operational Research . 151 : 140–152 . doi :10.1016/S0377-2217(02)00601-X.
Vanderbei, RJ (1980年11月). 「母集団のサブセットの最適選択」.オペレーションズ・リサーチ数学. 5 (4): 481– 486. doi :10.1287/moor.5.4.481.
Vanderbei, Robert J. (2012). 秘書問題のポスドク版(PDF) (レポート). CiteSeerX 10.1.1.366.1718 .

外部リンク

OEISシーケンスA054404（n人の娘がいるスルタンの持参金問題において、選ぶ前に待つべき娘の数）
ワイスタイン、エリック・W.「スルタンの持参金問題」。MathWorld。
ニール・ベアデン. 「最適探索（秘書問題）」. 2017年1月4日時点のオリジナルよりアーカイブ。
トーマス・S・ファーガソン著『最適停止とその応用』

注記

numpyをnpとしてインポートし、 pandasをpdとしてインポートします。   
   

# 最大値を求める関数を定義します。def 
func ( r , n ) : if r == 1 : return 0 else : return ( r - 1 ) / n * np . sum ([ 1 / ( i - 1 ) for i in range ( r , n + 1 )])  
       
         
    
                          

# 特定のnについて問題を解く関数を定義する
def solve ( n ): values = [ func ( r , n ) for r in range ( 1 , n + 1 )] r_max = np . argmax ( values ) + 1 return r_max , values [ r_max - 1 ] 
              
        
        


# 結果をMarkdownテーブルとして出力する関数を定義します。def print_table ( data ): df = pd.DataFrame ( data , columns = [ " r" , " Max Value" ], index = range ( 1 , len ( data ) + 1 )) df.index.name = " n " 
            
      

    # DataFrame を Markdown に変換して印刷します。print 
    ( df . transpose ( ) . to_markdown ())


n_max  =  10

# n が 1 から n_max までのテーブルを印刷します
。data  =  [ solve ( n )  for  n  in  range ( 1 ,  n_max  +  1 )] 
print_table ( data )