Secretary problem
The secretary problem demonstrates a scenario involving optimal stopping theory that is 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 who wants to hire the best secretary out of formula_1 rankable applicants for a position. The applicants are interviewed one by one in random order. A decision about each particular applicant is to be made immediately after  the interview. Once rejected, an applicant cannot be recalled. During the interview, the administrator gains information sufficient to 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. If the decision can be deferred to the end, this can be solved by the simple maximum selection algorithm of tracking the running maximum (and who achieved it), and selecting the overall maximum at the end. The difficulty is that the decision must be  made immediately. The shortest rigorous proof known so far is provided by the odds algorithm. It implies that the optimal win probability is always at least formula_2 (where "e" is the base of the natural logarithm), and that the latter holds even in a much greater generality. The optimal stopping rule prescribes always rejecting the first formula_3 applicants that are interviewed and then stopping at the first applicant who is better than every applicant interviewed so far (or continuing to the last applicant if this never occurs). Sometimes this strategy is called the formula_2 stopping rule, because the probability of  stopping at the best applicant with this strategy is about formula_2 already for moderate values of formula_1. 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, irrespective of whether there are 100 or 100 million applicants. Formulation. Although there are many variations, the basic problem can be stated as follows: A "candidate" is defined as an applicant who, when interviewed, is better than all the applicants interviewed previously. "Skip" is used to mean "reject  immediately after the interview". Since the objective in the problem is to select the single best applicant, only candidates will be considered for acceptance. The "candidate" in this context corresponds to the concept of record in permutation. Deriving the optimal policy. The optimal policy for the problem is a stopping rule. Under it, the interviewer rejects the first "r" − 1 applicants (let applicant "M" be the best applicant among these "r" − 1 applicants), and then selects the first subsequent applicant that is better than applicant "M". It can be shown that the optimal strategy lies in this class  of strategies. (Note that we should never choose an applicant who is not the best we have seen so far, since they cannot be the best overall applicant.) For an arbitrary cutoff "r", the probability that the best applicant is selected is The sum is not defined for "r" = 1, but in this case the only feasible policy is to select the first applicant, and hence "P"(1) = 1/"n". This sum is obtained by noting that if applicant "i" is the best applicant, then it is selected if and only if the best applicant among the first "i  − 1 applicants is among the first r" − 1 applicants that were rejected. Letting "n" tend to infinity, writing formula_8 as the limit of "(r-1)"/"n", using "t" for "(i-1)"/"n" and "dt" for 1/"n", the sum can be approximated by the integral Taking the derivative of "P"("x") with respect to formula_8, 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. The probability of selecting the best applicant in the classical secretary problem converges toward formula_11. Alternative solution. This problem and several modifications can be solved (including the proof of optimality) in a straightforward manner by the odds algorithm, which also has other applications. Modifications for the secretary problem that can be solved by this algorithm include random availabilities of applicants, more general hypotheses for applicants to be of interest to the decision  maker, group interviews for applicants, as well as certain models for a random number of applicants. Limitations. The solution of the secretary problem is only meaningful if it is justified to assume that the applicants have no knowledge of the decision strategy employed, because early applicants have no chance at all and may not show up otherwise. One important drawback for applications of the solution of the classical secretary problem is that the number of applicants formula_12 must be known in advance, which is rarely the case. One way to overcome this problem is to suppose that the number of  applicants is a random variable formula_13 with a known distribution of formula_14 (Presman and Sonin, 1972). For this model, the optimal solution is in general much harder, however. Moreover, the optimal success probability is now no longer around 1/"e" but typically lower. This can be understood in the context of having a "price" to pay for not knowing the number of applicants. However, in this model the price is high. Depending on the choice of the distribution of formula_15, the optimal win probability can approach zero. Looking for ways to cope with this new problem led to a new model  yielding the so-called 1/e-law of best choice. 1/e-law of best choice. The essence of the model is based on the idea that life is sequential and that real-world problems pose themselves in real time. Also, it is easier to estimate times in which specific events (arrivals of applicants) should occur more frequently (if they do) than to estimate the distribution of the number of specific events which will occur. This idea led to the following approach, the so-called "unified approach" (1984): The model is defined as follows: An applicant must be selected on  some time interval formula_16 from an unknown number formula_17 of rankable applicants. The goal is to maximize the probability of selecting only the best under the hypothesis that all arrival orders of different ranks are equally likely. Suppose that all applicants have the same, but independent to each other, arrival time density formula_18 on formula_16 and let formula_20 denote the corresponding arrival time distribution function, that is Let formula_23 be such that formula_24 Consider the strategy to wait and observe all applicants up to time formula_25 and then to select, if possible, the first candidate after time formula_25 which is  better than all preceding ones. Then this strategy, called "1/e-strategy", has the following properties: The "1/e-strategy" The 1/e-law, proved in 1984 by F. Thomas Bruss, came as a surprise. The reason was that a value of about 1/e had been considered before as being out of reach in a model for unknown formula_29, whereas this value 1/e was now achieved as a lower bound for the success probability, and this in a model with arguably much weaker hypotheses (see e.g. Math. Reviews 85:m). However, there are many other strategies that achieve  (i) and (ii) and, moreover, perform strictly better than the 1/e-strategy simultaneously for all formula_15>2. A simple example is the strategy which selects (if possible) the first relatively best candidate after time formula_25 provided that at least one applicant arrived before this time, and otherwise selects (if possible) the second relatively best candidate after time formula_25 (). The 1/e-law is sometimes confused with the solution for the classical secretary problem described above because of the similar role of the number 1/e. However, in the 1/e-law, this role is more general. The result is also  stronger, since it holds for an unknown number of applicants and since the model based on an arrival time distribution F is more tractable for applications. The game of googol. According to Ferguson(1989), the secretary problem appeared for the first time in print when it was featured by Martin Gardner in his February 1960 Mathematical Games column in "Scientific American". Here is how formulated it: "Ask someone to take as many slips of paper as he pleases, and on each slip write a different positive number. The numbers may range from small fractions of 1 to a number the size  of a "googol" (1 followed by a hundred zeroes) or even larger. These slips are turned face down and shuffled over the top of a table. One at a time you turn the slips face up. The aim is to stop turning when you come to the number that you guess to be the largest of the series. You cannot go back and pick a previously turned slip. If you turn over all the slips, then of course you must pick the last one turned." In the article "Who solved the Secretary problem?" Ferguson(1989) pointed out that the secretary  problem remained unsolved as it was stated by M. Gardner, that is as a two-person zero-sum game with two antagonistic players. In this game Alice, the informed player, writes secretly distinct numbers on formula_1 cards. Bob, the stopping player, observes the actual values and can stop turning cards whenever he wants, winning if the last card turned has the overall maximal number. The difference with the basic secretary problem is that Bob observes the actual values written on the cards, which he can use in his decision procedures. The numbers on cards are analogous to the numerical qualities  of applicants in some versions of the secretary problem. The joint probability distribution of the numbers is under the control of Alice. Bob wants to guess the maximal number with the highest possible probability, while Alice's goal is to keep this probability as low as possible. It is not optimal for Alice to sample the numbers independently from some fixed distribution, and she can play better by choosing random numbers in some dependent way. For formula_34 Alice has no minimax strategy, which is closely related to a paradox of T. Cover. But for formula_35 the game has a solution : Alice can choose random numbers (which are dependent random variables) in such a way that Bob cannot play better than using the classical stopping strategy based on the relative ranks (). Heuristic performance. The remainder of the article deals again with the secretary problem for a known number of applicants. 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. 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, the interviewer will derive some value from selecting an applicant that is not necessarily the best, and the derived value increases with the value of the one selected. To model this problem, suppose that the formula_1 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/she is reached. (To be clear, the interviewer does not learn the actual relative rank of "each" applicant. He/she learns only whether the applicant has relative rank 1.) However, in this version the "payoff" is given by the true value of the selected applicant. For example, if he/she selects an applicant whose true value is 0.8, then he/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 "t"th applicant given that formula_37 is given by As in the classical problem, the optimal policy is given by a threshold, which for this problem we will denote by formula_39, at which the interviewer should begin accepting candidates. showed that "c" is either formula_40 or formula_41. (In fact, whichever is closest to formula_42.) This follows from the fact that given a problem with formula_1 applicants, the expected payoff for some arbitrary threshold formula_44 is Differentiating formula_46 with respect to "c", one gets Since formula_48 for all  permissible values of formula_39, we find that formula_50 is maximized at formula_51. Since "V" is convex in formula_39, the optimal integer-valued threshold must be either formula_40 or formula_41. Thus, for most values of formula_1 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 formula_1. However, this is not the optimal policy to maximize expected value from a known distribution. In the case of a known distribution, optimal play can  be calculated via dynamic programming. A more general form of this problem introduced by Palley and Kremer (2014) assumes that as each new applicant arrives, the interviewer observes their rank relative to all of the applicants that have been observed previously. This model is consistent with the notion of an interviewer "learning" as they continue the search process by accumulating a set of past data points that they can use to evaluate new candidates as they arrive. A benefit of this so-called partial-information model is that decisions and outcomes achieved given the relative rank information can be directly  compared to the corresponding optimal decisions and outcomes if the interviewer had been given full information about the value of each applicant. This full-information problem, in which applicants are drawn independently from a known distribution and the interviewer seeks to maximize the expected value of the applicant selected, was originally solved by Moser (1956), Sakaguchi (1961), and Karlin (1962). Other modifications. There are several variants of the secretary problem that also have simple and elegant solutions. One variant replaces the desire to pick the best with the desire to pick the second-best. Robert J. Vanderbei calls this the  postdoc problem arguing that the "best" will go to Harvard. For this problem, the probability of success for an even number of applicants is exactly formula_57. This probability tends to 1/4 as n tends to infinity illustrating the fact that it is easier to pick the best than the second-best. For a second variant, the number of selections is specified to be greater than one. In other words, the interviewer is not hiring just one secretary but rather is, say, admitting a class of students from an applicant pool. Under the assumption that success is achieved if and only  if all the selected candidates are superior to all of the not-selected candidates, it is again a problem that can be solved. It was shown in that when n is even and the desire is to select exactly half the candidates, the optimal strategy yields a success probability of formula_58. Another variant is that of selecting the best formula_59 secretaries out of a pool of formula_1, again in an on-line algorithm. This leads to a strategy related to the classic one and cutoff threshold offormula_57 for which the classic problem is a special case . Multiple choice problem. A  player is allowed formula_62 choices, and he wins if any choice is the best. Gilbert and Mosteller showed that formula_67. For further cases that formula_68, see (for example formula_69). When formula_70, the probability of win converges to formula_71 (). Experimental studies. Experimental psychologists and economists have studied the decision behavior of actual people in secretary problem situations. 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. In 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 along a highway to stop for gas, people might not search enough before stopping. If true, then they would tend to pay more for gas than if they had searched longer. The same may be true when people search online for airline tickets. Experimental research on problems such as the secretary problem is sometimes referred to as behavioral operations research. Neural correlates. While there is a substantial body of neuroscience research on information integration, or the representation of belief , in perceptual decision-making tasks using both animal and human subjects, there is relatively little known about how the decision to stop gathering information is arrived at. Researchers have studied the neural bases of solving the secretary problem in healthy volunteers using functional MRI. A Markov decision process (MDP) was used to quantify the value of continuing to search versus committing to the current option. Decisions to take versus decline an option engaged parietal and dorsolateral prefrontal cortices, as well ventral striatum, anterior insula, and anterior cingulate. Therefore, brain regions previously implicated in evidence integration and reward representation encode threshold  crossings that trigger decisions to commit to a choice. History. The secretary problem was apparently introduced in 1949 by Merrill M. Flood, who called it the fiancée problem in a lecture he gave that year. He referred to it several times during the 1950s, for example, in a conference talk at Purdue on 9 May 1958, and it eventually became widely known in the folklore although nothing was published at the time. In 1958 he sent a letter to Leonard Gillman, with copies to a dozen friends including Samuel Karlin and J. Robbins, outlining a proof of the optimum strategy , with an appendix by R. Palermo who proved that all strategies are dominated by a strategy of the form "reject the first "p" unconditionally, then accept the next candidate who is better". (See Flood (1958).) The first publication was apparently by Martin Gardner in Scientific American, February 1960. He had heard about it from John H. Fox Jr., and L. Gerald Marnie, who had independently come up with an equivalent problem in 1958; they called it the "game of googol". Fox and Marnie did not know the optimum solution; Gardner asked for advice from Leo Moser, who (together with J.  R. Pounder) provided a correct analysis for publication in the magazine. Soon afterwards, several mathematicians wrote to Gardner to tell him about the equivalent problem they had heard via the grapevine, all of which can most likely be traced to Flood's original work. The 1/"e"-law of best choice is due to F. Thomas Bruss (1984). Ferguson (1989) has an extensive bibliography and points out that a similar (but different) problem had been considered by Arthur Cayley in 1875 and even by Johannes Kepler long before that. Combinatorial generalization. The secretary problem can be generalized to the case where there  are multiple different jobs. Again, there are formula_1 applicants coming in random order. When a candidate arrives, she reveals a set of nonnegative numbers. Each value specifies her qualification for one of the jobs. The administrator not only has to decide whether or not to take the applicant but, if so, also has to assign her permanently to one of the jobs. The objective is to find an assignment where the sum of qualifications is as big as possible. This problem is identical to finding a maximum-weight matching in an edge-weighted bipartite graph where the formula_1 nodes of  one side arrive online in random order. Thus, it is a special case of the online bipartite matching problem. By a generalization of the classic algorithm for the secretary problem, it is possible to obtain an assignment where the expected sum of qualifications is only a factor of formula_81 less than an optimal (offline) assignment.