Transcript PPT
Topics in Search Theory The Secretary Problem Theme Paper • Who Solved the Secretary Problem? – Thomas Ferguson, 1989 Background • Problem appeared in late 50’s and early 60’s • Also known as “marriage problem”, “the dowry problem” • Highly appealing problem: – Easy to state – Striking solution • Since then the problem has been extended and generalized in many directions to become a “field” of study (see [Freeman, 1983]) Problem Statement • Simplest form: – There is one secretarial position available – The number of applicants is known – The applicants are interviewed sequentially in random order (each sequence is equally likely) – You can rank all the applicants from best to worst without ties – The decision to accept or reject the applicant must be based only on the relative ranks of those applicants interviewed so far – An applicant once rejected cannot later be recalled – You will be satisfied with nothing but the very best (meaning: your payoff is 1 if choosing the best of the n applicants and 0 otherwise) Analysis • Attention can be restricted to the class of rules that for some integer r≥1 rejects the first r-1 applicants and then chooses the next applicant who is best in the relative ranking of the observed applicants (since we don’t learn anything new about the population over each interview) reject first r-1 accept (and stop) if better than max so far timeline n Analysis • What is the probability n r of selecting the best applicant? – For r=1 or r=n, 1/n – For r>1: the probability that this is the best candidate j - th applicant is best n 1 r 1 r 1 n 1 n r P j r and you select it j r n j 1 n j r j 1 n max of r-1 > max of j-r the probability that the maximum number in a sample of j-1 is one of the first r-1 numbers timeline n Analysis • The optimal r is the one that maximizes this probability r 1 n 1 n r n j r j 1 • For small values of n the optimal r can be easily computed (see excel file) • Approximation can be supplied for large n Kepler’s Problem • In 1611, the German astronomer Johannes Kepler lost his wife • Since his first marriage had been arranged for him, he decided this time to make his own decision • He arranged to interview and to choose from among no fewer than eleven candidates • The process consumed much of his attention for nearly 2 years, investigating: – – – – – Virtues and drawbacks Dowry Negotiation with the parents Advice of friends … Kepler’s Problem • Of the eleven candidates interviewed, Kepler eventually decided on the fifth • What a surprise! Check the excel sheet for the optimal strategy here… • Perhaps if Kepler had been aware of the secretary problem, he could have saved himself a lot of time and trouble • Of course, it is not exactly the same problem: – – – – Recall option Discount factor? Other utility aspects? Maybe it’s an optimal stopping rule problem? Back to Secretary problem: Analysis • This is actually a Riemann approximation to an integral! • When: r 1 n 1 n r n j r j 1 n r x lim n j t n dt 1 n 1 1 r 1 n n 1 x dt x log x n r x t n j r j 1 n Optimal Solution • First derivative: n r x log x n ' r log x 1 0 log x 1 x 1 / e 0.367879 • Substituting in n r : n r 1 / elog 1 / e 1 / e • Interpretation: wait until 37% of applicants have been interviewed and then select the relative best one. The probability of success in this case will be 37% Differences from One-Sided Search • • • • • Rankings No search costs Decision horizon Recall Goal function (find the best vs. optimize expected value)