這個演算法的故事背景聽起來就比推銷員演算法 (traveling salesman) 有趣多了. 傻傻的推銷員只會走來走去, 秘書演算法卻可以讓大家過老闆的癮呢! 可惜我以前念書的時候, 只有推銷員問題, 老師或書本上都沒有祕書問題. 上次看到有位小朋友研究這個問題得了獎, 因此我才有機會試著了解一下! (這位小朋友研究的是: 有競爭者的時候, 應該錄取第幾位秘書.)
假設有一個大老闆在挑選秘書, 又有很多的準秘書來應徵, 老闆如何在最短的時間內, 挑到最好的人才呢? 這就是秘書演算法討論的問題. 如果真的把每一位秘書都 interview 過一輪, 而且大家都願意等 offer (這是 off-line algorithm), 我們當然 100% 會挑到最好的, 但若是時間有限, 好秘書不等人, 我們怎樣在 95% 信心度之下, 挑出最好的那一位, 又不用面試完所有的人呢? (這樣好像在解計量考題…)
只選一位秘書的狀況下, 假使我們從 n 位應徵者中, 隨機面談了 k 位, k = 1,2,3…, 每面談一位, 老闆就要決定是否發 offer. 此時大家應該可以感受, 發 offer 與不發都需要智慧. 因為 offer 發出去就沒有了, 一不小心就錯過了最好的那位候選人 (這是 on-line algorithm).
on-line performance 對 off-line performance 的比值叫做 competitive ratio, 用來評估演算法好不好.有個 1/3 – competitive ratio 的演算法可以改進上面的狀況. 我們先從 n 位應徵者中面談一半的人, 然後挑出裡面最好的那一個, 假設他 (她) 的面談分數是 max v 分. 然後呢, 對於後一半的應徵者, 只要分數高過於 max v 分, 馬上就錄取他 (她), 後面的人就完全不用考慮了.
如果有 k 個 offer 要發, 我們優化的目標就變成有多樣選擇: (1) 在最少的面談次數找到最佳候選人, (2) 最小化 k 個錄取者的排名總和, (3) 最大化 k 個錄取者的評分總和. 因為要挑到最好的人的機率 (probability), 以及選擇最少的面談次數, 兩者是互斥的.
要從 n 個應徵者當中挑出 k 個人進公司時, 可以從 n 當中隨機挑出約一半的 m 個人, 並且發出 k 個名額當中約一半的 l 個 offer. 因此, n 選 k 的問題就縮減成了 m 選 l 的問題.
由第 m+1 個人開始, 如果這個人比我們已經發出 offer 的人都還要高分, 我們就錄取他/她. 不知道理解得對不對, 這個演算法是 divide and conquer. 據說這個演算法的 competitive ratio 為 1-O((1/k)1/2).
1966 年, Chow 等人證明在應徵者無限多, 只發一個 offer 時, 理論上選第 3.8695 的人最好, 也就是錄取第四個人吧! (我理解錯了的話, 還請網友糾正, 謝謝!)
我以前的老闆跟我說: “你面談的時候, 至少要談 3 個人才能能發 offer." 所以經驗法則和上面的證明也差不了多少. 事實上, 如果是以前熱門的國防役, 大概要談 10 個人才會錄取一個人. 2004 年, 我手上有 4 個國防役名額的時候, 就花了好多的時間在面談. 後來更是發了幾十個 offer 給軟體和韌體工程師, 一整年幾乎都荒廢了.
附帶一提, 數學上講究的是最佳化, 也就是談最少的人, 達到最滿意的結果. 然而, 在現實生活中, 考慮的層面就不是這麼單純, 我們不需要最佳化面談的時間, 因為人才是公司最重要的資產. 如果只是為了省主管的時間, 而找到次佳的人進來, 若他/她已經落入不佳的等級, 可能是公司莫大的災難.
K 個 offer (choice) 這個題目好像很多人都做過研究了, 我覺得考慮競爭者 (別的公司也在面談) 和錄取者彼此互補性都是很有趣的題目. 比方說, 過去的研究都是假設每個人只有一分數, 但若是錄取 A,B,C 3 人, A 的表現會受 B,C 的影響, 那麼這樣會更加地有趣.
在 “小職員週記" 這套漫畫裡提到, 其實公司會交替地錄用聰明的人, 踏實的人等等. 因為新人進來一陣子之後就會看到他/她們的缺點, 因此會想要找一點不同的人來彌補那些缺點. 所以這個命題也並非無的放矢, 我們在真實世界的面談分數也是隨者資深者已經有幾人, 無經驗者可以有幾人而變動的.
[Ref] http://paul.rutgers.edu/~mangesh/cs514/notes/pres8.pdf
Cash Chou's Blog 