pith. sign in

arxiv: 2605.22653 · v1 · pith:TFINWWPMnew · submitted 2026-05-21 · 💻 cs.DS · cs.LG

The Secretary Problem with a Stochastic Precursor

Franziska Eberle , Alexander Lindermayr This is my paper

Pith reviewed 2026-05-22 04:18 UTC · model grok-4.3

classification 💻 cs.DS cs.LG
keywords secretary problemstochastic precursoronline algorithmsrandom order modeladversarial orderoptimal stoppinglearning-augmented algorithmstemporal information
0
0 comments X

The pith

A content-free signal timed to arrive before the best candidate raises secretary problem success to at least one half.

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

The paper studies the secretary problem when a stochastic precursor is added: a signal that is guaranteed to arrive no later than the best item but carries no information about values or ranks. In the random-order model this timing information alone lifts the probability of selecting the best item from the classic 1/e to at least 1/2 for a uniform precursor, with the probability rising toward 1 as the precursor arrives later on average. The same signal also restores constant success guarantees in adversarial order when its distribution is sufficiently concentrated. The work therefore treats arrival time as an independent and powerful form of advice in online stopping problems.

Core claim

A stochastic precursor that arrives no later than the best item changes the structure of optimal stopping. In random order a uniform precursor already yields success probability at least 1/2 and later precursors drive the probability to 1; in adversarial order sufficiently concentrated precursors recover constant-factor guarantees. These results follow from characterizing the optimal policies that use the precursor's observed arrival as a reference point for deciding whether to stop on later candidates.

What carries the argument

The stochastic precursor: a content-free signal whose arrival time is random but guaranteed to precede or coincide with the best item, used as a timing reference that restructures the stopping threshold.

If this is right

  • Random-order success exceeds the classic 1/e benchmark even with minimal timing information.
  • Success probability increases monotonically toward 1 as the precursor distribution shifts later.
  • Adversarial-order instances regain constant success ratios once the precursor is concentrated enough.
  • Optimal policies can be computed by conditioning thresholds on whether the precursor has been observed.

Where Pith is reading between the lines

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

  • Similar timing signals could be added to other online selection or allocation problems to obtain improved guarantees without value predictions.
  • The separation between content and timing suggests that learning-augmented algorithms might benefit from studying arrival-time distributions separately from prediction accuracy.
  • Empirical tests on real arrival-time data from hiring or bidding platforms would check whether the modeled distributions match observed precursor behavior.

Load-bearing premise

The precursor is guaranteed to arrive no later than the best item.

What would settle it

A sequence in which the precursor arrives after the best item, or a distribution that places positive probability after the best item, would fall outside the model and could reduce success below the stated bounds.

Figures

Figures reproduced from arXiv: 2605.22653 by Alexander Lindermayr, Franziska Eberle.

