最良選択問題の諸相 - 秘書問題とその周辺 -

シリーズ 情報科学における確率モデル 10

最良選択問題の諸相 - 秘書問題とその周辺 -

最適な採用決定のためのいわゆる秘書問題に関する確率モデルとその周辺についての解説書。

ジャンル
発行年月日
2023/07/12
判型
A5
ページ数
270ページ
ISBN
978-4-339-02840-9
最良選択問題の諸相 - 秘書問題とその周辺 -
在庫あり
2営業日以内に出荷致します。

定価

4,510(本体4,100円+税)

カートに入れる

電子版を購入

購入案内

  • 内容紹介
  • まえがき
  • 目次
  • レビュー
  • 著者紹介
  • 広告掲載情報

【書籍の特徴】
本書は秘書問題の中で重要な位置を占める最良選択問題を中心に分かりやすく解説する。厳密な理論展開というよりは直感的理解を重んじた記述になっているので、理系学部で学ぶ微分積分と応用確率論の知識があれば十分読みすすむことができる。

【各章について】
1章「秘書問題の主要モデル」:最適化基準と利用可能な情報の組合せからなる四つの問題,すなわち無情報型最良選択問題,無情報型順位最小化問題,完全情報型最良選択問題,完全情報型順位最小化問題を紹介する。
2章「無情報型最良選択問題の展開」:無情報型最良選択問題の多方面への一般化を試みる。
3章「無情報型順位最小化問題の展開」:無情報型順位最小化問題に関係する変形モデルをいくつか紹介する。
4章「Sum–the–odds定理とその展開」:Sum–the–odds定理も無情報型最良選択問題の一般化と考えられるが,1–sla(1–stage look–ahead)ルールとの関係から興味深い応用につながる。
5章「Fergusonの秘書問題」:Fergusonの秘書問題は秘書問題のルーツといえる数当てゲームのグーゴル(Googol)と深く関係している。
6章「出現数が未知の場合の最良選択問題」:無情報型最良選択問題および完全情報型最良選択問題においては,応募者総数nは既知であった。本章では未知の場合への拡張を試みる。
7章「期間問題」:期間最大化という新しい最適化基準の下で秘書問題を考える。期間問題と最良選択問題の間の興味深い対応関係も示される。
8章「PPPとFIモデル」:秘書問題では,nを大きくしたときの特性値の挙動に大きな関心が寄せられるが,これを調べることは,完全情報型問題の場合は容易でない。この困難を克服する試みとして提案されたPPP(planar Poisson process)によるアプローチを紹介する。

【著者からのメッセージ】
本書を読んで秘書問題に関心を抱いた読者にはGilbert and Mosteller(1966)を薦める。この論文は、その後の発展の萌芽となったモデルを多く含み、今なおこの分野を目指す人の必読論文であり続けている。

【キーワード】
秘書問題 最良選択問題 順位最小化問題 期間問題 動的計画法 最適停止問題 グーゴル Sum–the–odds定理 1–slaルール PPP

