秘書問題

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

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

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

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

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

候補者とは、面接時に、それまでに面接したすべての応募者よりも優れている応募者と定義されます。Skipは、「面接後すぐに拒否する」という意味で使用されます。問題の目的は、最も優れた応募者を 1 人選ぶことであるため、受け入れ対象は候補者のみとなります。このコンテキストでの「候補者」は、順列のレコードの概念に対応します。

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

${\displaystyle {\begin{aligned}P(r)&=\sum _{i=1}^{n}P\left({\text{応募者 }}i{\text{ が選択される}}\cap {\text{応募者 }}i{\text{ が最良}}\right)\\&=\sum _{i=1}^{n}P\left({\text{応募者 }}i{\text{ が選択される}}|{\text{応募者 }}i{\text{ が最良}}\right)\cdot P\left({\text{応募者 }}i{\text{ が最良}}\right)\\&=\left[\sum _{i=1}^{r-1}0+\sum _{i=r}^{n}P\left(\left.{\begin{array}{l}{\text{最初の }}i-1 のベスト}}i-1{\text{応募者}}\\{\text{は最初の }}r-1{\text{ 応募者}}\end{配列}}\right|{\text{応募者 }}i{\text{ は最適}}\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として使用すると、合計は次の積分で近似できます。 ${\displaystyle x}$

${\displaystyle 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で選択されます。 ${\displaystyle x}$

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

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

この問題といくつかの修正は、オッズアルゴリズムによって簡単に解決できます (最適性の証明を含む) 。このアルゴリズムは他の用途もあります。このアルゴリズムによって解決できる秘書問題の修正には、応募者のランダムな可用性、意思決定者の関心を引く応募者に関するより一般的な仮説、応募者に対するグループ面接、およびランダムな数の応募者に対する特定のモデルが含まれます。^{[引用が必要]}

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

古典的な秘書問題の解決法の応用における 1 つの重要な欠点は、応募者の数を事前に知っていなければならないことですが、これはめったに起こりません。この問題を克服する 1 つの方法は、応募者の数がの既知の分布を持つ ランダム変数であると仮定することです (Presman および Sonin、1972)。ただし、このモデルでは、最適な解決法は一般にはるかに困難です。さらに、最適な成功確率は 1/ e付近ではなく、通常はそれより低くなります。これは、応募者の数がわからないことに対する「代償」があるという文脈で理解できます。ただし、このモデルでは代償は高いです。 の分布の選択に応じて、最適な当選確率はゼロに近づく可能性があります。この新しい問題に対処する方法を探すことで、いわゆる 1/e 法則に基づく新しいモデルが生まれました。 ${\displaystyle n}$${\displaystyle N}$${\displaystyle P(N=k)_{k=1,2,\cdots}}$${\displaystyle N}$

このモデルの本質は、人生は連続的であり、現実世界の問題はリアルタイムで発生するという考えに基づいています。また、特定のイベント (応募者の到着) がより頻繁に発生する時期 (発生する場合) を予測する方が、発生する特定のイベントの数の分布を予測するよりも簡単です。この考えから、次のようなアプローチ、いわゆる統一アプローチ(1984) が生まれました。

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

${\displaystyle F(t)=\int _{0}^{t}f(s)ds}$、。${\displaystyle \,0\leq t\leq T}$

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

1/e戦略

（i）は、すべての成功確率が少なくとも1/eとなる。${\displaystyle N}$

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

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

1984 年にF. Thomas Brussによって証明された 1/e 法則は驚きでした。その理由は、約 1/e の値は、未知のモデルでは以前は達成不可能であると考えられていたのに対し、この値 1/e は成功確率の下限として達成され、これはおそらくはるかに弱い仮説を持つモデルで達成されたためです (たとえば、Math. Reviews 85:m を参照)。 ${\displaystyle N}$

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

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

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

誰かに好きなだけ紙切れを取ってもらい、それぞれの紙切れに異なる正の数を書いてもらいます。その数は 1 の小さな分数から 1 グーゴル( 1 の後に 100 個のゼロが続く) またはそれ以上の大きさまでの範囲です。これらの紙切れは裏返しにされ、テーブルの上でシャッフルされます。1 枚ずつ紙切れを表向きにします。一連の紙切れの中で最大と思われる数に達したら、めくるのをやめます。戻って以前にめくった紙切れを取ることはできません。すべての紙切れをめくったら、もちろん最後にめくった紙切れを取らなければなりません。^[5]

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

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

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

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

アリスはまず n 個の数字を書き、それをシャッフルします。したがって、数字の順序は重要ではありません。つまり、アリスの数字は交換可能なランダム変数シーケンス である必要があります。アリスの戦略は、最もトリッキーな交換可能なランダム変数シーケンスを選択することです。 ${\displaystyle X_{1},X_{2},...,X_{n}}$

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

ボブに対する停止規則が の相対ランクのみに依存し、その数値には依存しない場合、その規則は相対ランク停止戦略であると言えます。言い換えれば、アリスが数字を選んだ後に誰かが密かに介入し、 の各数字をその相対ランクに変更した（同順位の場合はランダムに変更した）ようなものです。たとえば、 はまたはに等確率で変更されます。これは、アリスが に対して交換可能なランダム順列を実行したかのようになります。ここで、 に対する交換可能なランダム順列は上のすべての順列に対する一様分布のみであるため、最適な相対ランク停止戦略は、上記の秘書問題に対する勝利確率が である最適な停止規則です。アリスの目標は、ボブが相対ランク停止戦略よりも良い結果を出せないようにすることです。 ${\displaystyle \tau}$${\displaystyle X_{1},X_{2},...,X_{n}}$${\displaystyle X_{1},X_{2},...,X_{n}}$${\displaystyle 0.2,0.3,0.3,0.1}$${\displaystyle 2,3,4,1}$${\displaystyle 2,4,3,1}$${\displaystyle \{1,2,...,n\}}$${\displaystyle \{1,2,...,n\}}$${\displaystyle \{1,2,...,n\}}$$${\displaystyle 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 番目の数字も自信を持って選ぶことができます。アリスは、が正の相関関係にある を選ぶことで、成績を伸ばすことができます。${\displaystyle n=2}$${\displaystyle N(0,1)}$${\displaystyle -3}$${\displaystyle +3}$${\displaystyle X_{1},X_{2}}$

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

任意の停止規則に対して、 となるような、交換可能なランダム変数のシーケンスは存在しますか?${\displaystyle X_{1},...,X_{n}}$${\displaystyle \tau}$$${\displaystyle 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 で勝ちます。 ${\displaystyle n=2}$${\displaystyle Y}$${\displaystyle X_{1}>Y}$${\displaystyle X_{1}}$${\displaystyle X_{2}}$${\displaystyle Y\not \in [\min(X_{1},X_{2}),\max(X_{1},X_{2})]}$${\displaystyle Y\in [\min(X_{1},X_{2}),\max(X_{1},X_{2})]}$

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

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

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

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

Stein、Seale、Rapoport 2003 は、秘書問題で採用される可能性のあるいくつかの心理学的に妥当なヒューリスティックの期待成功確率を導き出しました。彼らが調査したヒューリスティックは次のとおりです。

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

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

最も優秀な応募者を 1 人見つけるというのは、かなり厳しい目標のように思えるかもしれません。面接官は、最も優秀な応募者を獲得することだけに関心があるのではなく、価値の低い応募者よりも価値の高い応募者を採用したいと考えるだろうと想像できます。つまり、面接官は必ずしも最優秀ではない応募者を選択することで何らかの価値を引き出し、その価値は選択した応募者の価値に応じて増大します。

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

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

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

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

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

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

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

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

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

一つの変種は、最善のものを選びたいという欲求を、次善のものを選びたいという欲求に置き換える。^{[13] [14] [15]} ロバート・J・ヴァンダーベイはこれを「ポスドク」問題と呼び、「最善のもの」はハーバードに行くと主張している。この問題では、偶数人の応募者の場合の合格確率はちょうど である。この確率は n が無限大に近づくにつれて 1/4 に近づき、最善のものを選ぶ方が次善のものを選ぶよりも簡単であるという事実を示している。 ${\displaystyle {\frac {0.25n^{2}}{n(n-1)}}}$

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

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

このバリエーションでは、プレイヤーは選択を許可され、いずれかの選択が最善であれば勝ちます。この問題の最適な戦略は、しきい値の集合によって定義される戦略のクラスに属します。ここで、 です。 ${\displaystyle r}$${\displaystyle (a_{1},a_{2},...,a_{r})}$${\displaystyle a_{1}>a_{2}>\cdots >a_{r}}$

具体的には、からまでとラベル付けされた合格通知があるとします。応募担当者がいて、それぞれが 1 通の通知を持っています。 応募者を面接し続け、応募担当者全員が見ることができる表で候補者をランク付けします。 担当者は、 から までのすべての候補者よりも優れている最初の候補者に合格通知を送ります。(送信されなかった合格通知は、標準的な秘書問題と同じように、デフォルトで最後の応募者に渡されます。) ^[17]${\displaystyle r}$${\displaystyle 1}$${\displaystyle r}$${\displaystyle r}$${\displaystyle i}$${\displaystyle 1}$${\displaystyle a_{i}}$

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

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

^[17]まで計算したが、 であった。 ${\displaystyle r=4}$${\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}}$

Matsui & Ano 2016 は一般的なアルゴリズムを示しました。たとえば、。 ${\displaystyle 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年に独立して同等の問題を思いついた。彼らはそれを「グーゴルのゲーム」と呼んだ。フォックスとマーニーは最適解を知らなかった。ガードナーはレオ・モーザーに助言を求めた。モーザーは（JR・パウンダーとともに）雑誌に掲載するための正しい分析を提供した。その後すぐに、数人の数学者がガードナーに手紙を書いて、噂で聞いた同等の問題を伝えたが、そのすべてはフラッドの元の研究に遡る可能性が高い。^[25]

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

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

秘書問題は、複数の異なる仕事がある場合に一般化できます。この場合も、応募者はランダムな順序でやって来ます。応募者が来ると、負でない数字のセットを提示します。各値は、いずれかの仕事に対する応募者の資格を指定します。管理者は、応募者を採用するかどうかを決定するだけでなく、採用する場合は、応募者をいずれかの仕事に永久に割り当てる必要があります。目的は、資格の合計が可能な限り大きくなる割り当てを見つけることです。この問題は、片側のノードがランダムな順序でオンラインになる、エッジ重み付けされた 2 部グラフで最大重みマッチングを見つけることと同じです。したがって、これはオンライン 2 部マッチング問題の特殊なケースです。 ${\displaystyle n}$${\displaystyle n}$

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

• 割り当て問題
• オッズアルゴリズム
• 最適な停止
• ロビンズの問題
• 検索理論
• 安定した結婚生活の問題

• Bearden, JN (2006). 「ランクベースの選択とカーディナルペイオフによる新しい秘書問題」。数学心理学ジャーナル。50 :58–9。doi : 10.1016 /j.jmp.2005.11.003。
• Bearden, JN; Murphy, RO; Rapoport, A. (2005). 「秘書問題の多属性拡張: 理論と実験」.数学心理学ジャーナル. 49 (5): 410–425. CiteSeerX  10.1.1.497.6468 . doi :10.1016/j.jmp.2005.08.002. S2CID  9186039.
• Bearden, J. Neil; Rapoport, Amnon; Murphy, Ryan O. (2006年9 月)。「順位依存の報酬による順次観察と選択: 実験的研究」。経営科学。52 ( 9): 1437–1449。doi :10.1287/mnsc.1060.0535。
• Bruss, F. Thomas (2000 年 6 月)。「オッズを 1 に合計して停止する」。確率年報。28 (3): 1384–139 ​​1。doi : 10.1214/ aop /1019160340。
• Bruss, F. Thomas (2003 年 10 月)。「最適停止のオッズ定理の境界に関する注記」。確率年報。31 (4): 1859–1961。doi : 10.1214/ aop /1068646368。
• Bruss, F. Thomas (1984年8 月)。「選択肢の数が不明な最良選択問題に対する統一的アプローチ」。確率年報。12 (3): 882–889。doi : 10.1214/aop/1176993237。
• フラッド、メリル R. (1958)。「最適戦略の証明」。マーティン ガードナーへの手紙。マーティン ガードナー文書シリーズ 1、ボックス 5、フォルダー 19: スタンフォード大学アーカイブ。{{cite press release}}: CS1 maint: location (link)
• Freeman, PR (1983). 「秘書問題とその拡張: レビュー」.国際統計評論 / Revue Internationale de Statistique . 51 (2): 189–206. doi :10.2307/1402748. JSTOR  1402748.
• ガードナー、マーティン (1966)。「3」。サイエンティフィック・アメリカンからの新しい数学的転換。サイモン・アンド・シュスター。[1960年2月に発表された彼のオリジナルのコラムを追加コメント付きで再録]
• Girdhar, Yogesh; Dudek, Gregory ( 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。
• Gilbert, J; Mosteller, F (1966). 「シーケンスの最大値の認識」アメリカ統計学会誌. 61 (313): 35–73. doi :10.2307/2283044. JSTOR  2283044.
• Gnedin, 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月号の表紙記事をご覧ください）
• Ketelaar, Timothy; Todd, Peter M. (2001)。「思考の枠組み: 進化心理学の枠組み問題に対する答えとしての生態学的合理性」。進化心理学における概念的課題。認知システム研究。第 27 巻。pp. 179–211。doi : 10.1007 /978-94-010-0618-7_7。ISBN 978-94-010-3890-4。
• Matsui, T; Ano, K (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。
• Sardelis, Dimitris A.; Valahas, Theodoros M. (1999 年3月)。「意思決定: 黄金律」。アメリカ数学月刊誌。106 (3): 215。doi :10.2307/2589677。JSTOR  2589677。
• Seale, DA; Rapoport, 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 人の娘がいるスルタンの持参金問題で選択する前に待つべき娘の数)
• Weisstein、Eric W.「スルタンの持参金問題」。MathWorld。
• ニール・ベアデン。「最適探索（秘書問題）」。2017年1月4日時点のオリジナルよりアーカイブ。
• Thomas S. Ferguson 著「Optimal Stopping and Applications」