1　はじめに

　最適停止問題はいわば「最適タイミング」を求める問題であり，経済学，オペレーションズ・リサーチ，金融工学など，幅広い分野において応用される重要な問題である．最適停止問題の目的は大きく確率最大化と期待値最大化の2つに分けられる．その中で古典的秘書問題はよく知られた確率最大化問題であり，多数の拡張が考えられてきた．

　本論文では，古典的秘書問題の拡張として，有限期間にポアソン過程にしたがって到着する選択肢の中から最良の選択肢を選ぶ確率を最大にすることを目的とした，ポアソン到着最良選択問題について研究した．ポアソン到着問題は，期間内に到着する選択肢の数が未知であり，また到着時間も確率過程に従うという点において非常に現実的な拡張である．

　ポアソン過程の到着頻度に関するパラメータが未知で，その事前分布が自然数パラメータをもつガンマ分布である場合を考えた。まず，選択肢に関して相対的な順位のみが観測される場合(無情報問題)について最適停止規則を求めた．最適停止規則はある時刻までは観測するだけでそれ以降初めて候補が到着したとき停止するという閾値規則となる．次に，選択肢の価値が観測される場合(完全情報問題)について順位のみ観測される場合とは異なり，問題は単調ではなく，OLA停止規則が最適停止規則となるための十分条件を満たさないことを示した．

　また，経済学で研究されてきたオークションを最適停止問題のフレームワークでモデルを考えた．本論文では1人の入札者の最適戦略に注目し，よく知られている公開，競り上げ型のオークションと，複数の品物が出品される競り下げ型のオークションにおいていくつかの効用関数を設定した問題について最適停止規則を求めた．

2　ポアソン到着問題

　ポアソン過程にしたがって，選択肢が到着する．ポアソン過程のパラメータλの事前分布にパラメータの1つが自然数であるガンマ分布G(r,1/a),rは自然数，a>0を仮定する．所与の時刻Tまでに到着する選択肢の中で最良のものを選ぶ確率を最大にすることを考える．このとき，選択肢についての情報として，現在までに到着した中での順位のみ得られる場合(無情報問題)と価値が観測できる場合(完全情報問題)がある．ここで，i番目の選択肢が到着した時刻をsi，その相対ランク(今までに到着した中での順位)をXiと表す．

　現在の相対的ベストがすべての中でベストである確率と次に到着する相対的ベストがすべての中でベストである確率を比較し，現在のほうが小さくない場合には停止するというOLA(one-stagelook-ahead)停止規則を求め，その最適性を示す．OLA停止規則が最適であることを示すにはOLA停止領域がclosedであることを示せばよいことが知られている．

　ある時刻以降にはじめて到着した相対的ベストな選択肢を選ぶという戦略が，相対ランクのみ観測できる場合，最適であることを証明した．このような規則を閾値規則とよぶ．最適停止規則は次の定理で与えられる．

定理1　ポアソン過程のパラメータλの事前分布がガンマ分布G(r,1/a),rは自然数，a>0に従うとき，最適停止規則はsi(r)*以降に到着する最初の相対的ベストを選択する，である．すなわち，最適停止時刻τr*は

τr*=min{si∈[si(r)*,T]:Xi=1}.

si(r)*は

ただし，θ=(s+a)/(T+a)，の唯一解として定まり，iについての非増加列である．

また，閾値si(r)*の漸近的なふるまいについて次の定理が与えられる．

定理2

よく知られたように古典的秘書問題の最適停止時刻を特徴付ける閾値は十分大きな観測数nに対してn/eとなる．これは定理2においてλのガンマ事前分布のパラメータaをa=0として得られるT/eと比べると興味深い。

ガンマ分布G(r,1/a),r=3,4,5,10について閾値ti(r)*≡(si(r)*+a)/(T+a)を数値計算により求めた．結果は以下の表にまとめた．

　一方，選択肢の価値が観測できる場合について同様にポアソン過程のパラメータλの事前分布がガンマ分布G(r,1/a),rは自然数，a>oであるときを考える．一般性を失わないので価値xの分布は一様分布U(0,1)と仮定する．また，時刻sに到着したi番目の選択肢が相対的ベストであり，価値xである状態を(i,s,x)と表す．

この問題においてOLA停止領域は

ここで，b(s,x)≡(s+a)/{(T+a)x+(s+a)x}〓0,〓≡1-x.OLA停止領域はclosedではないことが示され，したがってOLA停止規則が最適停止規則となるための十分条件を満たさないことが証明された．

3　オークションヘの応用

　最適停止問題の応用として，経済学で研究されてきたオークションを最適停止問題のフレームワークで定式化して，解くことを考えた．本論文では，1人の入札者に注目し，その入札者の最適戦略を求めることが目的である．期待利得を最大にする目的で，いつオークションからおりるべきかを決定する最適停止規則を求めることになる．

　オークションの形式は，イングリッシュ・オークション，ダッチ・オークションなど名前がついているもの，具体的には価格が上昇するもの，あるいは下降するもの，落札価格が付け値の最高額である，あるいは2番目に高い額であるものなど，さまざまである．価格が上昇していく上昇オークションと，価格が下降していく下降オークションについてそれぞれ取り上げた．

　オークション参加者の1人にのみ注目して，ほかの参加者については注目した1人に対して情報を与える環境と仮定する．また，オークションは価格が単位時間に一定額変化(上昇あるいは下降)していくと仮定し，さらに一般性を失わないので，価格は0から単位時間に1変化すると考える．

