Bài toán thư ký

Bài toán thư ký là một bài toán nổi tiếng trong lý thuyết dừng tối ưu. Bài toán này đã được nghiên cứu trong xác suất ứng dụng, thống kê, và lý thuyết quyết định.

Dạng cơ bản của bài toán là như sau. Một người quản lý cần tuyển thư ký tốt nhất trong n ứng viên có thể xếp hạng. Các ứng viên được phỏng vấn lần lượt theo một thứ tự ngẫu nhiên. Quyết định cho mỗi ứng viên phải được đưa ra ngay sau khi phỏng vấn ứng viên đó. Sau khi đã bị từ chối, ứng viên đó sẽ không thể được tuyển. Trong quá trình phỏng vấn, người quản lý có thể xếp hạng các ứng viên đã phỏng vấn nhưng không biết gì về chất lượng của các ứng viên chưa phỏng vấn. Câu hỏi đặt ra là nên sử dụng chiến thuật nào để tối ưu hóa xác suất tuyển được ứng viên tốt nhất.

Bài toán cơ bản trên có một lời giải đẹp. Đầu tiên phỏng vấn và từ chối khoảng n/e ứng viên (trong đó e là cơ số của lôgarit tự nhiên). Sau đó chấp nhận ứng viên đầu tiên tốt hơn tất cả các ứng viên đã được phỏng vấn trước đó (hoặc chấp nhận ứng viên cuối cùng nếu điều này không xảy ra). Nếu áp dụng thuật toán này thì xác suất tuyển được ứng viên tốt nhất là khoảng 1/e và đây cũng là xác suất tối ưu.

Nguồn gốc của bài toán

Bài toán được xuất bản lần đầu tiên bởi Martin Gardner trong Scientific American năm 1960.

Bài báo năm 1989 của T. S. Ferguson[1] chỉ ra rằng có những bài toán khác tương tự đã được xem xét bởi Arthur Cayley năm 1875 và Johannes Kepler từ lâu trước đó.

Ghi chú

1. Ferguson (1989)

Tham khảo

• Bearden, J.N. (2006). “A new secretary problem with rank-based selection and cardinal payoffs”. Journal of Mathematical Psychology. 50: 58–9. doi:10.1016/j.jmp.2005.11.003.
• Bearden, J.N., Murphy, R.O. Rapoport, A. (2005). “A multi-attribute extension of the secretary problem: Theory and experiments”. Journal of Mathematical Psychology. 49 (5): 410–425. doi:10.1016/j.jmp.2005.08.002.
• Bearden, J.N., Rapoport, A., Murphy R.O. (2006). “Sequential observation and selection with rank-dependent payoffs: An experimental test”. Management Science. 52 (9): 1437–49. doi:10.1287/mnsc.1060.0535.
• F. Thomas Bruss (1984). “A unified Approach to a Class of Best Choice problems with an Unknown Number of Options”. Annals of Probability. 12 (3): 882–891. doi:10.1214/aop/1176993237.
• F. Thomas Bruss (2000). “Sum the odds to one and stop”. Annals of Probability. 28 (3): 1384–91. doi:10.1214/aop/1019160340.
• Ferguson, T.S. (1989). “Who solved the secretary problem?”. Statistical science. 4 (3): 282–296. doi:10.1214/ss/1177012493.
• Gnedin, A. (1994). “A solution to the game of Googol”. Annals of Probability. 22 (3): 1588–1595. doi:10.1214/aop/1176988613.
• Freeman, P.R. (1983). “The secretary problem and its extensions: A review”. International Statistical Review / Revue Internationale de Statistique. 51 (2): 189–206. doi:10.2307/1402748. JSTOR 1402748.
• Hill, T.P. "Knowing When to Stop". American Scientist, Vol. 97, 126-133 (2009). (Có một bản dịch tiếng Pháp tại cover story Lưu trữ 2011-07-21 tại Wayback Machine trong số tháng 7 của Pour la Science (2009))
• Seale, D.A., Rapoport, A. (1997). “Sequential decision making with relative ranks: An experimental investigation of the 'secretary problem'”. Organizational Behavior and Human Decision Processes. 69 (3): 221–236. doi:10.1006/obhd.1997.2683.
• Stein, W.E.; Seale, D.A.; Rapoport, A. (2003). “Analysis of heuristic solutions to the best choice problem”. European Journal of Operational Research. 151: 140–152. doi:10.1016/S0377-2217(02)00601-X.
• Merrill R. Flood, thư viết năm 1958, một bản sao nằm trong bài báo của Martin Gardner tại Stanford University Archives, series 1, box 5, folder 19.
• Martin Gardner, "New Mathematical Diversions" trong Scientific American. Simon and Schuster, 1966, Chương 3, bài 3 [in lại từ bài báo xuất bản tháng 2 năm 1960 với thông tin bổ sung].
• Miller, Geoffrey F. (2001). The mating mind: how sexual choice shaped the evolution of human nature. Anchor Books. ISBN 0-385-49517-X.
• Framing Our Thoughts: Ecological Rationality as Evolutionary Psychology's Answer to the Frame Problem, Timothy Ketelaar and Peter M. Todd, Chương 5 của Conceptual Challenges in Evolutionary Psychology, tr. 187.
• Sardelis, D., Valahas, T. (1992). “Decision Making: A Golden Rule”. American Mathematical Monthly. 99 (3): 935–942.