科学技術と共に歩む

期待利益の最大化あるいは期待損失の最小化というような明確な最適化基準の下で，対象とする確率過程の変化を逐次観測しながらどの時点で所与の行動をとるかを決定するのが確率最適化（stochastic optimization）と呼ばれる問題である。その中でも，どのタイミングで観測を停止する（多くの場合，そのときの対象を選択して停止する）かを決める問題が最適停止問題（optimal stopping problem）であり，秘書問題（secretary problem）は秘書のポストを求めて出現する応募者の中から望ましい人を採用するという状況設定を用いた特殊な最適停止問題と考えられる。最適停止問題を解くことは一般に困難であるが，秘書問題はその特殊な構造の見返りとして実際に解くことができる問題も多く，そのエレガントな解が人々を引き付けてきた。

秘書問題の基本的な枠組みはつぎのように述べられる。秘書1人の採用に対して n 人の応募があり，採用者は応募者の能力を 1（最良）から n（最悪）まで順位（絶対順位）によって評価することができる。したがって，全員を一堂に集めて集団面接すれば容易にその中の最良を選ぶことができるが，応募者が毎時1人ずつランダムな順序で面接に臨む場合はどうなるか。この場合，採用者の利用可能な情報は応募者の相対順位（すでに面接をすませた人の中での順位）だけで，それに基づいて毎時採用か不採用（パス）かを決めなければならない。一度パスしたら後からは採用できない。また，最初のn−1 人をパスしたら最後の応募者を採用しなければならない。

最適化基準に関して二つのモデルを紹介しよう。最もよく知られたモデルはベスト（最良）をねらう問題である。この問題は自然対数の底e の逆数e^－1（≈0.368...）と関係している。すなわち，n が大きくなると，全体の約37%（≈e^−1 n）の応募者をパスし，その後に出現する最初の相対順位1の応募者を採用することが最適となる。また，この最適ルールの下で実際にベストが選ばれる確率もe^－1 に近づく（定理1.1）。Lindleyは，このモデルを最良の伴侶を選ぶ結婚問題に適用し，つぎのような具体例を挙げている。18歳から40歳までを適齢期と考える男性の最適選択ルールは，18 + (40−18) × 0.368 ≈ 26となることから，26歳までは観察するにとどめ，その後最初の相対順位1 の女性にプロポーズせよというものである。n = 40−18 = 22とみなし，これを大きな数と考えているようであるが，実際の出現数は22人とはかぎらない。このように出現数に不確実性がある場合は，むしろ6章で紹介するBrussの連続時間モデルのほうが適切と考えられる（定理6.7，系6.1）。両者は似た結果を与えるが，Brussモデルは出現数の不確実性に対して頑健性がある。

もう一つのモデルは選ばれた応募者の順位（の期待値）を最小にする問題である。n人の中の最良が順位1，そのつぎが順位2，...，最悪が順位 n であったから，これも適切な最適化基準と考えられる。このとき n が大きくなると，最適ルールの下で達成される期待順位はつぎの無限積
\prod_{j=1}^{\infty} (\frac{j+2}{j})^{\frac{1}{j+1}}
=(\frac{3}{1})^\frac{1}{2}(\frac{4}{2})^\frac{1}{3}(\frac{5}{3})^\frac{1}{4}
···≈3.869 5
に近づく。なんと，平均的に順位4以下の人を選ぶことができる（定理1.2）。最適ルールは少し複雑である。まず，全体の26%の応募者をパスする。その後，相対順位1の応募者が出現すればただちに採用するが，もし45%まで面接をつづけても該当者が出現しなければ，その後は相対順位1でも2でも早く出たほうを採用する。さらに，56%まで面接をつづけても該当者が出現しなければ，相対順位3以下まで基準を緩める。このように，最適ルールは時間の進行と共に採用基準を緩和する。

最初のモデルは最良選択（best choice，BC）問題と呼ばれ，2 番目のモデルは順位最小化（rank minimization，RM）問題と呼ばれる。最適化基準に従った分類である。利用可能な情報に従った分類も可能である。上に述べた二つのモデルでは，利用可能な情報は応募者の相対順位だけであった。このような問題を無情報型（no information，NI）と呼ぶ。この対極にあるのが完全情報型（full information，FI）と呼ばれる問題で，そこではk番目の応募者に付随する評価値X_k，1<=k<=nが観測され，それが利用可能な情報となる。通常，X1,...,Xnは区間(0,1)上で一様に分布する独立確率変数列と仮定される。完全情報型は無情報型より情報が多いので，採用者にとって（期待利得が大きい）ベターな決定が期待できる。

