pith. sign in

arxiv: 2604.08593 · v1 · submitted 2026-04-02 · 💻 cs.DS · cs.DM· cs.GT

Some variations of the secretary problem

Sarthak Agrawal , Sanjeev Saxena This is my paper

Pith reviewed 2026-05-13 21:06 UTC · model grok-4.3

classification 💻 cs.DS cs.DMcs.GT
keywords secretary problemoptimal stoppingthreshold rulereappearance probabilitytop-three selectionsuccess probabilityrandom permutation
0
0 comments X

The pith

Reappearances with probability p lower the optimal threshold in the returning secretary problem, while relaxing success to any top-three candidate raises overall performance and advances the stopping point.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies two extensions of the classic secretary problem. In the first, each candidate may reappear independently with fixed probability p; the authors derive the optimal threshold strategy that decides acceptance based on observed ranks and possible future returns. In the second, the goal is relaxed to selecting any of the top three candidates using the classical threshold rule, which increases the chance of success and moves the optimal threshold earlier in the sequence. These changes matter because many real selection tasks allow repeated looks at candidates or treat several strong options as interchangeable, so the derived rules give higher success rates than the strict single-best benchmark.

Core claim

We characterize the optimal threshold rule for the returning secretary problem with reappearance probability p and show that allowing selection among the top three significantly increases the success probability while shifting the optimal stopping threshold earlier than in the classical problem.

What carries the argument

The threshold rule that rejects an initial segment of candidates and then accepts the first one better than all seen so far, adjusted for the probability p of reappearances or for a relaxed top-three success criterion.

If this is right

  • Success probability rises monotonically with the reappearance probability p.
  • Applying the classical threshold to top-three selection produces a success rate strictly higher than the classical 1/e value.
  • The position of the optimal threshold decreases both with larger p and under the top-three criterion.
  • The models supply concrete decision rules for settings where multiple high-quality options are acceptable or repeated observations are possible.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same threshold logic may extend to online selection tasks with partial repeats, such as resume screening where candidates can reapply.
  • Generalizing the top-three relaxation to top-k for k greater than 3 would likely raise success further while requiring only modest changes to the threshold computation.
  • Empirical tests could replace the uniform random permutation with real arrival data from hiring platforms to check how robust the derived thresholds remain.

Load-bearing premise

Candidates appear in uniformly random order and any reappearances occur independently with a fixed probability p.

What would settle it

If arrival order deviates from uniform randomness or reappearances are correlated rather than independent, the computed thresholds no longer maximize success probability.

Figures

Figures reproduced from arXiv: 2604.08593 by Sanjeev Saxena, Sarthak Agrawal.

