The Secretary Problem Site
  • Home
  • Classical Problem
  • Simulations
  • Backward Induction
  • Variants
  • Resources
  • Timeline
  • References
  • About
  • Español

On this page

  • Variants & Extensions of the Secretary Problem
  • The classical benchmark
  • 1. Full-information secretary problem
    • Problem
    • What changes?
    • Optimal-strategy structure
    • Interactive first-decision experiment (uniform observations)
    • Connection to the classical model
  • 2. The postdoc problem: selecting the second best
    • Problem
    • What changes?
    • Interactive postdoc decision (exact backward induction)
    • Connection to the classical model
  • 3. Multiple-choice and dowry problems
    • Problem
    • Sakaguchi’s contribution
    • Tamaki’s double-choice problems
    • Dynamic-programming structure
    • Connection to the classical model
  • 4. Unknown or random horizon
    • Problem
    • What changes?
    • Connection to the \(1/e\) phenomenon
  • 5. Last-success problems and the odds theorem
    • Problem
    • Connection to secretary problems
    • Interactive experiment: sum the odds
  • 6. Applicant-side secretary problems
    • Problem
    • What changes?
    • Known self-rank
  • 7. Uncertain self-rank
  • Comparing the main variants
  • A map of the secretary-problem family
  • Where to go next

Secretary Problem Variants & Extensions

Explore mathematical variants of the secretary problem: full information, selecting the second best, multiple choices, random horizons, and alternative rewards.

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.

Secretary Problem
Information
Relative ranks
Full values
Partial information
Uncertain self-rank
Objective
Best candidate
Second best
Top k
Last success
Choice structure
One choice
Multiple choices
Dowry problems
Strategic positioning
Horizon
Fixed
Random
Unknown

A useful way to generate new secretary problems is therefore to modify one or more components of the classical model:

Information + Objective + Choice structure + Horizon

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.

Leer en español

References

Bayón, L., P. Fortuny Ayuso, J. M. Grau, A. M. Oller-Marcén, and M. M. Ruiz. 2018. “The Best-or-Worst and the Postdoc Problems.” Journal of Combinatorial Optimization 35 (3). https://doi.org/10.1007/s10878-017-0203-4.
Bruss, F. Thomas. 1984. “A Unified Approach to a Class of Best Choice Problems with an Unknown Number of Options.” The Annals of Probability 12 (3). https://doi.org/10.1214/aop/1176993237.
———. 2000. “Sum the Odds to One and Stop.” The Annals of Probability 28 (3): 1384–91. https://doi.org/10.1214/aop/1019160340.
Gilbert, John P., and Frederick Mosteller. 1966. “Recognizing the Maximum of a Sequence.” Journal of the American Statistical Association 61 (313): 35–73. https://doi.org/10.1080/01621459.1966.10502008.
Glass, Darren. 2012. “The Secretary Problem from the Applicant’s Point of View.” The College Mathematics Journal 43 (1): 76–81. https://doi.org/10.4169/college.math.j.43.1.076.
Sakaguchi, Minoru. 1978. “Dowry Problems and OLA Policies.” Reports of Statistical Application Research, Japanese Union of Scientists and Engineers 25: 124–28.
Tamaki, Mitsushi. 1979a. “A Secretary Problem with Double Choices.” Journal of the Operations Research Society of Japan 22 (4): 257–65. https://doi.org/10.15807/jorsj.22.257.
———. 1979b. “Recognizing Both the Maximum and the Second Maximum of a Sequence.” Journal of Applied Probability 16 (4): 803–12. https://doi.org/10.2307/3213146.

© 2026 José Ángel Islas Anguiano

Secretary problems and optimal stopping

Facultad de Ciencias Naturales y Exactas (FACINE), Universidad Autónoma de Sinaloa (UAS)