Secretary problem

From Wikipedia, the free encyclopedia

The secretary problem is an optimal stopping problem that 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, and the best choice problem. The problem can be stated as follows:

  1. There is a single secretarial position to fill.
  2. There are n applicants for the position, and the value of n is known.
  3. The applicants can be ranked from best to worst with no ties.
  4. The applicants are interviewed sequentially in a random order, with each order being equally likely.
  5. After each interview, the applicant is accepted or rejected.
  6. The decision to accept or reject an applicant can be based only on the relative ranks of the applicants interviewed so far.
  7. Rejected applicants cannot be recalled.
  8. The object is to select the best applicant. The payoff is 1 for the best applicant and zero otherwise.

Let us say that an applicant is a candidate only if it is better than all the applicants viewed previously. Clearly, since the objective in the problem is to select the single best applicant, only candidates will be considered for acceptance. One reason why the secretary problem has received so much attention is that the optimal policy for the problem (the stopping rule) has a surprising feature. Specifically, for large n the optimal policy is to skip the first n / e applicants (where e is the base of the natural logarithm) and then to accept the next candidate that is better than all those previously interviewed. As n gets larger, the probability of selecting the best applicant from the pool goes to 1 / e, which is around 37%. Whether one is searching through 100 or 100,000,000 applicants, the optimal policy will select the single best one about 37% of the time.

Contents

[edit] Deriving the Optimal Policy

The optimal policy for the problem is a stopping rule. Under it, the interviewer should skip the first r − 1 applicants, and then take the next applicant who is a candidate (i.e., who has the best relative ranking of those interviewed up to that point). For an arbitrary cutoff r, the probability that the best applicant is selected is

P(r)=\sum_{j=r}^{n}\left(\frac{1}{n}\right)\left(\frac{r-1}{j-1}\right)=\left(\frac{r-1}{n}\right)\sum_{j=r}^{n}\left(\frac{1}{j-1}\right).

Letting n tend to infinity, writing x as the limit of r / n, using t for j / n and dt for 1 / n, the sum can be approximated by the integral

P(r)=x \int_{x}^{1}\left(\frac{1}{t}\right)dt = -x \text{log}(x).

Taking the derivative of P(r) with respect to x, setting it to 0, and solving for x, we find that the optimal x is equal to 1 / e. Thus, the optimal cutoff tends to n / e as n increases, and the best applicant is selected with probability 1 / e.

For small values of n, the optimal r can also be obtained by standard dynamic programming methods. The optimal thresholds r and probability of selecting the best alternative P for several values of n are shown in the following table.

n 1 2 3 4 5 6 7 8 9
r 1 1 2 2 3 3 3 4 4
P 1.000 0.500 0.500 0.458 0.433 0.428 0.414 0.410 0.406

Note that the probability of selecting the best alternative converges quite rapidly toward 1/e\approx 0.368.

[edit] Alternative solution

The secretary problem and several modifications of this problem can be solved in a straightforward manner by the odds-algorithm.

[edit] Heuristic Performance

Expected success probabilities for three heuristics.
Expected success probabilities for three heuristics.

Stein, Seale, and Rapoport (2003) derived the expected success probabilities for several psychologically plausible heuristics that might be employed in the secretary problem. The heuristics they examined were:

  • The Cutoff Rule (CR): Do not accept any of the first y applicants; thereafter, select the first encountered candidate (i.e., an applicant with relative rank 1). This rule has as a special case the optimal policy for the CSP for which y = r.
  • Candidate Count Rule (CCR): Select the y encountered candidate. Note, that this rule does not necessarily skip any applicants; it only considers how many candidates have been observed, not how deep the decision maker is in the applicant sequence.
  • Successive Non-Candidate Rule (SNCR): Select the first encountered candidate after observing y non-candidates (i.e., applicants with relative rank >1).

Note that each heuristic has a single parameter y. The figure (shown on right) displays the expected success probabilities for each heuristic as a function of y for problems with n = 80.


[edit] Cardinal Payoff variant

Finding the single best applicant might seem like a rather strict objective. One can imagine that the interviewer would rather hire a higher-valued applicant than a lower-valued one, and not only be concerned with getting the best. That is, she will derive some value from selecting an applicant that is not necessarily the best, and the value she derives is increasing in the value of the one she selects.

To model this problem, suppose that the n applicants have "true" values that are random variables X drawn i.i.d. from a uniform distribution on [0,1]. Similar to the classical problem described above, the interviewer only observes whether each applicant is the best so far (a candidate), must accept or reject each on the spot, and must accept the last one if he is reached. (To be clear, the interviewer does not learn the actual relative rank of each applicant. She learns only whether the applicant has relative rank 1.) However, in this version her payoff is given by the true value of the selected applicant. For example, if she selects an applicant whose true value is 0.8, then she will earn 0.8. The interviewer's objective is to maximize the expected value of the selected applicant.

Since the applicant's values are i.i.d. draws from a uniform distribution on [0,1], the expected value of the tth applicant given that x_{t}=\max\left\{x_{1},x_{2},\ldots,x_{t}\right\} is given by

E_{t}=E\left(X_{t}|I_{t}=1\right)=\frac{t}{t+1}.

As in the classical problem, the optimal policy is given by a threshold, which for this problem we will denote by c, at which the interviewer should begin accepting candidates. Bearden (2006) showed that c is either \lfloor \sqrt n \rfloor or \lceil \sqrt n \rceil. This follows from the fact that given a problem with n applicants, the expected payoff for some arbitrary threshold 1\leq c \leq n is

V_{n}(c)=\sum_{t=c}^{n-1}\left[\prod_{s=c}^{t-1}\left(\frac{s-1}{s}\right)\right]\left(\frac{1}{t+1}\right) +\left[\prod_{s=c}^{n-1}\left(\frac{s-1}{s}\right)\right]\frac{1}{2}={\frac {2cn-{c}^{2}+c-n}{2cn}}.

Differentiating Vn(c) with respect to c, one gets \partial V / \partial c=\left(-{c}^{\,2}+n\right)/ \left(2{c}^{\,2}n\right). Since \partial^{\,2}V / \partial c^{\,2}<0 for all permissible values of c, we find that V is maximized at c=\sqrt n. Since V is convex in c, the optimal integer-valued threshold must be either \lfloor \sqrt n \rfloor or \lceil \sqrt n \rceil. Thus, for most values of n the interviewer will begin accepting applicants sooner in the cardinal payoff version than in the classical version where the objective is to select the single best applicant. Note that this is not an asymptotic result: It holds for all n.

[edit] Other Variants

A number of other variations of the classical secretary problem have been proposed.[1]

[edit] Experimental Studies

Psychologists and experimental economists have studied the decision behavior of actual people in secretary problems [2]. In large part, this work has shown that people tend to stop searching too soon. This may be explained, at least in part, by the cost of evaluating candidates. Extrapolating to real world settings, this might suggest that people do not search enough whenever they are faced with problems where the decision alternatives are encountered sequentially. For example, when trying to decide at which gas station to stop for gas, people might not search enough before stopping. If true, then they would tend to pay more for gas than they might had they searched longer. The same may be true when people search online for airline tickets, say. Experimental research on problems such as the secretary problem is sometimes referred to as behavioral operations research.

[edit] Citations

  1. ^ Many of these are reviewed in Freeman (1983).
  2. ^ Bearden, Murphy, and Rapoport, 2006; Bearden, Rapoport, and Murphy, 2006; Seale and Rapoport, 1997

[edit] References

[edit] See also

[edit] External links