ランチ最適化問題(秘書問題編)

はじめに

日々の生活を営む上で、ランチをどこで食べるかということは非常に重要な問題です。

ランチの選択肢としては、新しい店に入る（探索）と、今まで行ったことのある店で良かった店に入る（活用）のどちらかを行う必要があります。経験的に良かった店に入るのは比較的高い満足度を得ることができますが、未知でより良い店が近くにあるのを見逃している可能性があります。逆に新規の店に入る場合、その店が良い場合もありますが、あまり良くない店であることもあります。

より良いランチライフを送るためにはこの探索と活用をどう振り分けたらよいのでしょうか？

今回は、この問題を一般的に秘書問題や結婚問題とよばれる最適停止問題で考えてみたいと思います。

秘書問題について

wikiを読むとわかりやすいですが、 秘書問題はn人の候補者から1人の最良の人物を採用したい場合、 最初の37%の候補者は取らずにその中での最良の人物を覚えておき、 それ以後にそれ以上の候補者が現れたらその人を採用することで37%の確率で最良の候補者を採用できるというものです。

この問題は現実問題として理解しやすいので数理モデルの入門書では頻出で37%という数字だけが強調されるのですが、この問題は下記のように比較的強い制約の元に成り立っています。

• 候補者全体の数が既知である
• 採用できるのは一人
• 最良の候補者しか考慮しない
• 候補者には順位がついており、単一指標で優劣を判定できる

現実問題に置き換える場合、これらの条件を少し変化させる場合があると思いますので、 いろいろ条件を変えた時にこの37%という値はどう変化するのかを数値シミュレーションで確認していこうと思います。

実装

以下のサイトのコードを参考に数値シミュレーションを実装します。
https://imrankhan17.github.io/pages/Solving%20the%20secretary%20problem%20with%20Python.html

以下の4ケースの実験を行います。
1. 1位の店が選ばれる最適点(一般的な秘書問題)
2. n位以内の店が選ばれる最適点
3. 複数店舗選ぶ場合に最適な店が含まれる最適点
4. 複数店舗選ぶ場合の合計値の最適点

コードは上記サイトのものを少し変更しただけなのでここでは結果だけを載せていきます。

1位の店が選ばれる最適点(一般的な秘書問題)

横軸が探索と活用の切り替え点、縦軸が1位の店が選ばれる確率になります。 セオリー通り横軸も縦軸も約37%である点が最適となります。

n位以内の店が選ばれる最適点

１位に限定せずn位以内の店が選択できれば良いという場合です。 nが1,2,5,10の場合を示します。

nが大きくなると探索を打ち切る点が左にずれ、またn位以内の店が選ばれる確率は上がります。 もし10位以内でよければ15%くらいで打ち切るのが最も確率が良くなります。

複数店舗選ぶ場合に最良な店が含まれる最適点

１店ではなく複数店舗を選択することができ、その中で１位の店が選ばれる場合です。 選択できる店舗数が1,2,5,10である場合の結果を示します。

(私のコードが間違っていなければ)グラフは先ほどとかなり近しいものになりました。 選べる店舗数が増えるにつれて最適点は左上にずれていきます。

5店舗選ぶ場合の合計値の最適点

最後に5店舗選択し、その合計値が少ない、つまり選んだ5店舗が全体的に最適となる点を探します。 5店舗の順位の合計値が20,30,40,50以下となる場合の確率を示します。

順位の合計が20以下であって欲しい場合は15%前後、30-50の場合は10%前後で探索を打ち切るのが良さそうです。 この条件で良い場合は早めに打ち切るのが良さそうです。 例えば順位合計値30以下という条件で3ヶ月以内(90日)に５店を決定したいとなると、9日探索を行い、それ以後の81日の活用の際に探索時の最適店より良い店を採用していくのが最適解となります。それなりに良い店舗を5店選択することができれば快適な１週間のランチローテが組めそうですね。

メモ

• 心理学の実験では人はアルゴリズムの出す閾値よりも早く判断を下すという結果も出ているみたいだが、 仮定の違いが原因で、実際は上位10%がとれればいいやくらいの感覚で人事採用をするので探索の打ち切り点が早めになってしまっているのではという可能性もあると思った。
• 途中で思ったが実際はランチ店探しは後戻り可能なので課題設定としてはあまり適しておらず、これを解きたいならバンディットアルゴリズムとかを使った方がいいんじゃないかと思った(次回)。

使用したコードは以下になります。 github.com