Figure 1
Figure 1. Figure 1: Left: PDFs of Beta(α, 1). Right: Plot of OPT(α) from Theorem 2. Random order: exact optimal policy (Section 2). We fully characterize the optimal online policy (cf. Theorem 2). If α ≥ 1, then the optimal rule is A(S) (which does not need to know n): wait for the signal and then accept the first record. Notably, already a uniform signal boosts the probability of the next record being the overall maximum abo… view at source ↗
Figure 2
Figure 2. Figure 2: Left: Heatmap of the asymptotic guarantee [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Empirical experiments for asynchronous predictions. Left: clean-model empirical [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Random-order experiments for several problem sizes. Each curve shows the empirical [PITH_FULL_IMAGE:figures/full_fig_p030_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Misspecification slices in the random-order model. The top panel shows empirical [PITH_FULL_IMAGE:figures/full_fig_p031_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Noisy-signal breakdown in the random-order model. The three panels isolate missed [PITH_FULL_IMAGE:figures/full_fig_p031_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Adversarial position profile on the hard family [PITH_FULL_IMAGE:figures/full_fig_p032_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Adversarial scaling regime α = cn. Empirical worst-case success probabilities match the exact finite-n deterministic and randomized values and approach the limit 1 − e −c . 10 1 10 2 problem size n 1.6 1.8 2.0 2.2 2.4 2.6 2.8 3.0 e m piric al s u c c e s s pro b a bility s c ale d b y n Adversarial full-history separation for m = 2 last signal, deterministic full two-signal history, deterministic last sign… view at source ↗
Figure 9
Figure 9. Figure 9: Full-history separation for m = 2 in the adversarial-order model. The full-history deterministic value from Theorem 14 lies between the bounds in Corollary 15 and is strictly larger than the deterministic last-signal value from Theorem 6. 33 [PITH_FULL_IMAGE:figures/full_fig_p033_9.png] view at source ↗
read the original abstract

In learning-augmented online algorithms, predictions are usually valued for what they say: a value estimate, a solution, or an algorithmic recommendation. This paper shows that predictions can also be valuable solely due to their arrival time. We study the fundamental secretary problem augmented with a stochastic precursor: a content-free signal that is guaranteed to arrive no later than the best item, but is otherwise stochastically timed. The signal does not carry any additional information; nevertheless, its timing alone changes the structure of optimal stopping. We characterize optimal policies in the random-order and adversarial-order models. In random order, a single uniformly timed precursor already gives success probability at least $\frac12$, improving on the classic $\frac1e$ benchmark. With increasingly late precursors, the success probability approaches $1$. In adversarial order, for which traditional models do not admit strong guarantees, sufficiently concentrated precursors recover constant success guarantees. Our results show that such novel forms of asynchronous temporal information are a distinct and powerful form of advice in online decision making and may also be effective for other problems.

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

2 major / 3 minor

Summary. The paper augments the classic secretary problem with a stochastic precursor: a content-free signal guaranteed to arrive no later than the best item but otherwise stochastically timed. It characterizes optimal stopping policies for both the random-order and adversarial-order models. In random order, a single uniformly timed precursor yields success probability at least 1/2 (improving on the classic 1/e), with later precursors approaching probability 1; in adversarial order, sufficiently concentrated precursors recover constant success guarantees.

Significance. If the characterizations and probability bounds hold, the work establishes that arrival timing alone constitutes a distinct and powerful form of advice in online algorithms, independent of any value or rank information carried by the signal. This provides a clean separation between temporal and informational aspects of predictions and extends constant-factor guarantees to the adversarial secretary setting, where traditional models admit none. The results are parameter-free in their core claims and offer falsifiable predictions for other online stopping problems.

major comments (2)
  1. [§3.2, Theorem 2] §3.2, Theorem 2: The lower bound of 1/2 for the uniform precursor in random order is derived by comparing the precursor arrival to the classic 1/e threshold; however, the argument appears to condition on the precursor occurring before the optimal stopping time without explicitly handling the measure-zero cases where the precursor coincides with the last item, which could affect the exact constant.
  2. [§5.1, Eq. (8)] §5.1, Eq. (8): The adversarial-order analysis claims constant success probability for concentrated precursors via a reduction to a two-phase stopping rule, but the concentration parameter is left as a free variable; the paper should state the explicit dependence of the constant on the concentration width to make the guarantee fully quantitative.
minor comments (3)
  1. [§2] The notation for the precursor arrival distribution (e.g., uniform vs. beta) is introduced in §2 but reused without redefinition in later sections; a single consolidated definition table would improve readability.
  2. [Figure 2] Figure 2 (random-order success curves) lacks error bars or sample-size information for the Monte-Carlo validation points; adding these would strengthen the empirical support for the analytic curves.
  3. [§1.2] The related-work discussion cites the classic secretary literature but omits recent learning-augmented secretary results (e.g., on value predictions); a brief comparison paragraph would clarify the novelty of the timing-only model.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and constructive comments on our work. We address each major comment below.

read point-by-point responses

  1. Referee: [§3.2, Theorem 2] §3.2, Theorem 2: The lower bound of 1/2 for the uniform precursor in random order is derived by comparing the precursor arrival to the classic 1/e threshold; however, the argument appears to condition on the precursor occurring before the optimal stopping time without explicitly handling the measure-zero cases where the precursor coincides with the last item, which could affect the exact constant.

    Authors: The lower bound in Theorem 2 is obtained by comparing the uniform precursor arrival time against the classic 1/e threshold. Because arrival times are drawn from a continuous distribution, the probability that the precursor arrives at exactly the same instant as the final item is zero. This null event therefore contributes nothing to the success probability and leaves the constant 1/2 unchanged. The conditioning step is valid almost surely. We do not plan to alter the proof but can insert a one-sentence clarification on the measure-zero event if the referee considers it helpful. revision: no

  2. Referee: [§5.1, Eq. (8)] §5.1, Eq. (8): The adversarial-order analysis claims constant success probability for concentrated precursors via a reduction to a two-phase stopping rule, but the concentration parameter is left as a free variable; the paper should state the explicit dependence of the constant on the concentration width to make the guarantee fully quantitative.

    Authors: We agree that an explicit functional dependence would make the guarantee fully quantitative. In the revised manuscript we will replace the current statement of Equation (8) with an explicit expression that shows how the success probability depends on the concentration width parameter, and we will add a short paragraph deriving the dependence from the two-phase analysis. revision: yes

Circularity Check

0 steps flagged

No circularity: results follow from direct model analysis

full rationale

The paper defines a stochastic precursor model (guaranteed arrival no later than the best item, otherwise random timing, content-free) and derives optimal stopping policies plus success probabilities (≥1/2 in random order, approaching 1 for late precursors, constant in adversarial order for concentrated precursors) via explicit characterization of the random-order and adversarial-order settings. No equations reduce a claimed prediction to a fitted input by construction, no self-citations are invoked as load-bearing uniqueness theorems, and no ansatz or renaming is presented as a derivation. The central claims are obtained by analyzing the augmented stopping problem from first principles on the stated distributions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the definition of the stochastic precursor and the standard random-order and adversarial-order models of the secretary problem; no free parameters or additional invented entities beyond the precursor itself are visible in the abstract.

axioms (1)
  • domain assumption The precursor arrives no later than the best item but is otherwise stochastically timed and carries no value information.
    This guarantee is the load-bearing property that allows timing to convey information about remaining sequence length.
invented entities (1)
  • stochastic precursor no independent evidence
    purpose: To supply timing information usable for optimal stopping without carrying value or rank data.
    The precursor is introduced in the paper as a new form of asynchronous temporal advice.

pith-pipeline@v0.9.0 · 5710 in / 1350 out tokens · 49930 ms · 2026-05-22T04:18:32.924406+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

56 extracted references · 56 canonical work pages

  1. [1]

    Abramo, C

    G. Abramo, C. A. D’Angelo, and G. Felici. Predicting publication long-term impact through a combination of early citations and journal impact factor. In:J. Informetr.13.1 (2019), pp. 32–49

    work page 2019

  2. [2]

    J. Adams. Early citation counts correlate with accumulated impact. In:Scientometrics 63 (2005), pp. 567–581

    work page 2005

  3. [3]

    Agarwal and E

    A. Agarwal and E. Balkanski. Learning-Augmented Dynamic Submodular Maximization. In:NeurIPS. 2024

    work page 2024

  4. [4]

    Angelopoulos, M

    S. Angelopoulos, M. Bienkowski, C. Dürr, and B. Simon. Contract Scheduling with Distributional and Multiple Advice. In:IJCAI. ijcai.org, 2024, pp. 3652–3660

    work page 2024

  5. [5]

    Antoniadis, C

    A. Antoniadis, C. Coester, M. Eliás, A. Polak, and B. Simon. Online Metric Algorithms with Untrusted Predictions. In:ACM Trans. Algorithms19.2 (2023), 19:1–19:34

    work page 2023

  6. [6]

    Antoniadis, T

    A. Antoniadis, T. Gouleakis, P. Kleer, and P. Kolev. Secretary and online matching problems with machine learned advice. In:Discret. Optim.48.Part 2 (2023), p. 100778

    work page 2023

  7. [7]

    P. D. Azar, R. Kleinberg, and S. M. Weinberg. Prior independent mechanisms via prophet inequalities with limited information. In:Games Econ. Behav.118 (2019), pp. 511–532

    work page 2019

  8. [8]

    Y. Azar, S. Leonardi, and N. Touitou. Flow time scheduling with uncertain processing time. In:STOC. ACM, 2021, pp. 1070–1080

    work page 2021

  9. [9]

    Balkanski, W

    E. Balkanski, W. Ma, and A. Maggiori. Fair Secretaries with Unfair Predictions. In: NeurIPS. 2024

    work page 2024

  10. [10]

    Bansal, C

    N. Bansal, C. Coester, R. Kumar, M. Purohit, and E. Vee. Learning-Augmented Weighted Paging. In:SODA. SIAM, 2022, pp. 67–89

    work page 2022

  11. [11]

    Benomar, R

    Z. Benomar, R. Cosson, A. Lindermayr, and J. Schlöter. Non-Clairvoyant Scheduling with Progress Bars. In:NeurIPS. 2025

    work page 2025

  12. [12]

    Beyhaghi and L

    H. Beyhaghi and L. Cai. Recent Developments in Pandora’s Box Problem: Variants and Applications. In:SIGecom Exch.21.1 (2023), pp. 20–34

    work page 2023

  13. [13]

    Braun and S

    A. Braun and S. Sarkar. The Secretary Problem with Predicted Additive Gap. In:NeurIPS. 2024

    work page 2024

  14. [14]

    D. Choo, T. Gouleakis, C. K. Ling, and A. Bhattacharyya. Online bipartite matching with imperfect advice. In:ICML. 2024

    work page 2024

  15. [15]

    Correa, A

    J. Correa, A. Cristi, B. Epstein, and J. A. Soto. The Two-Sided Game of Googol. In:J. Mach. Learn. Res.23 (2022), 113:1–113:37

    work page 2022

  16. [16]

    Correa, A

    J. Correa, A. Cristi, L. Feuilloley, T. Oosterwijk, and A. Tsigonias-Dimitriadis. The Secretary Problem with Independent Sampling. In:Manag. Sci.71.4 (2025), pp. 2778–2801. 11

    work page 2025

  17. [17]

    Correa, P

    J. Correa, P. Dütting, F. A. Fischer, and K. Schewior. Prophet Inequalities for Independent and Identically Distributed Random Variables from an Unknown Distribution. In:Math. Oper. Res.47.2 (2022), pp. 1287–1309

    work page 2022

  18. [18]

    Correa, P

    J. Correa, P. Foncea, R. Hoeksma, T. Oosterwijk, and T. Vredeveld. Recent developments in prophet inequalities. In:SIGecom Exch.17.1 (2018), pp. 61–70

    work page 2018

  19. [19]

    Cui and M

    Q. Cui and M. Dinitz. Ski Rental with Distributional Predictions of Unknown Quality. In:CoRRabs/2602.21104 (2026)

    work page arXiv 2026

  20. [20]

    Diakonikolas, V

    I. Diakonikolas, V. Kontonis, C. Tzamos, A. Vakilian, and N. Zarifis. Learning Online Algorithms with Distributional Advice. In:ICML. Vol. 139. PMLR, 2021, pp. 2687–2696

    work page 2021

  21. [21]

    Dinitz, S

    M. Dinitz, S. Im, T. Lavastida, B. Moseley, A. Niaparast, and S. Vassilvitskii. Binary Search with Distributional Predictions. In:NeurIPS. 2024

    work page 2024

  22. [22]

    Dütting, S

    P. Dütting, S. Lattanzi, R. P. Leme, and S. Vassilvitskii. Secretaries with Advice. In: Math. Oper. Res.49.2 (2024), pp. 856–879

    work page 2024

  23. [23]

    E. B. Dynkin. The optimum choice of the instant for stopping a Markov process. In: Soviet Mathematics4 (1963), pp. 627–629

    work page 1963

  24. [24]

    Dziallas and K

    M. Dziallas and K. Blind. Innovation indicators throughout the innovation process: An extensive literature analysis. In:Technovation80-81 (2019), pp. 3–29

    work page 2019

  25. [25]

    Eliás, H

    M. Eliás, H. Kaplan, Y. Mansour, and S. Moran. Learning-Augmented Algorithms with Explicit Predictors. In:NeurIPS. 2024

    work page 2024

  26. [26]

    Esfandiari, M

    H. Esfandiari, M. Hajiaghayi, B. Lucier, and M. Mitzenmacher. Prophets, Secretaries, and Maximizing the Probability of Choosing the Best. In:AISTATS. PMLR, 2020, pp. 3717– 3727

    work page 2020

  27. [27]

    T. S. Ferguson. Who Solved the Secretary Problem. In:Stat. Sci.4 (1989), pp. 282–289

    work page 1989

  28. [28]

    Fujii and Y

    K. Fujii and Y. Yoshida. The Secretary Problem with Predictions. In:Math. Oper. Res. 49.2 (2024), pp. 1241–1262

    work page 2024

  29. [29]

    J. P. Gilbert and F. Mosteller. Recognizing the Maximum of a Sequence. In:J. Amer. Statistical Assoc.61 (1966), pp. 35–73

    work page 1966

  30. [30]

    Gupta, H

    A. Gupta, H. Kaplan, A. Lindermayr, J. Schlöter, and S. Yingchareonthawornchai. A Little Clairvoyance Is All You Need. In:FOCS. IEEE, 2025, pp. 86–118

    work page 2025

  31. [31]

    T. P. Hill and R. P. Kertz. A Survey of Prophet Inequalities in Optimal Stopping Theory. In:Contemporary mathematics125 (1992), pp. 191–207

    work page 1992

  32. [32]

    Y. Hu, C. Hu, S. Fu, M. Fang, and W. Xu. Predicting Key Events in the Popularity Evolution of Online Information. In:PLoS ONE12 (2017)

    work page 2017

  33. [33]

    Jin and W

    B. Jin and W. Ma. Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model. In:NeurIPS. 2022

    work page 2022

  34. [34]

    Joulani, A

    P. Joulani, A. Gyorgy, and C. Szepesvari. Online Learning under Delayed Feedback. In: ICML. PMLR, 2013, pp. 1453–1461

    work page 2013

  35. [35]

    Kaplan, D

    H. Kaplan, D. Naori, and D. Raz. Competitive Analysis with a Sample and the Secretary Problem. In:SIAM J. Comput.54.6 (2025), pp. 1489–1513

    work page 2025

  36. [36]

    Karisani, M

    H. Karisani, M. Daneshvaramoli, H. Beyhaghi, M. Hajiesmaili, and C. Musco. The Secretary Problem with Predictions and a Chosen Order. In:ITCS. Schloss Dagstuhl– Leibniz-Zentrum für Informatik, 2026, pp. 86–1

    work page 2026

  37. [37]

    Khodak, M

    M. Khodak, M. Balcan, A. Talwalkar, and S. Vassilvitskii. Learning Predictions for Algorithms with Predictions. In:NeurIPS. 2022

    work page 2022

  38. [38]

    Lattanzi, T

    S. Lattanzi, T. Lavastida, B. Moseley, and S. Vassilvitskii. Online Scheduling via Learned Weights. In:SODA. SIAM, 2020, pp. 1859–1877

    work page 2020

  39. [39]

    Lindermayr and N

    A. Lindermayr and N. Megow. Permutation Predictions for Non-Clairvoyant Scheduling. In:ACM Trans. Parallel Comput.12.2 (2025), 4:1–4:26

    work page 2025

  40. [40]

    Lindermayr and N

    A. Lindermayr and N. Megow.Repository of papers on algorithms with predictions.http: //algorithms-with-predictions.github.io/. 2026. 12

    work page 2026

  41. [41]

    D. V. Lindley. Dynamic Programming and Decision Theory. In:J. Roy. Stat. Soc. C-app. 10 (1961), pp. 39–51

    work page 1961

  42. [42]

    B. Lucier. An economic view of prophet inequalities. In:SIGecom Exch.16.1 (2017), pp. 24–47

    work page 2017

  43. [43]

    Lykouris and S

    T. Lykouris and S. Vassilvitskii. Competitive Caching with Machine Learned Advice. In: J. ACM68.4 (2021), 24:1–24:25

    work page 2021

  44. [44]

    Mitzenmacher and S

    M. Mitzenmacher and S. Vassilvitskii. Algorithms with predictions. In:Commun. ACM 65.7 (2022), pp. 33–35

    work page 2022

  45. [45]

    Moseley, H

    B. Moseley, H. Newman, K. Pruhs, and R. Zhou. Robust Gittins for Stochastic Scheduling. In:SIGMETRICS (Abstracts). ACM, 2025, pp. 166–168

    work page 2025

  46. [46]

    Nourmohammadi, Y

    H. Nourmohammadi, Y. Cao, B. Sun, and X. Tan. Ordinal Secretaries with Advice. In: AAAI. Vol. 40. 43. 2026, pp. 37108–37116

    work page 2026

  47. [47]

    P. Nuti. The Secretary Problem with Distributions. In:IPCO. Springer, 2022, pp. 429–439

    work page 2022

  48. [48]

    Y. Qian, Z. Zhang, P. Zhao, and Z.-H. Zhou. Learning with Asynchronous Labels. In: ACM Trans. Knowl. Discovery Data18 (2024), pp. 1–27

    work page 2024

  49. [49]

    Raman and A

    V. Raman and A. Tewari. Online Classification with Predictions. In:NeurIPS. 2024

    work page 2024

  50. [50]

    OptimalSingle-ChoiceProphetInequalities from Samples

    A.Rubinstein,J.Z.Wang,andS.M.Weinberg. OptimalSingle-ChoiceProphetInequalities from Samples. In:ITCS. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, 60:1– 60:10

    work page 2020

  51. [51]

    Spaeh and A

    F. Spaeh and A. Ene. Online Ad Allocation with Predictions. In:NeurIPS. 2023

    work page 2023

  52. [52]

    Szabo and B

    G. Szabo and B. A. Huberman. Predicting the popularity of online content. In:Commun. ACM53.8 (2010), pp. 80–88

    work page 2010

  53. [53]

    Tatar, M

    A.-F. Tatar, M. D. de Amorim, S. Fdida, and P. Antoniadis. A survey on predicting the popularity of web content. In:Journal of Internet Services and Applications5 (2014)

    work page 2014

  54. [54]

    A. Wei. Better and Simpler Learning-Augmented Online Caching. In:APPROX-RANDOM. Vol. 176. LIPIcs. 2020, 60:1–60:17

    work page 2020

  55. [55]

    Weitzman

    M. Weitzman. Optimal search for the best alternative. In:Econometrica47 (1978), pp. 641–654

    work page 1978

  56. [56]

    Yang and D

    J. Yang and D. Zhan. Generalized Delayed Feedback Model with Post-Click Information in Recommender Systems. In:NeurIPS. 2022. A Omitted proofs from Section 2 This section is dedicated to giving the formal proofs omitted from Section 2. We start by proving the Bellman recursion. Lemma 1(Bellman recursion).Fix α > 0. There is an optimal policy that never st...

    work page 2022