Lecture
The picky bride problem (the choice-stopping problem) is an optimization problem first formulated by Martin Gardner in 1960.
In the English-language literature it is also found under the name of the secretary problem.
The problem can be formulated as follows :
.In 1963 Eugene Dynkin proposed a solution to this problem for a special case. The general solution was found by Sabir Huseyn-Zade in 1966.
This problem has received a great deal of attention largely because the optimal strategy has an interesting feature: if the number of candidates is large enough, the optimal strategy consists of rejecting all the first 
(where 
— the base of the natural logarithm) candidates and then choosing the first one who is better than all the previous ones . As {\displaystyle n} increases, the probability of selecting the best candidate tends to 
, that is, to approximately 37%.
Among the variants and generalizations of the problem are those in which the total number of candidates is not known in advance, or those in which each candidate can not only be compared with the others, but also given an absolute rating .
In the dissertation of Boris Berezovsky, later a corresponding member of the Russian Academy of Sciences, for the degree of Doctor of Sciences, «Development of theoretical foundations for the algorithmization of pre-design decision-making and their application», defended in 1983, a generalization of the picky bride problem is considered .
The secretary problem demonstrates a scenario involving the theory of optimal stopping , which is widely studied in the fields of applied probability theory, 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 this: imagine an administrator who wants to hire the best secretary out of all of them. highly-rated candidates for the position. The candidates are interviewed one at a time in random order. A decision about each particular applicant is made immediately after the interview. Once rejected, an applicant cannot be recalled. During the interview, the administrator obtains information sufficient to rank the candidate among all candidates interviewed so far, but does not know about the quality of candidates not yet seen. The question is the optimal strategy (a stopping rule) to maximize the probability of choosing the best candidate. If the decision could be postponed until the end, this could be solved with a simple maximum-selection algorithm: tracking the running maximum (and who achieved it), and selecting the overall maximum at the end. The difficulty is that the decision has to be made immediately.
The shortest rigorous proof known so far is given by the odds algorithm. This means that the optimal probability of winning is always at least (where e is the base of the natural logarithm), and the latter holds even in much greater generality. The optimal stopping rule prescribes always rejecting the first 
candidates who are interviewed, and then stopping at the first candidate who is better than every candidate interviewed so far (or moving on to the last candidate if this never happens). This strategy is sometimes called the stopping rule, because the probability of stopping at the best candidate with this strategy is about already for moderate values of . One of the reasons the secretary problem receives so much attention is that the optimal policy for the problem (the stopping rule) is simple and selects the single best candidate in about 37% of cases, regardless of whether there are 100 or 100 million candidates.
Although there are many variants, the basic problem can be formulated as follows:
A candidate is defined as an applicant who, at interview, is better than all applicants interviewed previously. To skip means «to reject immediately after the interview». Since the goal of the problem is to select the single best candidate, only candidates will be considered for acceptance. A «candidate» in this context corresponds to the concept of a record in a permutation.
The optimal policy for solving 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 who is better than applicant M. It can be shown that the optimal strategy lies within this class of strategies. [ citation needed ] (Note that we should never select a candidate who is not the best candidate we have seen so far, since he cannot be the overall best candidate.) For an arbitrary cutoff r, the probability that the best candidate will be selected equals
The sum is undefined for r = 1, but in this case the only possible policy is to select the first applicant, and hence P (1) = 1 / n. This sum follows from the fact that if candidate i is the best candidate, then he is selected if and only if the best candidate among the first i - 1 applicants is among the first r - 1 applicants who were rejected. Letting n tend to infinity, writing
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, setting it to 0 and solving for x, we find that the optimal x equals 1 / e. Thus the optimal cutoff tends to n / e as n increases, and the best candidate 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 the probability P of selecting the best alternative for several values of n are shown in the following table.
|
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
 |
1 | 1 | 2 | 2 | 3 | 3 | 3 | 4 | 4 |
 |
