職員採用問題；表から見るか、裏から見るか？
まずタイトルですが表から見るか、裏から見るか？というのはこの問題を応募する側（裏側）から見た問題設定がないから新しい視点ということでこのタイトルにしました。応募者から見た最適停止問題、というのを後半で考えてみます。
雇用者からみた場合
秘書問題、お見合い問題と呼ばれる問題があります。X(旧Twitter)でもアンケートをとったんですが下記のような問題です。
院長として職員募集、面接に来た方はトライアル雇用1ヶ月後に採用/不採用を決定します。不採用の場合は次の面接、トライアル雇用に進みます。最大10人面接する予定。最初のr人は必ず不採用としそのr人の中でもっともよかった人より良い人が来たときに採用する戦略の場合に最適なnの数は？
Xは140文字以内という制限があるのでわかりにくいのでもう少しわかりやすく書いてみます。
問題文：
あなたは病院の院長で、新しい職員を募集しています。募集プロセスでは、応募者全員に面接を行い、その後選ばれた応募者には1ヶ月のトライアル雇用期間を経て、正式な採用か不採用の判断を下します。以下の条件があります：
面接プロセス：あなたは最大で10人の応募者を面接することができます。
トライアル雇用期間：面接後、応募者は1ヶ月間のトライアル雇用期間に入ります。この期間終了後、その応募者を正式に採用するかどうかを決定します。
不採用の場合：もし応募者が不採用の場合、次の応募者の面接とトライアル雇用に進みます。
採用戦略：あなたは、最初に面接したr人の応募者を必ず不採用にします。しかし、これらr人の中で最も評価が高かった応募者よりも優れた応募者がその後に現れた場合、その応募者を採用します。
目的： この採用戦略を踏まえ、最適なr（最初に不採用にする応募者の数）を決定することです。つまり、最も優れた応募者を採用する可能性を最大化するrの値を見つけることが求められます。
制約条件：
応募者は最大10人まで面接することができます。
最初のr人の応募者は必ず不採用とします。このrは1以上10未満の整数でなければなりません（全員を不採用にするわけにはいかず、最低1人は採用の機会が必要です）。
r人の応募者を評価した後、それらの中で最も優れていた応募者よりも優れた次の応募者が現れた場合にのみ採用を決定します。
応募者の評価は比較可能であり、互いに優劣をつけることができます。
わかりにくいところもあるので図解してみます。
この図では応募者の能力を10段階に分けています、最初の3人は見送る（r=3）、その後その3人よりもよい候補者が来た場合に採用（上図では5番目、青大X）となります。実際に最も能力が高い候補者は8番目に来ています（上図では赤X）。このケースでは最も良い候補者を選ぶのに失敗してます。
import numpy as np
import matplotlib.pyplot as plt
# Set the number of candidates and the observation phase end
num_candidates = 10
observation_phase_end = 3 # Example value, replace with optimal stopping rule if needed
# Generate unique abilities for each candidate to ensure no duplicates
unique_abilities = np.random.permutation(np.arange(1, num_candidates + 1))
# Determine the best candidate during the observation phase with unique abilities
best_during_observation_unique = max(unique_abilities[:observation_phase_end])
# Identify the selected candidate and the most able candidate
selected_candidate_index = None
most_able_candidate_index = np.argmax(unique_abilities) + 1 # Adding 1 for 1-based indexing in plotting
for i, ability in enumerate(unique_abilities[observation_phase_end:], start=observation_phase_end + 1):
if ability > best_during_observation_unique:
selected_candidate_index = i
break
# Re-plot with the selected and most able candidates highlighted
fig, ax = plt.subplots()
# Plot the observation phase again
ax.axvspan(0, observation_phase_end, color="yellow", alpha=0.3, label="Observation Phase")
ax.axvline(observation_phase_end, color="red", linestyle="--", label="Optimal Stopping Point")
# Color candidates based on their potential to be chosen
for i, ability in enumerate(unique_abilities, start=1):
if i <= observation_phase_end:
ax.scatter(i, ability, color="grey")
elif ability > best_during_observation_unique:
ax.scatter(i, ability, color="green")
else:
ax.scatter(i, ability, color="blue")
# Highlight the selected candidate if one was chosen
if selected_candidate_index is not None:
ax.scatter(selected_candidate_index, unique_abilities[selected_candidate_index - 1], color="blue", s=200, edgecolors="blue", linewidth=2, label="Selected Candidate")
# Highlight the most able candidate
ax.scatter(most_able_candidate_index, unique_abilities[most_able_candidate_index - 1], color="
このときrをいくらに設定すれば最も良い候補者（上図でAbilityが最も高い候補者）を選択できるのか？という問題です。
解答：
解答はネットで検索するといたるところに出てきますので簡単にします、理解で躓きそうなところを少し詳しくしてみます。この問題の目的は、最も優れた候補者を選択する戦略を見つけることです。最適な戦略は、最初のいくつかの候補者を単に観察するためにスキップし、その後、以前に面接した候補者よりも優れている最初の候補者を選択することです。
この問題の解決策は、まず最初の$${\frac{n}{e}}$$候補者を見送り（ただし$${e}$$は自然対数の底、約2.71828）、その後に初めて出現する、これまでの候補者よりも優れた候補者を選択することです。こうすることで、最適な候補者を選択する確率が最大になります。数学的には、最適な選択確率は約$${\frac{1}{e}}$$に収束し、これは約36.8%です。
詳細な数学的説明は以下のとおりです。
まず、応募者の総数を$${n}$$とし、最初の$${r}$$人の応募者を見送るとします。$${r}$$の値をどのように選択するかが問題の鍵です。応募者を見送った後、$${r+1}$$番目の応募者から、それまでに面接した中で最も優秀な応募者よりも優秀な最初の人を選択します。
確率$${P}$$（最適な候補者を選択する）を最大化する$${r}$$の値を見つける必要があります。これは、$${P}$$を$${r}$$についての関数として表し、その最大値を求めることによって行います。
具体的な計算は以下の通りです。
$$
P = \sum_{k=r+1}^{n} \frac{r}{k-1} \cdot \frac{1}{n}
$$
ここで、$${\frac{r}{k-1}}$$は$${k-1}$$番目までの最も優秀な応募者が$${r}$$番目の中に入っており、したがって$${k}$$番目の応募者に順番が回ってくる確率、$${\frac{1}{n}}$$はその応募者が全体の中で最も優秀である確率です。
この式を最大化する$${r}$$の値は、$${n}$$が無限大に近づくにつれて$${\frac{n}{e}}$$に近づきます。したがって、最適な停止ルールは、最初の$${\frac{n}{e}}$$候補者を見送り、その後に出現する最初の「記録破り」の応募者を選択することです。この戦略に従った場合、最適な候補者を選択する確率は約36.8%になります。
n=10の場合
$${n=10}$$の場合、確率$${P}$$を具体的に計算すると以下のようになります。ここで、$${P}$$は最適な候補者を選択する確率で、$${r}$$は最初に見送る応募者の数です。式は次のようになります：
$$
P = \sum_{k=r+1}^{10} \frac{r}{k-1} \cdot \frac{1}{10}
$$
この式は、$${r+1}$$番目から10番目までの応募者について、それが現時点で見た中で最も優秀な応募者であり、かつ全体の中で最も優秀である確率を加算しています。具体的には、$${r}$$の値に応じて確率がどのように変化するかを計算します。
$${n=10}$$で最も効果的な$${r}$$の値を見つけるために、異なる$${r}$$の値に対する$${P}$$の値を計算して比較することができます。理論的には、$${n}$$が大きな値のとき、最適な$${r}$$の値は$${n/e}$$の近似値になりますが、$${n=10}$$の場合、具体的な$${r}$$の最適値を計算する必要があります。
それでは、$${n=10}$$の場合について、異なる$${r}$$の値に対する$${P}$$の値を計算してみましょう。
$${n=10}$$の場合に異なる$${r}$$の値に対する確率$${P}$$の計算結果は以下の通りです：
$${r=1}$$の場合、$${P \approx 0.283}$$
$${r=2}$$の場合、$${P \approx 0.366}$$
$${r=3}$$の場合、$${P \approx 0.399}$$
$${r=4}$$の場合、$${P \approx 0.398}$$
$${r=5}$$の場合、$${P \approx 0.373}$$
$${r=6}$$の場合、$${P \approx 0.327}$$
$${r=7}$$の場合、$${P \approx 0.265}$$
$${r=8}$$の場合、$${P \approx 0.189}$$
$${r=9}$$の場合、$${P = 0.1}$$
この結果から、$${n=10}$$の場合、最適な候補者を選択する確率を最大化する$${r}$$の値は$${3}$$または$${4}$$であり、そのときの確率は約$${0.399}$$です。
シミュレーションでの解答
一般解答がわからなくてもPythonでシミュレーションするという方法もあります。r=0~9で10,000回づつシミュレーションしてみます。
シミュレーションの結果、$${n=10}$$の場合で各$${r=0}$$から$${9}$$までの値に対して、最も優秀な人が雇えた可能性（成功率）は以下の通りです：
$${r=0}$$の場合、成功率は約$${0.1006}$$
$${r=1}$$の場合、成功率は約$${0.2827}$$
$${r=2}$$の場合、成功率は約$${0.373}$$
$${r=3}$$の場合、成功率は約$${0.3964}$$
$${r=4}$$の場合、成功率は約$${0.4054}$$
$${r=5}$$の場合、成功率は約$${0.3766}$$
$${r=6}$$の場合、成功率は約$${0.3336}$$
$${r=7}$$の場合、成功率は約$${0.2654}$$
$${r=8}$$の場合、成功率は約$${0.1858}$$
$${r=9}$$の場合、成功率は約$${0.1013}$$
これらの結果は、以前の計算結果と非常に近く、特に$${r=4}$$での成功率が約$${0.4054}$$と最も高く、理論値に近い結果を示しています。これは、最初の4人の応募者を見送り、その後に出現する最初の「記録破り」の応募者を選択する戦略が、最適な候補者を選択する上で効果的であることを示しています(見送る人数を3人としてもほぼ同じです）。コードも示しておきます。
import numpy as np
import matplotlib.pyplot as plt
# シミュレーションの設定
n = 10 # 応募者の総数
simulations = 10000 # シミュレーション回数
results = []
# rを0から9まで変化させる
for r in range(10):
success = 0
for _ in range(simulations):
# 応募者の順位をランダムに生成
applicants = np.random.permutation(n) + 1
# 最初のr人を見送る
best_of_skipped = max(applicants[:r]) if r > 0 else 0
# r+1人目以降で最初にbest_of_skippedを超える応募者を選択
for applicant in applicants[r:]:
if applicant > best_of_skipped:
if applicant == n: # もし選択した応募者が最も優秀だった場合
success += 1
break
# 成功確率を記録
results.append(success / simulations)
# 結果をプロット
plt.figure(figsize=(10, 6))
plt.plot(range(10), results, marker='o', linestyle='-', color='blue')
plt.title('Success Rate of Hiring the Best Applicant')
plt.xlabel('Number of Applicants Skipped (r)')
plt.ylabel('Success Rate')
plt.grid(True)
plt.xticks(range(10))
plt.yticks(np.linspace(0, max(results), num=11))
plt.show()
results
応募者から見た場合
応募者から見るとどのような戦略をとれば採用されやすいでしょうか？応募者の相対的な能力は不明とします。
問題文：
職員募集に応募する予定。面接ではトライアル雇用1ヶ月後に採用/不採用を決定、不採用の場合は次の応募者が呼ばれる。最大10人面接予定。クリニックは最適停止問題をよく理解しており最初のn人は必ず不採用としより良い人が来たときに採用する戦略をとる。何人目に面接に行くべきか？
つまり自分が応募者であった場合、何番目に面接に行けば採用される可能性が高いか、という問題です。自分の能力は10人の中で何番目かは不明、という前提です。
解答：
この問題ではクリニックが採用に際して最適停止問題の解法を用いていると仮定します。最適な戦略は、最初の$${n/e}$$人の候補者を観察することで、ここで$${n}$$は面接する候補者の総数（この場合は10人）、$${e}$$はネイピア数（約2.71828）です。この戦略により、最適な候補者を選択する確率を最大化できます。
最初の$${n/e}$$人を観察期間として、その後に現れる、これまでに観察した中で最も優れた候補者よりも優れている最初の候補者を選択します。10人の候補者がいる場合、最適な観察期間の長さ$${n/e}$$は、約10/2.71828 = 3.68です。これを四捨五入すると、最初の3人または4人を観察期間とし、その後に出現する最初のより優れた候補者を選択するのが最適です。
したがって、応募者としては、観察期間の直後、つまり4人目または5人目に面接に行くことが、採用される可能性を最大化する戦略となります。n=10人の場合には、採用側が3人目まで経過観察にするのか、4人目まで経過観察にするのか不明です。3人目までの経過観察期間としても4人目までの経過観察期間としてもほぼ同じ結果になるからです。そう考えると5人目に面接に行くのが最適という結果になります。
この問題を図示しますと下記のようになります。採用される可能性があるのは下記の緑Xのグループです。その中で観察期間後に一番最初に行った人が採用されます。そうしますと応募者から見た場合は$${n/e}$$+1人目に面接に行くと最も採用される可能性が高いということになります。
実際にPythonでシミュレーションしてみます、応募者の能力は1-10にランダムに振り分けられるとします。100,000回のシミュレーションです。
import numpy as np
import matplotlib.pyplot as plt
# Parameters
n_simulations_adjusted = 100000 # Adjusted number of simulations
n_candidates = 10 # Number of candidates
observation_period = 4 # Number of candidates to observe before making a decision
# Initialize array to store the results with an adjusted number of simulations
hired_positions_adjusted = np.zeros(n_candidates)
for _ in range(n_simulations_adjusted):
# Generate random abilities for each candidate
abilities_adjusted = np.random.permutation(n_candidates) + 1 # Abilities from 1 to 10
# The best ability seen during the observation period
best_during_observation_adjusted = max(abilities_adjusted[:observation_period])
# Simulate the selection process after the observation period
for i in range(observation_period, n_candidates):
if abilities_adjusted[i] > best_during_observation_adjusted:
hired_positions_adjusted[i] += 1
break # Stop the process once the first candidate better than all observed candidates is found
# Calculate probabilities with adjusted number of simulations
hired_probabilities_adjusted = hired_positions_adjusted / n_simulations_adjusted
# Plotting with adjusted number of simulations as a bar graph
plt.figure(figsize=(10, 6))
plt.bar(range(1, n_candidates + 1), hired_probabilities_adjusted, color='teal')
plt.xlabel('Position of Interview')
plt.ylabel('Probability of Being Hired')
plt.title('Probability of Being Hired Based on Interview Position (Observation Period: 4, 100,000 Simulations)')
plt.xticks(range(1, n_candidates + 1))
plt.grid(axis='y')
plt.show()
応募者から見た場合は$${n/e}$$+1人目に面接に行くと良い、というシンプルな結論なのですがまず最適停止問題の文脈を理解していないといけないと言うハードルはあります。また10人の場合は見送られる人数が3人なのか4人なのか、どちらの可能性もあるというハードルもあります。ただ4人目まで見送られた場合は4人目にいくと可能性はゼロです。そう考えると10人の場合は5番目にいくのがもっとも良いという結論になります。
応募者から見た場合の職員採用問題は新しいのではないかと考え解説いたしました。