秘書問題(あるいは お見合い問題、あるいは浜辺の美女問題)

More than 1 year has passed since last update.

OR大研究には、鳩山元首相も研究した秘書問題の話が出ています。

秘書問題とは、下記のような問題です。(wikipediaより)

  1. 秘書を1人雇いたいとする。
  2. n 人が応募してきている。n という人数は既知である。
  3. 応募者には順位が付けられ、複数の応募者が同じ順位になることはない(1位からn位まで重複無く順位付けできる)。
  4. 無作為な順序で1人ずつ面接を行う。次に誰を面接するかは常に同じ確率である。
  5. 毎回の面接後、その応募者を採用するか否かを即座に決定する。
  6. その応募者を採用するか否かは、それまで面接した応募者の相対的順位にのみ基づいて決定する。
  7. 不採用にした応募者を後から採用することはできない。
  8. このような状況で、最良の応募者を選択することが問題の目的である。

数学美術館には、20人の場合に平均順位を最小化する手順が出ています。

1)最初の5人はスルー。
2)次の5人については、それまでで最高だったら誘う。
3)次の3人については、それまでで最高or2位なら誘う。
4)次の2人については、それまでで3位以内なら誘う。
5)16番目の人は、それまでで4位以内なら誘う。
6)17番目の人は、それまでで5位以内なら誘う。
7)18番目の人は、それまでで7位以内なら誘う。
8)19番目の人は、それまでで10位以内なら誘う。
9)最後まで来てしまったらその人を誘う。

この手順で平均3位の美女が選べるそうです。

pythonで確かめてみましょう。

python
import numpy as np
def order1(b):
    n = len(b)
    c = sorted(zip(b.argsort(), range(n))) # 実際の順位
    for i in range(5, n): # 最初の5人スルー
        d = b[:i+1]
        e = len(d[d < b[i]]) + 1 # 順位
        if i < 10:
            if e == 1: break
        elif i < 13:
            if e <= 2: break
        elif i < 14:
            if e <= 3: break
        elif i < 15:
            if e <= 4: break
        elif i < 16:
            if e <= 5: break
        elif i < 17:
            if e <= 7: break
        elif i < 18:
            if e <= 10: break
    return c[i][1] + 1

np.random.seed(1)
a = np.random.randn(100000, 20)
print(np.mean([order1(b) for b in a]))
>>>
3.12287

だいたい3位ですね。

でも、最初の5人は必ずスルーというのは、腑に落ちません。面接に来てくれた人にも悪いです。上記の例では、標準正規分布(N(0,1))を用いました。

このように予め分布がわかっていれば、単純にあるしきい値以下なら選択するということもできるでしょう。

やってみました。

python
def order2(b, t):
    n = len(b)
    c = sorted(zip(b.argsort(), range(n))) # 実際の順位
    d = b < t
    if not d.any(): return n
    return c[d.argmax()][1] + 1

np.random.seed(1)
a = np.random.randn(100000, 20)
print(np.mean([order2(b, -0.92) for b in a]))
>>>
2.66621

しきい値は試行錯誤で求めました。さっきより、いいですね。

P.S.
機械学習で、できないか考えてみましたが、上手くいきませんでした。

以上