Figure 1
Figure 1. Figure 1: Success probability graph w.r.t. k at n = 100 4 Secretary problem with top-3 success In this case, each interview arrives exactly once. But, we will be satisfied if the chosen candidate is amongst the best (top) three. 15 [PITH_FULL_IMAGE:figures/full_fig_p015_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Success probability graph w.r.t k at n = 100 [PITH_FULL_IMAGE:figures/full_fig_p021_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Simulation Success top-3 graph w.r.t k at n = 100, trials = 10000 we derived a recursive formula and an O(n) time dynamic programming algorithm to calculate the probability of success at a general threshold k. We further studied the asymptotic behavior of the model and the optimal threshold and corresponding optimal probability of success. 21 [PITH_FULL_IMAGE:figures/full_fig_p021_3.png] view at source ↗
read the original abstract

We consider two variations of the classical secretary problem. * A variation of the returning secretary problem where each interviewee may appear a second time with a fixed probability p. The decision-maker observes interviewees sequentially and must choose whether to accept or reject each appearance. We characterize the optimal threshold rule and examine its dependence on the reappearance probability p, highlighting how additional information from repeated appearances improves selection performance. * A variation of the secretary problem in which success is defined as selecting any one of the top three interviewees rather than the single best. Interviewees are observed sequentially in random order, and decisions are irreversible. We estimated the success probability under this relaxed success criterion using the threshold strategy of the classical secretary problem. The results show that allowing selection among the top three significantly increases the success probability and shifts the optimal stopping threshold earlier than in the classical problem. This model provides insight into realistic decision-making scenarios where top interviewees are more or less similar.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper studies two variants of the classical secretary problem. In the first, each interviewee reappears independently with fixed probability p; the authors characterize the optimal threshold rule for this returning-secretary setting and study its dependence on p. In the second, success is redefined as selecting any of the top three candidates; the authors apply the classical secretary threshold and report that the resulting success probability rises substantially while the optimal stopping threshold moves earlier than in the single-best case.

Significance. If the threshold characterizations and probability estimates are rigorously derived, the work supplies concrete extensions of the secretary problem that are relevant to hiring models with callbacks and to decision settings in which near-optimal candidates are acceptable. The first variant’s explicit dependence on p could be directly usable in applications; the second illustrates how relaxing the objective affects strategy. The manuscript does not supply machine-checked proofs or reproducible code, so its main contribution would rest on the analytic derivations and numerical estimates once they are fully presented.

major comments (1)
  1. [Abstract] Abstract (second variation): the reported earlier optimal threshold and associated success-probability increase are obtained by substituting the classical 1/k threshold (derived for payoff 1 only on rank 1) into the top-3 objective. Because the payoff function has changed, the threshold that maximizes the probability of selecting any of ranks 1–3 must be obtained by solving the corresponding dynamic program or recurrence; the classical threshold is not guaranteed to be optimal for the relaxed criterion, so the claimed shift cannot yet be attributed to optimality under the new objective.
minor comments (2)
  1. The manuscript should include the explicit recurrence or dynamic-programming equations that define the optimal thresholds for both variants, together with any numerical tables or plots that support the dependence on p and the top-3 success probabilities.
  2. Notation for the reappearance probability p and for the top-3 success indicator should be introduced once and used consistently; currently the abstract refers to these quantities without defining them formally.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and constructive feedback on our manuscript. We address the major comment below and will revise the manuscript to correct imprecise wording in the abstract.

read point-by-point responses

  1. Referee: [Abstract] Abstract (second variation): the reported earlier optimal threshold and associated success-probability increase are obtained by substituting the classical 1/k threshold (derived for payoff 1 only on rank 1) into the top-3 objective. Because the payoff function has changed, the threshold that maximizes the probability of selecting any of ranks 1–3 must be obtained by solving the corresponding dynamic program or recurrence; the classical threshold is not guaranteed to be optimal for the relaxed criterion, so the claimed shift cannot yet be attributed to optimality under the new objective.

    Authors: We agree with the referee. In the second variation we evaluate the classical 1/k threshold strategy under the relaxed top-3 success criterion; we do not derive the threshold that is optimal for the new payoff. The abstract's reference to an 'optimal stopping threshold' for this setting is therefore imprecise. We will revise the abstract (and any corresponding text) to state explicitly that the classical threshold is applied, that this produces a higher success probability and an earlier stopping time than in the single-best case, and that computing the truly optimal threshold for the top-3 objective would require a separate dynamic program, which lies outside the scope of the present work. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper derives its optimal threshold characterizations for the returning secretary problem directly from the standard uniform random permutation model augmented by the independent reappearance probability p, using the usual dynamic programming recurrence for optimal stopping. For the top-3 variant, success probabilities are computed by direct substitution of the known classical threshold into the relaxed payoff function. No equations reduce by construction to previously fitted quantities, no load-bearing self-citations are invoked, and no ansatz or uniqueness claim is smuggled in; all steps remain self-contained against the stated model assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard random-order assumption plus the new independent reappearance probability; no free parameters are explicitly fitted in the abstract, and no new entities are postulated.

axioms (2)
  • domain assumption Interviewees appear in uniformly random order (random permutation)
    Invoked for both variations to guarantee the existence of threshold rules.
  • domain assumption Each interviewee reappears independently with fixed probability p
    Core modeling choice for the first variation; determines how information accumulates.

pith-pipeline@v0.9.0 · 5456 in / 1357 out tokens · 54353 ms · 2026-05-13T21:06:44.808228+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    Knowing when to stop.American Scientist, 97(2):126, 2009

    Theodore Hill. Knowing when to stop.American Scientist, 97(2):126, 2009

    work page 2009

  2. [2]

    Secretary problem

    Wikipedia. Secretary problem. http://en.wikipedia.org/w/index.php?title=Secretary%20problem& oldid=987132965, 2021

    work page 2021

  3. [3]

    The Returning Secretary

    Shai Vardi. The Returning Secretary. In Ernst W. Mayr and Nicolas Ollinger, editors,32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), volume 30 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 716–729, 2015

    work page 2015

  4. [4]

    Thomas Bruss

    F. Thomas Bruss. Sum the odds to one and stop.Ann. Probab., 28(3):1384–1391, 06 2000

    work page 2000

  5. [5]

    E. B. DYNKIN. The optimum choice of the instant for stopping a markov process.Soviet Mathematics, 4:627–629, 1963

    work page 1963

  6. [6]

    Online auctions and generalized secretary problems.ACM SIGecom Exchanges, 7(2):1–11, June 2008

    Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. Online auctions and generalized secretary problems.ACM SIGecom Exchanges, 7(2):1–11, June 2008

    work page 2008

  7. [7]

    A knapsack secretary problem with applications

    Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. A knapsack secretary problem with applications. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 16–28. Springer Berlin Heidelberg, 2007

    work page 2007

  8. [8]

    Matroids, secretary problems, and online mechanisms

    Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. InSymposium on Discrete Algorithms (SODA’07), pages 434–443, January 2007

    work page 2007

  9. [9]

    How to choose the best twins.SIAM Journal on Discrete Mathematics, 26(1):384–398, January 2012

    Bryn Garrod, Grzegorz Kubicki, and Michał Morayne. How to choose the best twins.SIAM Journal on Discrete Mathematics, 26(1):384–398, January 2012

    work page 2012

  10. [10]

    The secretary returns.CoRR, abs/1404.0614, 2014

    Shai Vardi. The secretary returns.CoRR, abs/1404.0614, 2014

    work page arXiv 2014

  11. [11]

    J. M. Grau Ribas. A new look at the returning secretary problem.Journal of Combinatorial Optimization, 37(4):1216–1236, September 2018

    work page 2018

  12. [12]

    Bayón, P

    L. Bayón, P. Fortuny Ayuso, J. M. Grau, A. M. Oller-Marcén, and M. M. Ruiz. The best-or-worst and the postdoc problems.Journal of Combinatorial Optimization, 35(3):703–723, November 2017. 22

    work page 2017