どこまでやるかに区切りをつける、最適停止問題


# はじめに
日常で、「どこまで調査して、どこで判断するのが良いのだろう」と考えたことはありませんか？
例えば、就職をするとき。
はじめての就職先が自分にとって、もっとも働きやすい場所かどうかは分かりません。一方で、他の会社でどんな働き方ができるかはその会社に入社してみないと分かりません。一方、入社をしてしまうと、前職には戻りにくくなってしまうところもあるでしょう。何社までを調査対象として、その後、値を張る会社を決めるのか、は悩ましい問題の一つでしょう。

いくつかの条件がそろえば、こうした問題については数理的に何社は様子を見るべき、という試算が可能です。
今回はそれを行う最適停止問題をご紹介します。

# 例題
以下のような例題を立てます。
* あなたは就職先を探しており、就職が可能な会社はA社~E社の5社しかありません。
* この5社のうち、最も自分にあった会社を探しています。今回は簡略化のために、最も自分に合っているとは、最も年収が高い会社である、とします。
* 年収は生涯変わりません。
* 会社に入社してみないと、その会社の年収は分かりません。
* 転職をすることができます。
* 転職元に再就職することはできません。

この例題の場合、転職をすることでしか、自分の年収を高める方法はありません。しかし、無暗に転職を繰り返すと、転職先の方が年収が低く、しかしもう元の会社には戻れない、という悪い結果を招いてしまう可能性もあります。
転職をしない方が良いのでしょうか、もしくは転職をする方が良いのでしょうか。もし転職すべきならば、何回転職を繰り返すべきなのでしょうか。

# 方法
順を追って計算していきます。
分かりやすくするために、各社の年収が以下と決まっていたとしましょう。ここでは、D社が最高の800万円ですね。もちろん、求職者はこの年収を入社するまで知ることができません。

|会社名|年収|
|----|----|
|A社|400万円|
|B社|500万円|
|C社|600万円|
|D社|800万円|
|E社|700万円|

## 転職をしない場合
A社~E社の会社のいずれかを選んで、新卒入社します。事前に年収は分からないのであてずっぽうで入社するしかありません。一番年収の高いD社を選択して入れる確率は5社のうちから1社を選ぶ確率ですので、$1/5$ですね。

## 転職をする場合
今回は、転職のやり方として
* 最初の何社かは年収の相場を知るために様子見をする。
* 様子見を終えてから転職を繰り返す
* 転職先が様子見してきた会社よりも年収がよかったら、その会社で永久に働くことにする。

このような戦略を取る際、何社、様子を見ればよいでしょうか。

### 1社、様子見する場合
上記の戦略を取る場合、どのようなケースで年収が最高の会社に入ることができるか、というと
「最高の年収の企業に転職するまでの過程で、一番年収の高かった会社が、様子見をした会社に含まれていること」となります。
少し難しいので順を追って、有り得る就職順のパターンを洗い出して解説します。
最高の年収の会社D社には、1社目～5社目のいずれかのタイミングで入社できます。すなわち、以下の箇条書きが発生する確率はそれぞれ$1/5$です。
* まず、1社目がD社だった場合、残念ですがこの会社は確実にやめてしまうため、D社に永久就職することはできません。
* 2社目がD社だった場合、様子見をした1社がどんな会社であったとしても、D社に永久就職することができます。
* 3社目がD社だった場合、D社に入社する前に入る2つの会社のうち、年収の高い方が1社目であれば、D社に入社することができます。例えばもし、A社->B社->D社、の順で転職した場合、B社に永久就職してしまいますが、A社B社のうち年収の高い会社を様子見できた場合、すなわちB社->A社->D社で就職をすると、D社に永久就職できます。この確率は2社のうちの1社を選ぶ確率ですから$1/2$となります。
* 4社目がD社の場合も同様です。先に体験する3社のうち、最も高い年収の会社を様子見できていれば、D社に就職することができます。この確率は$1/3$ですね。
* 5社目の場合も同様です。確率は$1/4$となります。

これらを合算すると、
|パターン|D社に永久就職する確率|
|----|----|
|1社目がD社|$0$|
|2社目がD社|$1/5\times1=1/5$|
|3社目がD社|$1/5\times1/2=1/10$|
|4社目がD社|$1/5\times1/3=1/15$|
|5社目がD社|$1/5\times1/4=1/20$|
|合計|$\frac{1}{5}+\frac{1}{10}+\frac{1}{15}+\frac{1}{20}=\frac{25}{60}\approx41.7％$|

ということで、もし、1社は様子見をする、という意思決定をする場合、41.7%の確率で一番高い年収の会社に就職することができます。

### 2~3社様子見する場合
1社様子見をする場合と同様に、2~3社様子見する場合も、同様に各パターンを洗い出すことで計算できます。（今回の記事では割愛します。）
|様子見をする会社数|D社に永久就職する確率|
|----|----|
|2社|$43.4％$|
|3社|$35％$|

### 4社様子見する場合
この場合は、最後の会社がD社である必要がありますから、転職しない場合と同様で、$1/5$の確率ですね。

# 結果
|様子見をする会社数|D社に永久就職する確率|
|----|----|
|0社（転職しない）|$20％$|
|1社|$41.7％$|
|2社|$43.4％$|
|3社|$35％$|
|4社（最後の会社に永久就職する）|$20％$|

という結果となりました、このケースでは2社様子を見た後、転職を繰り返すのが、一番年収の高い会社に就職できる確率が最も高い、という結論になりました。（一番期待値が高い、ということではありません。）

この、何社様子を見た場合に、どんな確率$P$になるかは、会社数を$n$と置き、様子見する会社数を$r$と置くと、以下のような数式で表すことができます。
$$P(r) = \frac{r}{n}\sum_{t=r+1}^{n}\frac{1}{t-1}$$

少し難しい式ですが、式の意味は今までやってきた計算をよく考えてみると、だんだんと理解できるかと思います。
この数式はnが大きな数になればなるほど$r=\frac{n}{e}$で最大値を迎えることが知られています。（今回の例でいうと、$見送る会社数r=\frac{5}{2.718...}\approx1.840$ということで、やはり2に近い設定がよさそうです)

# おわりに
今回は最適停止問題をご紹介いたしました。実際の現実問題でこれを使おうとすると
1. ふたを開けてみないと、どのくらい良いものか分からない
1. 次のふたを開けるためには、今の壺を捨てる必要がある
1. 最初から壺の数の上限が決まっていて、未来永劫壺は増えない

という状況でないと、正しく扱うことのできない戦略ではあります。特に3つ目の条件が厳しいですね。恋愛であったり、就職であったり、似たような条件のことはあるかもしれませんが、大抵無数ともいえる選択肢が用意されていて、かつその数は時事刻々と変化しています。
実際生きていく上での意思決定はやはりもっと複雑です。一方でナンの指針もなく考えすぎてしまうことによって時間が溶けるのもまた問題ですから、この $選択肢\times37％$ という計算方法は、覚えておいて損はないのではないでしょうか。

株式会社LOKIARでは、こうした業務の最適化を実現するための意思決定をサポートする物流コンサルティング、システム開発業務を承っております。ぜひお気軽にお問合せくださいませ。[物流について相談する](https://www.lokiar.com/contact)

また、弊社では開発にご助力いただける方を募集しています。
まずはカジュアルに情報交換させて頂ければと思いますので、
ぜひ[こちら](https://www.lokiar.com/recruite/entry)からお問い合わせください。