期待利益の最大化あるいは期待損失の最小化というような明確な最適化基準の下で,対象とする確率過程の変化を逐次観測しながらどの時点で所与の行動をとるかを決定するのが確率最適化(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月
玉置光司

1. 秘書問題の主要モデル
1.1 秘書問題
1.2 無情報型モデル
 1.2.1 無情報型最良選択問題
 1.2.2 無情報型順位最小化問題
1.3 完全情報型モデル
 1.3.1 完全情報型最良選択問題
 1.3.2 完全情報型順位最小化問題

2. 無情報型最良選択問題の展開
2.1 拒否とリコール
 2.1.1 Petruccelliモデル
 2.1.2 もう一つの拒否モデル
2.2 候補者選択問題
 2.2.1 割引を考慮したNIBC
 2.2.2 坂口モデル
 2.2.3 1–slaルールの最適性
2.3 利得の一般化
 2.3.1 ベストあるいはセカンドベストの選択
 2.3.2 セカンドベストの選択
2.4 トレーニングサンプル付最良選択問題
 2.4.1 トレーニングサンプル
 2.4.2 漸近挙動

3. 無情報型順位最小化問題の展開
3.1 メモリの制限
 3.1.1 メモリサイズ
 3.1.2 メモリサイズ1のNIRM
 3.1.3 無限問題
3.2 NIRMの簡易ルール
 3.2.1 短縮型ルール
 3.2.2 漸近挙動とNHPP

4. Sum–the–odds定理とその展開
4.1 Sum–the–odds定理
4.2 Sum–the–odds定理の一般化
 4.2.1 独立でないベルヌーイ試行
 4.2.2 FIBCの一般化
4.3 Sum–the–multiplicative–odds定理

5. Fergusonの秘書問題
5.1 グーゴル
5.2 Fergusonの生成ルール
5.3 Gnedinの生成ルール

6. 出現数が未知の場合の最良選択問題
6.1 不確実性の導入
6.2 無情報型問題
 6.2.1 Presman and Soninモデル
 6.2.2 Samuel–Cahnモデル
 6.2.3 Brussの連続時間モデル
6.3 完全情報型問題
 6.3.1 Porosinskiモデル
 6.3.2 Samuel–Cahnモデル
6.4 Petruccelliの部分情報型最良選択問題
 6.4.1 PET
 6.4.2 PETとPORの奇妙な一致

7. 期間問題
7.1 応募者数が既知の期間問題
 7.1.1 無情報型期間問題
 7.1.2 完全情報型期間問題
7.2 応募者数が未知の無情報型期間問題
7.3 最良選択問題と期間問題の交互対応

8. PPPとFIモデル
8.1 PPP
8.2 FIBC
 8.2.1 最適ルール
 8.2.2 成功確率
8.3 PETとFIBC
 8.3.1 最適ルール
 8.3.2 成功確率
8.4 PORとFIBC
 8.4.1 最適ルール
 8.4.2 成功確率

付録
A.1 マルチンゲール停止定理
A.2 単調ルールの下での期待利得
引用・参考文献
あとがき
索引

読者モニターレビュー【 N/M 様 (ご専門:総合情報学(情報科学) )】

本書は,「シリーズ 情報科学における確率モデル」(全18巻)の10巻目に位置する書籍である.本巻では「最良選択問題の諸相(しょそう)(=いろいろな姿,様子の意)」ということで,その中でも秘書問題 (Secretary Problem) とその周辺という応用(秘書問題の条件を拡張させたもの)についての詳細な記述がなされている.

前提知識としては,大学の学部レベルの微分積分学,確率論の知識がないと,数式を読み解くことが困難かと思われる.なお,刊行のことばにも記載されている通り『初学者を対象とした教科書というよりも,各分野の体系を網羅的に著した専門書の色彩が強い』ため,本書の内容を詳細には言及できないことを予め断っておく.

1章では,秘書問題とはそもそも何なのかについての解説があった後,秘書問題自身は,状況設定を用いた特別な最適停止問題だということ,古典的な秘書問題の構成要素を列挙し,それらを応用(拡張)していくと,4つのタイプの問題に分けられることが述べられている.それらの4つのタイプ問題をそれぞれ定義して証明するところまでが,この章で解説されている.

2章以降では,1章で分類した問題をそれぞれ展開した事項や,それらを拡張した応用について,詳細に述べられている.

最後に,本書には引用・参考文献が洋書・和書の論文や書籍が103本も紹介されており,これらの文献にあたることで,秘書問題をより網羅的に学べるだろうと思われる.

〔なお,余談だが,本読者モニタに応募する前に予め「秘書問題」とWebで検索した際に「結婚問題」,「お見合い問題」とも呼ばれていることから,『情報科学のための離散数学』(Ref: https://www.coronasha.co.jp/np/isbn/9784339023299/)のグラフ理論の応用で出てくる「結婚問題」のことだと勘違いしていた・・・〕

レビュー,書籍紹介・書評掲載情報一覧

玉置 光司(タマキ ミツシ)

掲載日:2023/09/06

電子情報通信学会2023年ソサイエティ大会プログラム

掲載日:2023/09/05

人工知能学会誌「人工知能」2023年9月号

掲載日:2023/08/17

「数理科学」2023年9月号

掲載日:2023/07/01

電子情報通信学会誌2023年7月号

掲載日:2023/07/01

日本オペレーションズ・リサーチ学会誌「オペレーションズ・リサーチ」2023年7月号

掲載日:2023/05/17

情報処理学会誌「情報処理」2023年6月号広告

★特設サイトはこちらから★

シリーズ刊行のことば,シリーズラインアップ,著者一覧,書籍の特徴,目次,著者からのメッセージ,キーワードがご覧いただけます

https://www.coronasha.co.jp/stochasticmodels/