Secretary Problem Variants & Extensions
Variants & Extensions of the Secretary Problem
The classical secretary problem is only the starting point.
Changing the information available, the objective, the number of choices, or the horizon leads to genuinely different optimal-stopping problems.
The classical benchmark
There are \(n\) candidates whose absolute ranks form a uniformly random permutation of
\[ 1,2,\ldots,n, \]
with rank \(1\) best. Write \(X_k\) for the absolute rank of the candidate arriving at position \(k\), and \(R_k\) for that candidate’s relative rank among the first \(k\) arrivals.
Candidates are observed sequentially. At time \(k\), only the candidate’s relative rank among the first \(k\) observations is known. Decisions are irrevocable, and only one candidate may be selected.
The objective is
\[ \max_{\tau}\Pr(X_\tau=1). \]
For a threshold \(1\le r<n\), reject the first \(r\) candidates and then accept the first subsequent record. Its success probability is
\[ P_n(r) = \frac{r}{n} \sum_{j=r+1}^{n}\frac{1}{j-1}. \]
For \(r=0\), the first candidate is selected immediately and \(P_n(0)=1/n\).
As \(n\to\infty\), a choice of optimal threshold \(r_n^\star\) satisfies
\[ \frac{r_n^\star}{n}\to \frac1e, \]
and the optimal success probability also converges to \(1/e\).
The extensions below can be organized by asking which part of this benchmark is changed.
1. Full-information secretary problem
Problem
Instead of seeing only relative ranks, suppose the numerical observations
\[ Y_1,\ldots,Y_n\overset{\mathrm{iid}}{\sim}F \]
are revealed sequentially, where \(F\) is a known continuous distribution. Here \(Y_k\) is an observed value, not the absolute rank \(X_k\) used in the classical model.
The objective is to maximize
\[ \Pr\!\left(Y_\tau=\max_{1\le j\le n}Y_j\right). \]
What changes?
The numerical value of the current observation contains information about how likely future observations are to exceed it.
The optimal decision therefore depends not only on whether the current observation is a record, but also on how large that record is.
Optimal-strategy structure
Using the probability-integral transform,
\[ U_i=F(Y_i), \]
the problem can be reduced to independent \(U(0,1)\) observations.
The optimal rule is described by time-dependent critical values: a record is accepted only when its value is sufficiently large relative to the number of observations remaining.
Interactive first-decision experiment (uniform observations)
To obtain closed-form, verifiable stopping decisions, the experiment uses \(Y_1,\ldots,Y_n\overset{\mathrm{iid}}{\sim}U(0,1)\) with \(n=2\) or \(n=3\). After seeing the first value \(x\), accepting wins with probability \(x^{n-1}\).
Rejecting and then acting optimally has probability
\[ C_2(x)=1-x, \]
and
\[ C_3(x)= \begin{cases} \frac34-\frac{x^2}{2},&0\le x\le\frac12,\\ \frac12+x-\frac{3x^2}{2},&\frac12<x\le1. \end{cases} \]
For \(n=3\), if the first value \(x\) is rejected, the second observation \(y\) should be accepted only if it is a record and \(y\ge 1/2\); otherwise the last observation is chosen only when it sets a new record. Integrating over the second observation gives \(C_3(x)\) above.
Thus the first-observation acceptance thresholds are \(1/2\) for \(n=2\) and \((1+\sqrt6)/5\approx0.68990\) for \(n=3\). These are first-stage thresholds, not the full-information rule for an arbitrary horizon.
Full-information: select or continue?
Accept now
Continue optimally
First-stage cutoff:
Assumptions: independent, identical and continuous Uniform(0,1) observations. Exact analytical continuation formulas; probabilities shown as rounded percentages.
Connection to the classical model
Both problems seek the overall maximum.
The difference is informational:
- no information: only relative ranks are observed;
- full information: the actual values are observed.
Gilbert and Mosteller developed the foundational analysis of both settings (Gilbert and Mosteller (1966)).
2. The postdoc problem: selecting the second best
Problem
Change the reward from selecting absolute rank \(1\) to selecting absolute rank \(2\):
\[ \max_{\tau}\Pr(X_\tau=2). \]
The arrival order is still uniformly random, decisions remain irrevocable, and only relative ranks are observed.
What changes?
The current record is no longer the only potentially useful candidate: a candidate with current relative rank \(2\) can also be the overall second best. Relative ranks \(a\ge3\) have zero immediate success probability. Thus changing the reward changes the stopping decisions that must be compared, even though the observed relative-rank information remains the same.
Interactive postdoc decision (exact backward induction)
Conditional on observing relative rank \(a\) at position \(k\), the probability that the current candidate has absolute rank \(2\) is
\[ g_{n,k}(a)= \begin{cases} \dfrac{k(n-k)}{n(n-1)},&a=1,\\[4pt] \dfrac{k(k-1)}{n(n-1)},&a=2,\\[4pt] 0,&a\ge3. \end{cases} \]
The relative ranks are independent with \(R_k\) uniform on \(\{1,\ldots,k\}\). Let \(V_{n+1}=0\) and let \(V_k\) be the maximum probability of selecting absolute rank \(2\) before observing relative rank \(R_k\). Then
\[ V_k=\frac1k\sum_{a=1}^k\max\{g_{n,k}(a),V_{k+1}\}, \qquad k=n,n-1,\ldots,1. \]
At position \(k\), select when \(g_{n,k}(a)\ge V_{k+1}\) and this success probability is positive; otherwise continue. When tied at zero, the experiment displays continuation. This dynamic program optimizes over all admissible decisions based on observed relative ranks.
Postdoc problem: select rank 2
Select now
Continue optimally
Optimal win probability before the first candidate:
Assumptions: uniformly random arrival order, relative ranks only, one irrevocable selection. Calculations use the exact Bellman recursion and display rounded percentages.
Connection to the classical model
The information structure is unchanged. Only the reward changes:
\[ \mathbf 1_{\{X_\tau=1\}} \quad\longrightarrow\quad \mathbf 1_{\{X_\tau=2\}}. \]
This makes the postdoc problem a particularly useful example of how the optimal rule can change when the target rank changes. For further analysis of the standard postdoc problem and its relationship to best-or-worst selection, see Bayón et al. (2018).
3. Multiple-choice and dowry problems
Problem
Suppose the decision maker is allowed more than one selection.
With \(m\) available choices, the decision maker chooses stopping times
\[ \tau_1<\tau_2<\cdots<\tau_m. \]
The success event depends on the particular model—for example, whether one of the selected observations is the overall best, or whether several top ranks must be captured.
Sakaguchi’s contribution
Sakaguchi’s work is an important early part of this branch of the literature.
His 1978 paper, Dowry Problems and OLA Policies (Sakaguchi (1978)), studied secretary-type stopping rules in a dowry formulation and belongs to the development of multiple-stopping extensions.
Sakaguchi also studied generalized secretary models with uncertain employment, showing that changing the selection mechanism itself can produce new optimal-stopping structures.
Tamaki’s double-choice problems
Tamaki subsequently analyzed explicit two-choice secretary problems.
In one formulation, the decision maker is allowed two choices and succeeds when one of them is the best or second-best candidate (Tamaki (1979a)). In another, the objective is to select both the maximum and the second maximum (Tamaki (1979b)).
These problems illustrate why multiple-choice secretary models require more state information than the classical one-choice problem.
Dynamic-programming structure
If \(j\) selections remain at time \(k\), the state must record both the information observed so far and the remaining number of choices.
Schematically,
\[ V_{k,j}(s) = \max\{ \text{value of selecting now}, \text{value of continuing} \}. \]
Selecting now changes the state from \(j\) remaining choices to \(j-1\).
Connection to the classical model
The classical secretary problem is recovered when
\[ m=1. \]
Thus multiple-choice models enlarge the stopping problem by adding a resource variable: the number of selections still available.
4. Unknown or random horizon
Problem
The classical model assumes that the total number \(n\) of observations is known.
Suppose instead that the number of observations is a random variable
\[ N. \]
The distribution of \(N\) may be known even though its realized value is not.
What changes?
With a fixed horizon, the decision maker knows exactly how many observations remain.
With a random horizon, the continuation value must also account for the probability that the sequence ends.
The resulting continuation values must account for both the information observed and the conditional distribution of the remaining horizon.
Connection to the \(1/e\) phenomenon
The classical \(1/e\) threshold is not a universal rule for random horizons. In the continuous-time unified-approach model of Bruss (1984), a \(1/e\) law holds under the model’s specific conditional-independence assumptions. A generic prior distribution for the unknown horizon \(N\) need not yield the same optimal rule or success probability (Bruss (1984)).
5. Last-success problems and the odds theorem
Problem
Let
\[ I_1,\ldots,I_n \]
be independent Bernoulli random variables with
\[ \Pr(I_k=1)=p_k,\qquad 0\le p_k<1. \]
The objective is to stop at an index \(\tau\) for which \(I_\tau=1\) and no later success occurs. If there is no success, the attempt fails. Assume decisions use only the observations up to the current index.
Define
\[ q_k=1-p_k>0, \qquad r_k=\frac{p_k}{q_k}. \]
Sum-the-odds rule (Bruss, 2000). Define
\[ s=\max\left(\{1\}\cup\left\{k\in\{1,\ldots,n\}:\sum_{j=k}^{n}r_j\ge1\right\}\right). \]
Reject observations before \(s\), then stop at the first success \(I_k=1\) with \(k\ge s\). If no success occurs after \(s\), the attempt fails. When the total sum of odds is less than \(1\), this convention gives \(s=1\). This rule maximizes the probability of stopping on the last success among all stopping times in this model. See Bruss (2000).
Connection to secretary problems
The odds theorem is not the classical secretary problem itself.
It belongs to the same broader optimal-stopping family: the decision maker must act without knowing whether a future event will supersede the current one.
Interactive experiment: sum the odds
Change the success probabilities of four independent Bernoulli trials. The page computes the exact last-success probability for each possible starting position and highlights the start prescribed by Bruss’s odds theorem. A decision maker rejects successes before that position and accepts the first later success.
Optimal start —
Exact winning probability —
This demonstration concerns the last-success objective, not selecting the best candidate in the classical secretary problem. Probabilities remain strictly below 1.
6. Applicant-side secretary problems
Problem
The classical problem is posed from the employer’s perspective:
When should the employer stop?
Glass (2012) studied the problem from the applicant’s perspective (Glass (2012)).
Suppose the employer follows a known stopping rule and an applicant may choose an interview position \(i\).
The applicant seeks to maximize
\[ \Pr(\text{selected}\mid\text{position }i). \]
What changes?
The applicant’s decision variable is an interview position \(i\), not the employer’s stopping time \(\tau\). The employer’s stopping rule is taken as given when the applicant chooses their position.
Known self-rank
If the applicant knows their own absolute rank, the best position can depend strongly on that rank.
This produces a strategic positioning problem built on top of a classical secretary stopping rule.
7. Uncertain self-rank
Suppose the applicant does not know their absolute rank.
Let
\[ J\in\{1,\ldots,n\} \]
be the applicant’s random absolute rank, distinct from the observed relative ranks \(R_k\), with a prior distribution. Assume the employer follows a specified stopping rule. For example, a truncated geometric prior is
\[ \Pr(J=j) = \frac{(1-q)q^{j-1}}{1-q^n}, \qquad 0<q<1. \]
The applicant’s value from position \(i\) becomes
\[ V(i) = \sum_{j=1}^{n} \Pr(J=j) \Pr(\text{selected}\mid J=j,\text{position }i). \]
This turns applicant positioning into a Bayesian decision problem under the specified employer stopping rule.
Comparing the main variants
| Variant | Information | Objective | Decision |
|---|---|---|---|
| Classical secretary | Relative ranks | Select rank \(1\) | One stopping time |
| Full information | Numerical values | Select maximum | One stopping time |
| Postdoc | Relative ranks | Select rank \(2\) | One stopping time |
| Multiple choice / dowry | Relative ranks | Capture target using several choices | Multiple stopping times |
| Random horizon | Relative ranks or events | Best choice with uncertain \(N\) | Stopping time |
| Odds theorem | Bernoulli successes | Stop on last success | Stopping time |
| Applicant perspective | Employer rule + self-rank | Be selected | Interview position |
| Uncertain self-rank | Prior over own rank | Be selected | Interview position |
A map of the secretary-problem family
The main extensions can be classified according to which component of the classical model is changed.
A useful way to generate new secretary problems is therefore to modify one or more components of the classical model:
Each modification can produce a genuinely different optimal-stopping problem.
Where to go next
The Secretary Problem Site presents these ideas from several complementary viewpoints.
- Backward Induction shows how finite stopping problems can be solved state by state.
- Simulations lets you experiment with threshold strategies.
- Research Timeline places the major developments in historical context.
- Resources provides Python examples and exercises for the existing interactive variants.