バリエーション: 基本報酬問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/24 18:52 UTC 版)
「秘書問題」の記事における「バリエーション: 基本報酬問題」の解説
最善の応募者を選択するというのは厳密すぎると思われる場合もある。むしろ、ベストでなくとも、なるべくよい人を雇えればよいという考え方もある。したがって、ベストでなくてもなるべくよい人を選択するほうがよい場合も考えられる。基本報酬問題 (cardinal payoff problem) は、面接者が誰かを採用しないと報酬が得られないとする派生問題である。 この問題をモデル化するため、 n {\displaystyle n} 人の応募者それぞれに [ 0 , 1 ] {\displaystyle [0,1]} で一様分布する独立かつ同一の分布の確率変数 X {\displaystyle X} で表される値が対応しているとする。上述の問題と同様、面接者は応募者がそれまでで最善かどうかをその場で判断し、採用するか否かを決める。最後の応募者まで到達したら、その人を必ず採用することになる。話を単純化するため、面接者は応募者の相対順位を知らず、単に候補者かどうか（それまでの最善かどうか）だけを知るものとする。面接者はこのバージョンでは、採用した人の「価値」に応じて報酬を得る。例えば、採用された人の値が 0.8 なら、0.8 の報酬を受ける。面接者の目的は、採用者の期待値を最大化することである。 応募者の価値は [ 0 , 1 ] {\displaystyle [0,1]} に一様分布する互いに独立な同一分布であるため、 t {\displaystyle t} 番目の応募者が x t = max { x 1 , x 2 , … , x t } {\displaystyle x_{t}=\max \left\{x_{1},x_{2},\ldots ,x_{t}\right\}} となる場合の期待値は次のようになる。 E t = E ( X t | I t = 1 ) = t t + 1 {\displaystyle E_{t}=E\left(X_{t}|I_{t}=1\right)={\frac {t}{t+1}}} 本来の秘書問題と同様、最適ポリシーにはしきい値があり、ここではそれを c {\displaystyle c} とする。面接者は c {\displaystyle c} 人目以降の候補者を採用すべきである。Bearden (2006)によれば、 c {\displaystyle c} は ⌊ n ⌋ {\displaystyle \lfloor {\sqrt {n}}\rfloor } または ⌈ n ⌉ {\displaystyle \lceil {\sqrt {n}}\rceil } である。実際、 n {\displaystyle n} 人の候補者で 1 ≤ c ≤ n {\displaystyle 1\leq c\leq n} の任意のしきい値について期待される報酬は次のようになる。 V n ( c ) = ∑ t = c n − 1 [ ∏ s = c t − 1 ( s − 1 s ) ] ( 1 t + 1 ) + [ ∏ s = c n − 1 ( s − 1 s ) ] 1 2 = 2 c n − c 2 + c − n 2 c 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}}} V n ( c ) {\displaystyle V_{n}(c)} を c {\displaystyle c} について微分すると ∂ V / ∂ c = ( − c 2 + n ) / ( 2 c 2 n ) {\displaystyle \partial V/\partial c=\left(-{c}^{\,2}+n\right)/\left(2{c}^{\,2}n\right)} となる。 c {\displaystyle c} の許容される値については常に ∂ 2 V / ∂ c 2 < 0 {\displaystyle \partial ^{\,2}V/\partial c^{\,2}<0} なので、 V {\displaystyle V} は c = n {\displaystyle c={\sqrt {n}}} のときに最大となることがわかる。 V {\displaystyle V} は c {\displaystyle c} の凸関数なので、最適な整数のしきい値は ⌊ n ⌋ {\displaystyle \lfloor {\sqrt {n}}\rfloor } か ⌈ n ⌉ {\displaystyle \lceil {\sqrt {n}}\rceil } のどちらかとなる。したがって、本来の秘書問題に比べて基本報酬問題ではスキップする人数が少ないことが多い。なお、これは近似解ではなく、全ての n {\displaystyle n} について成り立つ。
※この「バリエーション: 基本報酬問題」の解説は、「秘書問題」の解説の一部です。
「バリエーション: 基本報酬問題」を含む「秘書問題」の記事については、「秘書問題」の概要を参照ください。
- バリエーション: 基本報酬問題のページへのリンク