本書の構成は以下のようになっている。1 章では，最適化基準と利用可能な情報の組合せからなる四つの問題，すなわち無情報型最良選択問題，無情報型順位最小化問題，完全情報型最良選択問題，完全情報型順位最小化問題を紹介する。本書では，これらはしばしば英語の頭文字をとって，NIBC，NIRM，FIBC，FIRMと略記される。2 章では，NIBCの多方面への一般化を試みる。3 章では，NIRMに関係した変形モデルをいくつか紹介する。4 章のSum–the–odds定理も，NIBCの一般化と考えられるが，1–sla（1–stage look–ahead）ルールとの関係から興味深い応用につながる。5 章の問題はFergusonが提起した問題で，秘書問題のルーツといえる数当てゲームのグーゴル（Googol）と深く関係している（グーゴルについては，そこで改めて紹介する）。ここまでは応募者総数nを既知と仮定しているが，6 章では未知の場合への拡張を試みる。7 章では，期間最大化という新しい最適化基準の下で秘書問題を考える。期間最大化問題と最良選択問題の間の興味深い対応関係も示される。秘書問題では，nを大きくしたときの特性値の挙動に大きな関心が寄せられるが，これを調べることは，特に完全情報型問題の場合は容易ではない。8 章では，この困難を克服する試みとして提案されたPPP（planar Poisson process）によるアプローチを紹介する。これは，完全情報型の極限問題を平面ポアソン過程の上で考えようというものである。

秘書問題の歴史についてはFergusonに詳しい。それによれば，活字になった最初の秘書問題はScientific Americanに掲載されたGardnerのグーゴルに関する記事と考えられている。したがって，秘書問題は60年を超す歴史を有する。1960年代に入ると，Lindley，Dynkin， Chow， Moriguti，Robbins and Samuels，Gilbert and Mosteller，Dynkin and Yushkevitch など著名な研究者による重要な研究がつぎつぎと発表された。中でも特筆すべきは Gilbert and Mosteller で，この論文に含まれる多くのモデルはその後の発展の萌芽となり，いまなお，この分野を目指す人の必読論文でありつづけている。少し遅れるが，Chow, Robbins and Siegmund，DeGrootも最適停止の研究に大きな影響を与えた。

秘書問題のサーベイ論文としてはSamuels，Ferguson，Freemanが推奨される。坂口，玉置からは文献に関して若干の追加情報が得られる。研究集会の報告書としては，アメリカ数学会のContemporary Mathematics 125 (1992)やポーランドの数学会誌 Matematyka Stosowana（Mathematica Applicanda 44(1) (2016)）が参考になる。秘書問題に特化した本としては，Berezovskiy and Gnedinのロシア語本が知られている。Fergusonの電子テキスト“Optimal Stopping and Applications”は，広く最適停止問題を研究する人にとって格好のテキストである。この本は秘書問題にもスペースを割いていて，本書の執筆に際しても利用させていただいた。和書では最近，高木英明著「秘書問題入門」が出版された。豊富な計算例を通して秘書問題が体感できる。穴太克則著「タイミングの数理」も参考になる。

本書は厳密な理論展開というよりは直感的理解を重んじた記述になっている。したがって，読む上で高度な数学は必要とされない。理系学部で学ぶ微分積分と応用確率論の知識があれば十分である。ただし，結果の紹介にとどまる箇所が一部ある。本書を通して，多くの人に秘書問題の面白さを知っていただければ幸いである。

最後に，研究生活でお世話になった方々に謝意を表したい。筆者をこの分野に導いて下さった坂口実教授（大阪大学）に感謝いたします。前述の論文をご覧になれば，先生の秘書問題への強い思いが伝わってきます。Thomas Ferguson(UCLA)，Thomas Bruss(Universite Libre de Bruxelles)，Krzysztof Szajowski (Wroclaw University of Technology)，Vladimir Mazalov (Karelian Research Center of the Russian Academy of Science)の諸先生方の30 年を超えるご交誼に感謝いたします。この中の3 氏とは共同研究の機会にも恵まれました。生前親しくご指導いただいた大野勝久先生（名古屋工業大学）の薫陶も忘れられません。しばしば有益なご助言をいただいた中井達先生（千葉大学）のご厚情にも感謝いたします。数値計算などでお世話になった友，太田拓男，浅倉史興，玉井清二，有澤健治の諸氏に改めてお礼申し上げます。ITに精通した王先生（長崎総合科学大学）の献身的支援に深く感謝いたします。遅筆の筆者に辛抱強くお付き合いただき，原稿のチェックと適切なご助言をいただいたコロナ社の皆様に厚くお礼申し上げます。最後に本書の執筆をおすすめいただいた編集委員長の土肥正教授（広島大学大学院）のご厚意と貴重なコメントに深甚なる謝意を表します。本書を父母に捧げる。

2023年5月
玉置光司