1.000 | 0,500 | 0,500 | 0,458 | 0,433 | 0,428 | 0,414 | 0,410 | 0,406 |
The probability of selecting the best candidate in the classical secretary problem converges to 
.
This problem and several modifications can be solved (including the proof of optimality) in a simple way using the odds algorithm, which also has other applications. Modifications of the secretary problem that can be solved by this algorithm include random availability of candidates, more general hypotheses for candidates of interest to the decision maker, group interviews for candidates, and certain models for a random number of candidates.
Solving the secretary problem makes sense only if the assumption is justified that the candidates are unaware of the decision-making strategy used, because early candidates would otherwise have no chance at all and might not show up. [ citation needed ]
One important drawback of applications of the solution to the classical secretary problem is that the number of applicants must be known in advance, which is rarely the case. One way to solve this problem is to assume that the number of applicants is a random variable
with a known distribution 
(Presman, Sonin, 1972). However, for this model the optimal solution is generally much more complex. Moreover, the optimal probability of success is now no longer around 1 / е, but usually lower. This can be understood in the context of a «price» that has to be paid 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 probability of winning can approach zero. Finding ways to deal with this new problem led to a new model yielding the so-called 1/e law of best choice.
The essence of the model is based on the idea that life is sequential and that real problems occur in real time. Furthermore, it is easier to estimate the time at which particular events (arrivals of candidates) are more likely to occur (if they occur) than to estimate the distribution of the number of particular events that will occur. This idea led to the following approach, the so-called unified approach (1984):
The model is defined as follows: a candidate must be chosen over some time interval 
from an unknown number of highly-rated 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 candidates have the same, but mutually independent, density of arrival time
on and let 
denote the corresponding arrival time distribution function, that is
, 
.
Let 
be such that 
Consider the strategy of waiting and watching all candidates until time and then selecting, if possible, the first candidate after time who is better than all the previous ones. Then this strategy, called the 1/e-strategy, has the following properties:
1/e-strategy
(i) yields, for all , a probability of success of at least 1/e,
(ii) is the only strategy guaranteeing this lower bound of 1/e on the probability of success, and this bound is optimal,
(iii) selects, if there is at least one applicant, no one with probability exactly 1/e.
The 1/e law, proved in 1984 by F. Thomas Bruss, came as a surprise. The reason was that a value near 1/e had previously been thought unattainable in the model for unknown, whereas this value of 1/e was now achieved as a lower bound on the probability of success, and this in a model with possibly weaker hypotheses (see, e.g., Math. Reviews 85: m).
The 1/e law is sometimes confused with the solution to 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 candidates and since the model, based on the arrival time distribution F, is more convenient for applications.
According to Ferguson 1989 harvnb error: multiple targets (2 ×): CITEREFFerguson1989 ( help ), the secretary problem first appeared in print when it was presented by Martin Gardner in his «Mathematical Games» column in the February 1960 issue of Scientific American. Here is how Gardner phrased it: «Ask someone to take as many sheets of paper as he likes, and write a different positive number on each one. The numbers may range from small fractions of a unit to a number as large as a googol(1 followed by a hundred zeros) or even larger. These sheets are turned face down and shuffled over on the table. One at a time, you turn the sheets face up. The goal is to stop turning when you reach the number that you believe is the largest in the series. You cannot go back and choose a previously turned sheet. If you turn over all the sheets, then of course you must choose the last one».
In the article "Who Solved the Secretary Problem?" Ferguson 1989 harvnb error: multiple targets (2 ×): CITEREFFerguson1989 ( help ) 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, secretly writes different numbers oncards. Bob, the stopping player, observes the actual values and can stop turning over cards whenever he wants, winning if the last card turned over has the overall maximum value. The difference from the basic secretary problem is that Bob observes the actual values written on the cards, which he can use in his decision-making procedures. The numbers on the cards are analogous to the quantitative qualities of the applicants in some versions of the secretary problem. The joint probability distribution of the numbers is under Alice's control.
Bob wants to guess the maximum number with the highest possible probability, while Alice's goal is to keep that probability as low as possible. It is not optimal for Alice to draw numbers independently from some fixed distribution, and she can play better by choosing random numbers in some dependent manner. For
Alice has no minimax strategy, which is closely related to T. Cover's paradox. But for
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 relative ranks ( Gnedin 1994 ).
The remainder of the article again considers the secretary problem for a known number of candidates.
Stein, Seale & Rapoport 2003 derived the expected probabilities of success for several psychologically plausible heuristics that could be used in the secretary problem. They examined the following heuristics:
Each heuristic has a single parameter y. The figure (shown at right) shows the expected probabilities of success for each heuristic as a function of y for problems with n = 80.
Searching for the single best candidate may seem like a rather strict task. One could imagine that an interviewer would prefer to hire a more valuable applicant than a less valuable one, and not only care about getting the best. That is, the interviewer would derive some value from selecting a candidate who is not necessarily the best, and the value obtained increases together with the value of the selected candidate.
To model this problem, suppose that candidates have «true» values that are random variables X, drawn iid from a uniform distribution on [0, 1]. As in the classical problem described above, the interviewer only observes whether each candidate is the best so far (a candidate), must accept or reject each on the spot, and must accept the last one if reached. (To be clear, the interviewer does not learn the actual relative rank of every candidate. He/she only learns whether the candidate has relative rank 1.) However, in this version the payoffis given by the true value of the selected applicant. For example, if he/she selects a candidate whose true value is 0.8, then he/she earns 0.8. The interviewer's task is to maximize the expected value of the selected applicant.
Since the applicants' values are iid draws from a uniform distribution on [0, 1], the expected value of the t-th applicant given that
is given by
As in the classical problem, the optimal policy is given by a threshold, which for this problem we denote as 
, at which the interviewer should begin accepting candidates. Bearden 2006 showed that c is either
or 
. (In fact, whichever is closest to
.) This follows from the fact that, given a problem with applicants, the expected payoff for some arbitrary threshold 
is
Differentiating 
with respect to c, we obtain
Since 
for all admissible values of , we find that 
is maximized at 
. Since V is convex in, the optimal integer threshold must be either or . Thus, for most values of, the interviewer will begin accepting candidates earlier in the cardinal-payoff version than in the classical version, where the goal is to select the single best candidate. Note that this is not an asymptotic result: it holds for all. However, this is not the optimal policy for maximizing the expected value from a known distribution. In the case of a known distribution, the optimal slack can be calculated using dynamic programming.
A more general form of this problem, presented by Palley and Kremer (2014) , assumes that as each new applicant arrives, the interviewer observes their rank relative to all candidates previously observed. This model corresponds to the concept of the interviewer learningas they continue the search process, accumulating a set of past data that they can use to evaluate new candidates as they arrive. The advantage of this so-called partial information model is that the decisions and outcomes achieved with knowledge of relative rank information can be directly compared with the corresponding optimal decisions and outcomes if the interviewer had been given complete information about the value of every candidate. This full information problem, in which candidates are drawn independently from a known distribution and the interviewer seeks to maximize the expected value of the selected candidate, was originally solved by Moser (1956), Sakaguchi (1961), and Karlin (1962).
There are several variants of the secretary problem that also have simple and elegant solutions.
One variant replaces the desire to select the best with the desire to select 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 equals exactly
. This probability tends to 1/4 as n tends to infinity, which shows that it is easier to select the best than the second best.
For the second variant, the number of choices allowed is greater than one. In other words, the interviewer hires not one secretary, but, say, accepts a group of students from a pool of candidates. Under the assumption that success is achieved if and only if all the selected candidates outrank all the unselected candidates, this is again a problem that can be solved. In Vanderbei 1980 it was shown that for even n, and wanting to select exactly half of the candidates, the optimal strategy gives a probability of success equal to
.
Another variant is selecting the best 
secretaries from a pool of , again in an online algorithm. This leads to a strategy related to the classical one, and a cutoff thresholdfor which the classical problem is a special case, Ghirdar 2009 .
The player is allowed choices, and wins if any of the choices is the best. Gilbert and Mosteller 1966 showed that the optimal strategy is given by a threshold strategy (a cutoff strategy). The optimal strategy belongs to the class of strategies defined by a set of threshold numbers
, where 
. The first choice should be used for the first candidates, starting from the
-th candidate, and once the first option has been used, the second option should be used for the first applicant starting from the 
-th applicant, and so on.
Gilbert and Mosteller showed that 
. For further cases, where
see Matsui & Ano 2016 (for example,
).
When 
the probability of winning converges to 
( Gilbert and Mosteller, 1966 ). Matsui and Ano 2016 showed that for any positive integer, the probability of winning (of choice of secretary) converges to 
where 
. Thus the probability of winning converges to 
and 
when 
respectively.
Experimental psychologists and economists have studied the behavior of real people making decisions in secretary-problem situations. To a large extent, this work has shown that people tend to stop searching too soon. This can be explained, at least in part, by the cost of evaluating candidates. In real-world settings this may mean that people do not search enough whenever they face problems in which alternative solutions are encountered sequentially. For example, when trying to decide which gas station along the highway to stop at for refueling, people may not search enough before stopping. If this is true, then they will pay more for gasoline 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 the study of behavioral operations.
Although there is a substantial body of neuroscientific research on the integration of information or the representation of beliefs in perceptual decision-making tasks using both animals and humans , relatively little is known about how this decision is made to stop gathering information.
Researchers studied the neural basis of solving the secretary problem in healthy volunteers using functional MRI. [10] A Markov decision process (MDP) was used to quantify the cost of continuing to search versus committing to the current option. Decisions to select an option versus continuing to decide involved the parietal and dorsolateral prefrontal cortex, as well as the ventral striatum, anterior insula, and anterior cingulate cortex. Thus, brain regions previously implicated in evidence integration and reward representation encode the crossing of threshold values that trigger decisions to commit to a choice.
The secretary problem was apparently introduced in 1949 by Merrill M. Flood, who called it the bride problem in a lecture he gave that same year. He mentioned it several times during the 1950s, for example during a talk at a Purdue conference on May 9, 1958, and it eventually became widely known in folklore, although nothing was published about it at the time. In 1958 he sent a letter to Leonard Gillman with copies to a dozen friends, including Samuel Karlin and D. Robbins, presenting a proof of the optimal strategy, with an appendix by R. Palermo, who proved that among all strategies the dominant one has the form «unconditionally reject the first p, 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 independently developed a similar problem in 1958; they called it the «googol game». Fox and Marnie did not know the optimal solution; Gardner sought advice from Leo Moser, who (together with J. R. Pounder) provided the correct analysis for publication in the magazine. Soon after, several mathematicians wrote to Gardner to tell him about an equivalent problem they had heard through the grapevine, all of which can most likely be traced back to Flood's original work.
The best-choice 1/e law is due to F. Thomas Bruss (1984).
Ferguson (1989) has an extensive bibliography and points out that a similar (but different) problem was considered by Arthur Cayley in 1875, and even by Johannes Kepler long before that.
The secretary problem can be generalized to the case where there are several different positions. Again, there areapplicants arriving in random order. When a candidate arrives, she reveals a set of nonnegative numbers. Each value indicates her qualification for one of the positions. The administrator must not only decide whether to accept the applicant, but, if so, must also assign her permanently to one of the positions. The task is to find the assignment in which the sum of qualifications is as large as possible. This problem is identical to finding a maximum-weight matching in an edge-weighted bipartite graph, wherenodes on one side arrive online in random order. Thus it is a special case of the online bipartite matching problem.
By generalizing the classical algorithm for the secretary problem, one can obtain an assignment in which the expected sum of qualifications is only a factor of 
less than the optimal (offline) assignment.
Comments