View source for Secretary problem

{{Short description|Mathematical problem involving optimal stopping theory}}
{{Use dmy dates|date=March 2020}}
{{secretary_problem.svg}}
[[File:secretary_problem_graphs.svg|thumb|Graphs of probabilities of getting the best candidate (red circles) from ''n'' applications, and ''k''/''n'' (blue crosses) where ''k'' is the sample size]]
The '''secretary problem''' demonstrates a scenario involving [[optimal stopping]] theory<ref name=TomFer89>{{cite journal |last1=Ferguson |first1=Thomas S. |title=Who Solved the Secretary Problem? |journal=Statistical Science |date=August 1989 |volume=4 |issue=3 |pages=282–289 |doi=10.1214/ss/1177012493 |doi-access=free }}</ref><ref name="Hill2009">{{Cite journal | first1 = Theodore P. | last1 = Hill| author-link1 = Theodore P. Hill | doi = 10.1511/2009.77.126 | title = Knowing When to Stop | journal = [[American Scientist]] | year = 2009 | volume = 97 | issue = 2| pages = 126–133 | s2cid = 124798270| issn = 1545-2786}} For French translation, see [https://web.archive.org/web/20110721020330/http://www.pourlascience.fr/ewb_pages/f/fiche-article-savoir-quand-s-arreter-22670.php cover story] in the July issue of ''Pour la Science'' (2009).</ref> 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'''.<ref>{{cite news |last1=Thomson |first1=Jonny |title=Mathematicians suggest the "37% rule" for your life's biggest decisions |url=http://bigthink.com/neuropsych/the-37-percent-rule/ |access-date=6 February 2024 |work=Big Think |date=21 April 2022}}</ref>

The basic form of the problem is the following: imagine an administrator who wants to hire the best secretary out of <math>n</math> 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 <math>1/e</math> (where ''[[e (mathematical constant)|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 <math> \sim n/e</math> 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 <math>1/e</math> stopping rule, because the probability of stopping at the best applicant with this strategy is already about <math>1/e</math> for moderate values of <math>n</math>. 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. The secretary problem is an [[exploration–exploitation dilemma]].

==Formulation==
Although there are many variations, the basic problem can be stated as follows:

* There is a single position to fill. 
* There are ''n'' applicants for the position, and the value of ''n'' is known.
* The applicants, if all seen together, can be ranked from best to worst unambiguously.
* The applicants are interviewed sequentially in random order, with each order being equally likely.
* Immediately after an interview, the interviewed applicant is either accepted or rejected, and the decision is irrevocable.
* The decision to accept or reject an applicant can be based only on the relative ranks of the applicants interviewed so far.
* The objective of the general solution is to have the highest probability of selecting the best applicant of the whole group.  This is the same as maximizing the expected payoff, with payoff defined to be one for the best applicant and zero otherwise.

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''&nbsp;−&nbsp;1 applicants (let applicant ''M'' be the best applicant among these ''r''&nbsp;−&nbsp;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.{{citation needed|date=June 2016}} (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

:<math>
\begin{align}
P(r)
&= \sum_{i=r}^{n}
P\left(\text{applicant } i \text{ is selected} \cap \text{applicant } i \text{ is the best}\right)
\\
&= \sum_{i=r}^{n}
P\left(\text{applicant } i \text{ is selected} | \text{applicant } i \text{ is the best}\right) \cdot
P\left(\text{applicant } i \text{ is the best}\right)
\\
&= \left[ \sum_{i=1}^{r-1} 0
+ \sum_{i=r}^{n} P\left( \left.
\begin{array}{l}
\text{the best of the first } i - 1 \text{ applicants} \\
\text{is in the first } r-1 \text{ applicants}
\end{array} \right|  \text{applicant } i \text{ is the best}
\right) \right] \cdot \frac{1}{n}
\\
&= \left[\sum_{i=r}^{n} \frac{r-1}{i-1}\right] \cdot \frac{1}{n}
 \\
&=\frac{r-1}{n} \sum_{i=r}^{n} \frac{1}{i-1}.
\end{align}
</math>

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''&nbsp;−&nbsp;1 applicants is among the first ''r''&nbsp;−&nbsp;1 applicants that were rejected. Letting ''n'' tend to infinity, writing <math>x</math> 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

:<math>
P(x)=x \int_{x}^{1}\frac{1}{t}\,dt = -x \ln(x)\;.
</math>

Taking the derivative of ''P''(''x'') with respect to <math>x</math>, 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.{{NoteTag|<syntaxhighlight lang="python">
import numpy as np
import pandas as pd

# Define the function for which you want to find the maximum
def func(r, n):
    if r == 1:
        return 0
    else:
        return (r - 1) / n * np.sum([1 / (i - 1) for i in range(r, n + 1)])

# Define a function to solve the problem for a specific n
def solve(n):
    values = [func(r, n) for r in range(1, n + 1)]
    r_max = np.argmax(values) + 1
    return r_max, values[r_max - 1]

# Define a function to print the results as a Markdown table
def print_table(data):
    df = pd.DataFrame(data, columns=["r", "Max Value"], index=range(1, len(data) + 1))
    df.index.name = "n"

    # Convert the DataFrame to Markdown and print
    print(df.transpose().to_markdown())


n_max = 10

# Print the table for n from 1 to n_max
data = [solve(n) for n in range(1, n_max + 1)]
print_table(data)
</syntaxhighlight>}}

{| class="wikitable"
|-
! <math>n</math>
! 1
! 2
! 3
! 4
! 5
! 6
! 7
! 8
! 9
!10
|-
| <math>r</math>
| 1
| 1
| 2
| 2
| 3
| 3
| 3
| 4
| 4
|4
|-
| <math>P</math>
| 1.000
| 0.500
| 0.500
| 0.458
| 0.433
| 0.428
| 0.414
| 0.410
| 0.406
|0.399
|}

The probability of selecting the best applicant in the classical secretary problem converges toward <math>1/e\approx 0.368</math>.

==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.{{Citation needed|date=May 2022}}

==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 <math> n </math> 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 <math>N </math> with a known distribution of  <math>P(N=k)_{k=1,2,\cdots} </math> (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 <math>N</math>, 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 <math>[0,T]</math> from an unknown number <math> N</math> 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 <math>f</math> on <math>[0,T]</math> and let  <math>F</math> denote the corresponding arrival time distribution function, that is

: <math>F(t) = \int_{0}^{t} f(s)ds </math>, <math>\, 0\le t\le T</math>.

Let <math>\tau</math> be such that <math> F(\tau)=1/e.</math> Consider the strategy to wait and observe all applicants up to time <math>\tau </math> and then to select, if possible, the first candidate after time <math>\tau </math> which is better than all preceding ones. Then this strategy, called ''1/e-strategy'', has the following properties:

The ''1/e-strategy''

:(i) yields for all <math>N</math> a success probability of at least 1/e,

:(ii) is a minimax-optimal strategy for the selector who does not know <math>N</math>,

:(iii) selects, if there is at least one applicant, none at all 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 of about 1/e had been considered before as being out of reach in a model for unknown <math> N </math>, 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 <math>N</math>>2. A simple example is the strategy which selects (if possible) the first relatively best candidate after time <math>\tau </math> provided that at least one applicant arrived before this time, and otherwise selects (if possible) the second relatively best candidate after time <math>\tau </math>.{{sfn|Gnedin|2021}}
 
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==
In the article "Who solved the Secretary problem?" ([[Thomas S. Ferguson|Ferguson]], 1989){{r|TomFer89}}, it's claimed the secretary problem first appeared in print in [[Martin Gardner]]'s February 1960 [[Mathematical Games column]] in ''[[Scientific American]]:''<blockquote>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.{{sfn|Gardner|1966}}</blockquote>Ferguson pointed out that the secretary ''game'' remained unsolved, as a [[zero-sum game]] with two antagonistic players.{{r|TomFer89}} In this game:

* Alice, the informed player, writes secretly distinct numbers on <math>n</math> 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. 
* 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. 

The difference with the basic secretary problem are two:

* Alice does not have to write numbers uniformly at random. She may write them according to any [[joint probability distribution]] to trick Bob.
* Bob observes the actual values written on the cards, which he can use in his decision procedures.

=== Strategic analysis ===
Alice first writes down n numbers, which are then shuffled. So, their ordering does not matter, meaning that Alice's numbers must be an [[Exchangeable random variables|exchangeable random variable sequence]] <math>X_1, X_2, ..., X_n</math>. Alice's strategy is then just picking the trickiest exchangeable random variable sequence.

Bob's strategy is formalizable as a [[Stopping time|stopping rule]] <math>\tau</math> for the sequence <math>X_1, X_2, ..., X_n</math>.

We say that a stopping rule <math>\tau</math> for Bob is a '''relative rank stopping strategy''' if it depends on only the relative ranks of <math>X_1, X_2, ..., X_n</math>, and not on their numerical values. In other words, it is as if someone secretly intervened after Alice picked her numbers, and changed each number in <math>X_1, X_2, ..., X_n</math> into its relative rank (breaking ties randomly). For example, <math>0.2, 0.3, 0.3, 0.1</math> is changed to <math>2, 3, 4, 1</math> or <math>2, 4, 3, 1</math> with equal probability. This makes it ''as if'' Alice played an exchangeable [[random permutation]] on <math>\{1, 2, ..., n\}</math>. Now, since the only exchangeable random permutation on <math>\{1, 2, ..., n\}</math> is just the uniform distribution over all permutations on <math>\{1, 2, ..., n\}</math>, the optimal relative rank stopping strategy is the optimal stopping rule for the secretary problem, given above, with a winning probability<math display="block">Pr(X_\tau = \max_{i\in 1:n} X_i) = \max_{r\in 1:n}\frac{r-1}{n} \sum_{i=r}^{n} \frac{1}{i-1}</math>Alice's goal then is to make sure Bob cannot do better than the relative-rank stopping strategy.

By the rules of the game, Alice's sequence must be exchangeable, but to do well in the game, Alice should not pick it to be independent. If Alice samples the numbers independently from some fixed distribution, it would allow Bob to do better. To see this intuitively, imagine if <math>n=2</math>, and Alice is to pick both numbers from the normal distribution <math>N(0, 1)</math>, independently. Then if Bob turns over one number and sees <math>-3</math>, then he can quite confidently turn over the second number, and if Bob turns over one number and sees <math>+3</math>, then he can quite confidently pick the first number. Alice can do better by picking <math>X_1, X_2</math> that are positively correlated.

So the fully formal statement is as below:<blockquote>Does there exist an exchangeable sequence of random variables <math>X_1, ..., X_n</math>, such that for ''any'' stopping rule <math>\tau</math>, <math display="block">Pr(X_\tau = \max_{i\in 1:n} X_i) \leq \max_{r\in 1:n}\frac{r-1}{n} \sum_{i=r}^{n} \frac{1}{i-1}</math>?</blockquote>

=== Solution ===
For <math>n=2</math>, if Bob plays the optimal relative-rank stoppings strategy, then Bob has a winning probability 1/2. Surprisingly, Alice has no [[minimax]] strategy, which is closely related to a paradox of [[Thomas M. Cover|T. Cover]]<ref>{{Citation |last=Cover |first=Thomas M. |title=Pick the Largest Number |date=1987 |url=https://isl.stanford.edu/people/cover/papers/paper73.pdf |work=Open Problems in Communication and Computation |pages=152 |editor-last=Cover |editor-first=Thomas M. |access-date=2023-06-25 |place=New York, NY |publisher=Springer |language=en |doi=10.1007/978-1-4612-4808-8_43 |isbn=978-1-4612-4808-8 |editor2-last=Gopinath |editor2-first=B.}}</ref> and the [[Two envelopes problem|two envelopes paradox]]. Concretely, Bob can play this strategy: sample a random number <math>Y</math>. If <math>X_1 > Y</math>, then pick <math>X_1</math>, else pick <math>X_2</math>. Now, Bob can win with probability strictly greater than 1/2. Suppose Alice's numbers are different, then condition on <math>Y \not\in [\min(X_1, X_2), \max(X_1, X_2)]</math>, Bob wins with probability 1/2, but condition on <math>Y \in [\min(X_1, X_2), \max(X_1, X_2)]</math>, Bob wins with probability 1. 

Note the random number <math>Y</math> can be sampled from ''any'' random distribution, as long as <math>Y \in [\min(X_1, X_2), \max(X_1, X_2)]</math> has a nonzero probability.

However, for any <math>\epsilon > 0</math>, Alice can construct an exchangeable sequence <math>X_1, X_2</math> such that Bob's winning probability is at most <math>1/2 + \epsilon</math>.{{r|TomFer89}}

But for <math>n>2</math>, 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.{{sfn|Gnedin|1994}}

==Heuristic performance==
The remainder of the article deals again with the secretary problem for a known number of applicants.

[[File:SecretaryProblemHeuristicPlot.png|thumb|upright=1.3|Expected success probabilities for three heuristics]]

{{harvnb|Stein|Seale|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 classical secretary problem for which ''y''&nbsp;=&nbsp;''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&nbsp;>&nbsp;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''&nbsp;=&nbsp;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 <math>n</math> applicants have "true" values that are [[random variable]]s ''X'' drawn [[i.i.d.]] from a [[Uniform distribution (continuous)|uniform distribution]] on [0,&nbsp;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,&nbsp;1], the [[expected value]] of the ''t''th applicant given that <math>x_{t}=\max\left\{x_1, x_2, \ldots, x_t\right\}</math> is given by

:<math>
E_{t}=E\left(X_{t}|I_{t}=1\right)=\frac{t}{t+1}.
</math>

As in the classical problem, the optimal policy is given by a threshold, which for this problem we will denote by <math>c</math>, at which the interviewer should begin accepting candidates. Bearden showed that ''c'' is either <math>\lfloor \sqrt n \rfloor</math> or <math>\lceil \sqrt n \rceil</math>.{{sfn|Bearden|2006}} (In fact, whichever is closest to <math> \sqrt n </math>.) This follows from the fact that given a problem with <math>n</math> applicants, the expected payoff for some arbitrary threshold <math>1 \le c \le n</math> is

:<math>
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}}.
</math>

Differentiating <math> V_{n}(c)</math> with respect to ''c'', one gets

: <math>\frac{\partial V}{\partial c} = \frac{ -{c}^{\,2}+n }{ 2{c}^{\,2}n }.</math>

[[File:RelativeRankLearning2.pdf|thumb|Learning in the partial-information sequential search paradigm. The numbers display the expected values of applicants based on their relative rank (out of m total applicants seen so far) at various points in the search. Expectations are calculated based on the case when their values are uniformly distributed between 0 and 1. Relative rank information allows the interviewer to more finely evaluate applicants as they accumulate more data points to compare them to.]]
Since <math>\partial^{\,2}V / \partial c^{\,2}<0</math> for all permissible values of <math>c</math>, we find that <math>V</math> is maximized at <math>c=\sqrt n</math>. Since ''V'' is convex in <math>c</math>, the optimal integer-valued threshold must be either <math>\lfloor \sqrt n \rfloor</math> or <math>\lceil \sqrt n \rceil</math>. Thus, for most values of <math>n</math> 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 <math>n</math>. Interestingly, if each of the <math>n</math> secretaries has a fixed, distinct value from <math>1</math> to <math>n</math>, then <math>V</math> is maximized at <math>c=\sqrt n - 1</math>, with the same convexity claims as before.<ref>{{Cite website|last1=Jones|first1=Maxwell|last2=Nene|first2=Advait|date=2024-08-20|title=Secretary Problem Variant Deep Dive|url=https://maxwelljon.es/blog/2024/secretaryproblem/}}</ref> For other known distributions, optimal play can be calculated via dynamic programming.

A more general form of this problem introduced by Palley and Kremer (2014)<ref>{{Cite journal|last1=Palley|first1=Asa B.|last2=Kremer|first2=Mirko|date=2014-07-08|title=Sequential Search and Learning from Rank Feedback: Theory and Experimental Evidence|url=https://pubsonline.informs.org/doi/abs/10.1287/mnsc.2014.1902|journal=Management Science|volume=60|issue=10|pages=2525–2542|doi=10.1287/mnsc.2014.1902|issn=0025-1909|url-access=subscription}}</ref> 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),<ref>{{Cite journal|last=Moser|first=Leo|date=1956|title=On a problem of Cayley|journal=Scripta Math|volume=22|pages=289–292}}</ref> Sakaguchi (1961),<ref>{{Cite journal|date=1961-06-01|title=Dynamic programming of some sequential sampling design|journal=Journal of Mathematical Analysis and Applications|language=en|volume=2|issue=3|pages=446–466|doi=10.1016/0022-247X(61)90023-3|issn=0022-247X|last1=Sakaguchi|first1=Minoru|doi-access=free}}</ref> and Karlin (1962).

==Other modifications==
There are several variants of the secretary problem that also have simple and elegant solutions.

=== Pick the second-best, using one try ===
One variant replaces the desire to pick the best with the desire to pick the second-best.<ref name="NonExtRose">{{cite journal |last1=Rose |first1=John S. |year=1982 |title=Selection of nonextremal candidates from a random sequence |journal=J. Optim. Theory Appl.|doi=10.1007/BF00934083 |pages=207–219|volume=38|issue=2 |s2cid=121339045 |issn=0022-3239}}</ref><ref name="AthSza">{{cite journal |last1=Szajowski |first1=Krzysztof |year=1982 |title=Optimal choice of an object with ath rank |journal=Matematyka Stosowana|series=Annales Societatis Mathematicae Polonae, Series III|doi=10.14708/ma.v10i19.1533 |pages=51–65|volume=10|number=19|issn=0137-2890}}</ref><ref name="postdoc">{{cite journal |last1=Vanderbei |first1=Robert J. |author-link=Robert J. Vanderbei |title=The postdoc variant of the secretary problem |journal=Mathematica Applicanda|series=Annales Societatis Mathematicae Polonae, Series III|url=https://wydawnictwa.ptm.org.pl/index.php/matematyka-stosowana/article/view/7076 |pages=3–13|volume=49|number=1|issn=2299-4009|date=2021-06-21 |doi=10.14708/ma.v49i1.7076 |url-access=subscription }}</ref> For this problem, the probability of success for an even number of applicants is exactly <math> \frac{0.25n^2}{n(n-1)} </math>. 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.

=== Pick the top-k ones, using k tries ===
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 <math>r=\left\lfloor\frac{n}{k e^{1 / k}}\right\rfloor</math> candidates without picking any one of them, then pick every candidate that is better than those first <math>r</math> candidates until we run out of candidates or picks. If <math>k</math> is held constant while <math>n\to\infty</math>, then the probability of success converges to <math>\frac{1}{ek}</math>.{{sfn|Girdhar|Dudek|2009}} By {{harvnb|Vanderbei|1980}}, if <math>k = n/2</math>, then the probability of success is <math>\frac{1}{n/2+1}</math>.

===Pick the best, using multiple tries===
In this variant, a player is allowed <math>r</math> 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 <math>(a_1, a_2, ..., a_r)</math>, where <math>a_1 > a_2 > \cdots > a_r</math>. 

Specifically, imagine that you have <math>r</math> letters of acceptance labelled from <math>1</math> to <math>r</math>. You would have <math>r</math> 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 <math>i</math> would send their letter of acceptance to the first candidate that is better than all candidates <math>1</math> to <math>a_i</math>. (Unsent letters of acceptance are by default given to the last applicants, the same as in the standard secretary problem.){{sfn|Gilbert|Mosteller|1966}}

At <math>n \rightarrow \infty</math> limit, each <math>a_i \sim ne^{-k_i}</math>, for some rational number <math>k_i</math>.{{sfn|Matsui|Ano|2016}}

==== Probability of winning ====
When <math>r=2</math>, the probability of winning converges to <math>e^{-1} + e^{-\frac{3}{2}} , (n \rightarrow \infty)</math>. More generally, for positive integers <math>r</math>, the probability of winning converges to <math>p_1 + p_2 + \cdots + p_r</math>, where <math>p_i = \lim_{n \rightarrow \infty} \frac{a_i}{n}</math>.{{sfn|Matsui|Ano|2016}}

{{sfn|Gilbert|Mosteller|1966}} computed up to <math>r=4</math>, with <math>e^{-1} + e^{-\frac{3}{2}} + e^{-\frac{47}{24}} + e^{-\frac{2761}{1152}}</math>.

{{harvnb|Matsui|Ano|2016}} gave a general algorithm. For example, <math>p_5 = e^{-\frac{4162637}{1474560}}</math>.

==Experimental studies==
Experimental [[Experimental psychology|psychologists]] and [[experimental economics|economists]] have studied the [[Decision making|decision behavior]] of actual people in secretary problem situations.<ref>Bearden, Murphy, and Rapoport, 2006; Bearden, Rapoport, and Murphy, 2006; Seale and Rapoport, 1997; [https://pubsonline.informs.org/doi/abs/10.1287/mnsc.2014.1902 Palley and Kremer, 2014]</ref> 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<ref>{{cite journal |last1=Shadlen |first1=M. N. |last2=Newsome |first2=W. T. |title=Motion perception: seeing and deciding. |journal=Proceedings of the National Academy of Sciences |date=23 January 1996 |volume=93 |issue=2 |pages=628–633 |doi=10.1073/pnas.93.2.628 |pmid=8570606 |pmc=40102 |bibcode=1996PNAS...93..628S |doi-access=free }}</ref><ref>{{cite journal |last1=Roitman |first1=Jamie D. |last2=Shadlen |first2=Michael N. |title=Response of Neurons in the Lateral Intraparietal Area during a Combined Visual Discrimination Reaction Time Task |journal=The Journal of Neuroscience |date=1 November 2002 |volume=22 |issue=21 |pages=9475–9489 |doi=10.1523/JNEUROSCI.22-21-09475.2002 |pmid=12417672 |pmc=6758024 }}</ref> and human subjects,<ref>{{cite journal |last1=Heekeren |first1=Hauke R. |last2=Marrett |first2=Sean |last3=Ungerleider |first3=Leslie G. |title=The neural systems that mediate human perceptual decision making |journal=Nature Reviews Neuroscience |date=9 May 2008 |volume=9 |issue=6 |pages=467–479 |doi=10.1038/nrn2374 |pmid=18464792 |s2cid=7416645 }}</ref> 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]].<ref>{{cite journal |last1=Costa |first1=V. D. |last2=Averbeck |first2=B. B. |title=Frontal-Parietal and Limbic-Striatal Activity Underlies Information Sampling in the Best Choice Problem |journal=Cerebral Cortex |date=18 October 2013 |volume=25 |issue=4 |pages=972–982 |doi=10.1093/cercor/bht286 |pmid=24142842 |pmc=4366612 }}</ref> 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 cortex|parietal]] and [[dorsolateral prefrontal cortex|dorsolateral prefrontal]] cortices, as well as [[ventral striatum]], [[Insular cortex|anterior insula]], and [[anterior cingulate]]. Therefore, brain regions previously implicated in evidence integration and [[Reward system|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 University|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".{{sfn|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.{{sfn|Gardner|1966|loc=Problem 3}}

The 1/''e''-law of best choice is due to [[F. Thomas Bruss]].{{sfn|Bruss|1984}}

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#Second marriage|Johannes Kepler]] long before that, who spent 2 years investigating 11 candidates for marriage during 1611 -- 1613 after the death of his first wife.{{sfn|Ferguson|1989}}

==Combinatorial generalization==
The secretary problem can be generalized to the case where there are multiple different jobs. Again, there are <math>n</math> applicants coming in random order. When a candidate arrives, he 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 <math>n</math> nodes of one side arrive online in random order. Thus, it is a special case of the [[Matching (graph theory)#Online bipartite matching|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 <math>e</math> less than an optimal (offline) assignment.<ref>{{cite book |doi=10.1007/978-3-642-40450-4_50 |chapter=An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions |title=Algorithms – ESA 2013 |volume=8125 |pages=589–600 |series=Lecture Notes in Computer Science |year=2013 |last1=Kesselheim |first1=Thomas |last2=Radke |first2=Klaus |last3=Tönnis |first3=Andreas |last4=Vöcking |first4=Berthold |isbn=978-3-642-40449-8 }}</ref>

==See also==
{{Portal|Economics|Mathematics}}
{{Commons}}
* [[Assignment problem]]
* [[Odds algorithm]]
* [[Optimal stopping]]
* [[Robbins' problem]]
* [[Search theory]]
* [[Stable marriage problem]]
* [[Exploration–exploitation dilemma]]

==Notes==
{{Reflist|30em}}

==References==
* {{Cite journal|last=Bearden |first=J.N. |title=A new secretary problem with rank-based selection and cardinal payoffs |journal=Journal of Mathematical Psychology |volume=50 |pages=58–9 |year=2006 |doi=10.1016/j.jmp.2005.11.003 }}
* {{Cite journal|author=Bearden, J.N.|author2=Murphy, R.O.|author3=Rapoport, A. |title=A multi-attribute extension of the secretary problem: Theory and experiments |journal=Journal of Mathematical Psychology |volume=49 |pages=410–425 |year=2005 |doi=10.1016/j.jmp.2005.08.002|issue=5 |citeseerx=10.1.1.497.6468 |s2cid=9186039 }}
* {{cite journal |last1=Bearden |first1=J. Neil |last2=Rapoport |first2=Amnon |last3=Murphy |first3=Ryan O. |title=Sequential Observation and Selection with Rank-Dependent Payoffs: An Experimental Study |journal=Management Science |date=September 2006 |volume=52 |issue=9 |pages=1437–1449 |doi=10.1287/mnsc.1060.0535 }}
* {{cite journal |last1=Bruss |first1=F. Thomas |author-link=F. Thomas Bruss |title=Sum the odds to one and stop |journal=The Annals of Probability |date=June 2000 |volume=28 |issue=3 |pages=1384–1391 |doi=10.1214/aop/1019160340 |doi-access=free }}
* {{cite journal |last1=Bruss |first1=F. Thomas |author-link=F. Thomas Bruss |title=A note on bounds for the odds theorem of optimal stopping |journal=The Annals of Probability |date=October 2003 |volume=31 |issue=4 |pages=1859–1961 |doi=10.1214/aop/1068646368 |doi-access=free |hdl=2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/181669 |hdl-access=free }}
* {{cite journal |last1=Bruss |first1=F. Thomas |title=A Unified Approach to a Class of Best Choice Problems with an Unknown Number of Options |journal=The Annals of Probability |date=August 1984 |volume=12 |issue=3 |pages=882–889 |doi=10.1214/aop/1176993237 |doi-access=free }}
* {{cite letter|first=Merrill R.|last=Flood|title=Proof of the optimum strategy|year=1958|recipient=Martin Gardner|publisher=Stanford University Archives|series=Martin Gardner papers series 1, box 5, folder 19}}
* {{Cite journal|doi=10.2307/1402748 |author=Freeman, P.R. |title=The secretary problem and its extensions: A review |journal=International Statistical Review / Revue Internationale de Statistique |volume=51 |issue=2 |pages=189–206 |year=1983 |jstor=1402748 }}
* {{cite book|first1=Martin|last1=Gardner|title=New Mathematical Diversions from Scientific American|publisher=Simon and Schuster|year=1966|chapter=3}} [reprints his original column published in February 1960 with additional comments]
*{{cite book |doi=10.1109/CRV.2009.30 |chapter=Optimal Online Data Sampling or How to Hire the Best Secretaries |title=2009 Canadian Conference on Computer and Robot Vision |pages=292–298 |year=2009 |last1=Girdhar |first1=Yogesh |last2=Dudek |first2=Gregory |isbn=978-1-4244-4211-9 |citeseerx = 10.1.1.161.41 |s2cid=2742443 }}
*{{Cite journal|last1=Gilbert |first1=J |last2=Mosteller |first2=F |title= Recognizing the Maximum of a Sequence |journal=Journal of the American Statistical Association |volume=61 |pages=35–73 |year=1966 |issue=313 |doi=10.2307/2283044 |jstor=2283044 }}
* {{Cite journal|last=Gnedin|first=A.|title=A solution to the game of Googol  |journal=Annals of Probability |volume=22 |pages=1588–1595  |year=1994 |doi=10.1214/aop/1176988613|issue=3|doi-access=free}}
* {{Cite journal|last=Gnedin|first=A.|title=The best choice problem with random arrivals: How to beat the 1/e-strategy  
|journal=Stochastic Processes and Their Applications |year=2021 |volume=145 |pages=226–240 |doi=10.1016/j.spa.2021.12.008|s2cid=245449000 |url=https://qmro.qmul.ac.uk/xmlui/handle/123456789/75838 }}
* Hill, T.P. "[https://www.americanscientist.org/article/knowing-when-to-stop Knowing When to Stop]". ''American Scientist'', Vol. 97, 126-133 (2009). (For French translation, see [https://web.archive.org/web/20110721020330/http://www.pourlascience.fr/ewb_pages/f/fiche-article-savoir-quand-s-arreter-22670.php cover story] in the July issue of ''Pour la Science'' (2009))
*{{cite book |last1=Ketelaar |first1=Timothy |last2=Todd |first2=Peter M.|doi=10.1007/978-94-010-0618-7_7 |chapter=Framing Our Thoughts: Ecological Rationality as Evolutionary Psychology's Answer to the Frame Problem |title=Conceptual Challenges in Evolutionary Psychology |volume=27 |pages=179–211 |series=Studies in Cognitive Systems |year=2001  |isbn=978-94-010-3890-4 }}
*{{cite journal |last1=Matsui |first1=T |last2=Ano | first2=K |title=Lower bounds for Bruss' odds problem with multiple stoppings |journal=[[Mathematics of Operations Research]] |volume=41 |pages=700–714 |year=2016 |issue=2 |doi=10.1287/moor.2015.0748|arxiv=1204.5537 |s2cid=31778896 }}
* {{Cite book|author=Miller, Geoffrey F. |title=The mating mind: how sexual choice shaped the evolution of human nature |publisher=Anchor Books |year=2001 |isbn=978-0-385-49517-2 }}
* {{cite journal |last1=Sardelis |first1=Dimitris A. |last2=Valahas |first2=Theodoros M. |title=Decision Making: A Golden Rule |journal=The American Mathematical Monthly |date=March 1999 |volume=106 |issue=3 |pages=215 |doi=10.2307/2589677 |jstor=2589677 }}
* {{Cite journal|author=Seale, D.A.|author2=Rapoport, A. |title=Sequential decision making with relative ranks: An experimental investigation of the 'secretary problem' |journal=Organizational Behavior and Human Decision Processes |volume=69 |pages=221–236 |year=1997 |doi=10.1006/obhd.1997.2683|issue=3 }}
* {{Cite journal|last1=Stein |first1=W.E. |last2=Seale |first2=D.A. |last3=Rapoport |first3=A. |title=Analysis of heuristic solutions to the best choice problem |journal=European Journal of Operational Research |volume=151 |pages=140–152 |year= 2003|doi=10.1016/S0377-2217(02)00601-X }}
*{{cite journal |last1=Vanderbei |first1=R. J. |title=The Optimal Choice of a Subset of a Population |journal=[[Mathematics of Operations Research]] |date=November 1980 |volume=5 |issue=4 |pages=481–486 |doi=10.1287/moor.5.4.481}}
* {{cite report |last1=Vanderbei |first1=Robert J. |author-link=Robert J. Vanderbei |year=2012 |title=The postdoc variant of the secretary problem |url=https://vanderbei.princeton.edu/tex/PostdocProblem/PostdocProb.pdf |citeseerx=10.1.1.366.1718 }}

==External links==
* {{OEIS el|1=A054404|2=Number of daughters to wait before picking in sultan's dowry problem with n daughters}} 
* {{MathWorld | urlname=SultansDowryProblem | title=Sultan's Dowry Problem}}
* {{cite web|url=http://www.spotlightmind.com/optimal-search |archive-url=https://web.archive.org/web/20170104050807/http://www.spotlightmind.com/optimal-search |archive-date=4 January 2017 |author= Neil Bearden |url-status=usurped | title = Optimal Search (Secretary Problems)}}
* [https://www.math.ucla.edu/~tom/Stopping/Contents.html ''Optimal Stopping and Applications''] book by Thomas S. Ferguson

== Notes ==
<references group="note" />{{Authority control}}

{{DEFAULTSORT:Secretary Problem}}
[[Category:Decision theory]]
[[Category:Sequential methods]]
[[Category:Matching (graph theory)]]
[[Category:Optimal decisions]]
[[Category:Probability problems]]
[[Category:Mathematical optimization in business]]