Оңтайлы тоқтау теориясы: «Хатшылар мәселесі»

Mathematical problem involving optimal stopping theory

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. Its solution is also known as the 37% rule. The basic form of the problem is the following: imagine an administrator who wants 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 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 (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 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 stopping rule, because the probability of stopping at the best applicant with this strategy is already about 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, irrespective of whether there are 100 or 100 million applicants.

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.

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 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 with a known distribution of (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 , 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.

For , if Bob plays the optimal relative rank stoppings strategy, then Bob has winning probability 1/2. Surprisingly, Alice has no minimax strategy, which is closely related to a paradox of T. Cover and the two envelopes paradox. Concretely, Bob can play this strategy: sample a random number If , then pick , else pick Now, Bob can win with probability strictly greater than 1/2. Suppose Alice's numbers are different, then conditional on , Bob wins with probability 1/2, but conditional on , Bob wins with probability 1. Note that the random number can be sampled from any random distribution, as long as has nonzero probability. However, for any , Alice can construct an exchangeable sequence such that Bob's winning probability is at most
But for , the answer is yes: 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.

The remainder of the article deals again with the secretary problem for a known number of applicants. 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 classical secretary problem for which y = r.
Candidate count rule (CCR): Select the y th 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). 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.

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 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.

Consider the problem of picking the k best secretaries out of n candidates, using k tries. In general, the optimal decision method starts by observing candidates without picking any one of them, then pick every candidate that is better than those first candidates until we run out of candidates or picks. If is held constant while , then the probability of success converges to By , if , then the probability of success is .

In this variant, a player is allowed choices and wins if any choice is the best. An optimal strategy for this problem belongs to the class of strategies defined by a set of threshold numbers , where

Specifically, imagine that you have letters of acceptance labelled from to You would have application officers, each holding one letter. You keep interviewing the candidates and rank them on a chart that every application officer can see. Now officer would send their letter of acceptance to the first candidate that is better than all candidates to (Unsent letters of acceptance are by default given to the last applicants, the same as in the standard secretary problem.) At limit, each , for some rational number .

When , the probability of winning converges to More generally, for positive integers , the probability of winning converges to , where
computed up to , with
gave a general algorithm. For example, .

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.

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.

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". 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. Ferguson 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, who spent 2 years investigating 11 candidates for marriage during 1611 1613 after the death of his first wife.

The secretary problem can be generalized to the case where there are multiple different jobs. Again, there are 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 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 less than an optimal (offline) assignment.