Secretary Problem

The secretary problem is one of many names for a famous problem of the optimal stopping theory. The problem has been studied extensively in the fields of applied probability, statistics, and decision theory. It is also known as the marriage problem, the sultan's dowry problem, the fussy suitor problem, the googol game, and the best choice problem.

The basic form of the problem is the following: imagine an administrator willing to hire the best secretary out of rankable applicants for a position. The applicants are interviewed one-by-one in random order. A decision about each particular applicant is to be taken immediately after the interview. Once rejected, an applicant cannot be recalled. During the interview, the administrator can rank the applicant among all applicants interviewed so far, but is unaware of the quality of yet unseen applicants. The question is about the optimal strategy (stopping rule) to maximize the probability of selecting the best applicant.

The problem has a strikingly elegant solution. The optimal stopping rule prescribes to reject about applicants after the interview (where e is the base of the natural logarithm) without choice then stop at the first applicant who is better than every applicant interviewed so far (or proceed to the last applicant if this never occurs). Sometimes this strategy is called the stopping rule, because the probability to stop at the best applicant with this strategy is about already for moderate values of . One reason why the secretary problem has received so much attention is that the optimal policy for the problem (the stopping rule) is simple, and selects the single best candidate about 37% of the time, no matter for searching through 100 or 100,000,000 applicants. In fact, for every the probability of best choice with the optimal policy is at least .

Read more about Secretary ProblemFormulation, Deriving The Optimal Policy, Alternative Solution, Unknown Number of Applicants, The Game of Googol, Heuristic Performance, Cardinal Payoff Variant, Experimental Studies, History, See Also, References

Other articles related to "secretary problem, problems":

Secretary Problem - References
... "A new secretary problem with rank-based selection and cardinal payoffs" ... "A multi-attribute extension of the secretary problem Theory and experiments" ... unified Approach to a Class of Best Choice problems with an Unknown Number of Options" ...

Famous quotes containing the words problem and/or secretary:

    We have heard all of our lives how, after the Civil War was over, the South went back to straighten itself out and make a living again. It was for many years a voiceless part of the government. The balance of power moved away from it—to the north and the east. The problems of the north and the east became the big problem of the country and nobody paid much attention to the economic unbalance the South had left as its only choice.
    Lyndon Baines Johnson (1908–1973)

    ... the wife of an executive would be a better wife had she been a secretary first. As a secretary, you learn to adjust to the boss’s moods. Many marriages would be happier if the wife would do that.
    Anne Bogan, U.S. executive secretary. As quoted in Working, book 1, by Studs Terkel (1973)