上昇オークション

　まず，上昇オークションにおいて注目した参加者について最適停止戦略を考える。いくつかの効用関数の形を考え，それぞれについて最適戦略を求めた．オークション終了時刻Nが一様分布U[1,M]に従うことを仮定する．また，オークションの品物の価値については時間によらず一定の場合と，時間によって変化する場合を考えた．時刻i乞での損失関数と品物の価値をそれぞれl(i)とv(i)で表す．落札したとき時刻iで支払う金額はiであるので，効用関数は次のように表される．

R(i) =

-l(i)，時刻iでオークションをおりたとき

v(i) -i，時刻iで落札したとき

品物の価値が一定の場合

品物の価値が一定(v(i)=T,T

であり，最適停止領域である．つまり，最適停止規則はi〓(T-c-1-Mc)/(1-2c)となるはじめてのiでオークションからおりる，である．

品物の価値が時間により変化する場合

品物の価値が時間について線形(v(i)=vo+ui)であり，損失関数が線形(I(i)=ci)の場合，OLA停止領域は

B={(2c+u-1)i+(vo+u-Mc+c-1)〓0}.

2c+u-1<0のとき，βは最適停止領域である．つまり，i〓(vo+u-Mc+c-1)/(1-2c-u)となるはじめてのiで停止する，が最適停止規則である．

下降オークション

　下降オークションについては最高額Mから出発して，価格が下降していくものとする．時刻が1進むごとに価格が1単位ずつ下がっていくので，利得は1ずつ増える．また，時刻iでの利得関数は次のように表されるとする．

H(i)=

v+i，落札したとき

0，落札できなかったとき

上昇オークションの場合と同様に，オークション終了時刻Nが一様分布U[1,M]に従うことを仮定すると，OLA停止領域は

であり，これはclosedであり，最適停止領域となる．したがって，最適停止規則は

を満たす最小の整数iをi*とすると，i*で停止，つまり品物を買う，である．また，i*以前に品物が売り切れてしまった場合には手に入れられないことになる．

　次に，下降オークションにおいて同種の品物がいくつか出品されている場合について考えた．品物の残りの個数の情報が得られ，単位時間に売れる品物の個数が既知の平均λのポアソン分布に従うとすると，OLA停止領域は次のように表される．

ただし，(s,j)は時刻sで残りj個の状態を表す．Bはclosedであるので，最適停止領域である．よって，最適停止規則はv+s+1>0かつ(v+s)/(v+s+1)〓e-λΣj k=1λk/k!を満たす最初の(s,j)で停止する，である．

表1:r=3,4,5,10のときの閾値

　オペレーションズリサーチ、経済学、金融工学などの各分野に現れる重要な問題の一つとして、最適な停止タイミングを求める最適停止問題がある。本論文の前半では、離散時刻上の古典的ないわゆる秘書問題を、連続時間上のポアソン過程に従って選択肢が現れる場合に一般化した最適停止問題を扱っている。後半では、オークションにおけるひとりのプレーヤーの戦略を最適停止問題に定式化した問題を扱っている。そして、これらの様々な最適停止問題において、どのような問題においてOLA (One-Step Look-Ahead) 停止規則が最適停止規則となりうるかを明らかにし、さらにOLA 停止規則が最適停止規則である場合には、その最適停止時刻を計算するための方程式を導出して示している。

　第1章では、研究の背景と本研究に先行する諸結果が述べられている。

　選択肢の相対的順位のみしか分からない場合を無情報問題と呼ぶが、第2章では、この無情報下において選択肢がポアソン到着するとした最適停止問題が扱われている。この問題では、選択肢の生起が従うポアソン過程のパラメーターの事前分布が指数分布である場合について、Bruss (1987) によって、問題が単調でかつOLA 停止規則が最適停止規則になるという結果が示されている。本研究では、このBruss の古典的な結果を直接に一般化し、事前分布が一般のガンマ分布である場合においてもOLA 停止規則が最適停止規則を与えることを証明し、かつ最適停止時刻の満たす方程式を、計算、導出している。また、古典的秘書問題では選択時間の上限n に対する最適停止時刻s*の割合s*/n が、n→∞ のとき1/e に収束することはよく知られた事実であるが、これと全く相似な1/e 収束定理がこのポアソン到着における最適停止問題においても成立することが示されている。

　第3章では、選択肢の相対的順位だけでなくその絶対的価値を選択者が知ることができる完全情報問題の場合が扱われている。この最適停止問題が単調問題であると述べたSakaguchi (1989) の定理の証明には誤りがあることが広く知られていて、問題が単調であるかないかについては未解決であった。本研究では、この証明で欠落していた部分を補って、この場合の最適停止問題が、実は逆に、常に非単調になることを証明した。

　第4章では、オークションの入札者の最適停止問題を考察している。オークションの形式には様々なものがあるが、そのうち上昇オークション、下降オークションにおいて、最適停止領域を求め、最適停止規則を導出している。このとき、様々な効用関数、損失関数のそれぞれに対して最適停止規則を求め、それらを比較、考察している。

　以上、最適停止問題において本論文で示された研究結果は広汎かつ顕著な結果であり、特に第3章における停止問題の非単調性の証明は、この分野で他に類を見ない極めて斬新な結果である。このように、本研究は応用確率学の研究の展開に寄与するところ大であり、よって本審査委員会は、本論文が博士（学術）の学位を授与するにふさわしいものと認定する。