pith. sign in

arxiv: 1907.05350 · v1 · pith:YBXZNKTEnew · submitted 2019-07-11 · 💻 cs.DS

Competitive Analysis with a Sample and the Secretary Problem

Haim Kaplan , David Naori , Danny Raz This is my paper

Pith reviewed 2026-05-24 22:46 UTC · model grok-4.3

classification 💻 cs.DS
keywords online algorithmssecretary problemcompetitive analysisrandom sampleworst-case modelrandom-order modelcompetitive ratio
0
0 comments X

The pith

A random sample of the adversarial input lets a simple algorithm achieve the optimal competitive ratio for the secretary problem in the worst-case model, for any sample size.

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

The paper extends standard online models by giving the algorithm a random sample drawn from the full adversarial input before the rest arrives online. Performance is measured by comparing the algorithm's value on the unseen part against the expected optimum there. In this worst-case sample model the authors give a simple algorithm whose competitive ratio is optimal no matter how large or small the sample is. In the random-order version of the model they give a simple algorithm whose ratio is nearly tight for small samples. They also prove that once the sample is large enough, no algorithm can be optimal in both models at the same time.

Core claim

In the worst-case model with a random sample, a simple online algorithm attains the optimal competitive ratio for every sample size. In the random-order model with a sample, a similar simple algorithm attains an almost tight competitive ratio for small samples. For all sufficiently large sample sizes, however, no algorithm can be simultaneously optimal in both the worst-case and random-order versions of the model.

What carries the argument

The central mechanism is the random sample drawn from the adversarial input and revealed to the online player in advance, so that the algorithm can base its decisions on both the sample and the remaining online stream while competing against the expected optimum on the unseen portion.

If this is right

  • The worst-case competitive ratio for the secretary problem becomes a simple function of sample size that a threshold rule can achieve.
  • Small samples already suffice to reach nearly the best possible ratio when arrivals are random.
  • Large samples force a designer to choose between the two models rather than optimize for both.
  • The sample model sits strictly between fully adversarial and fully stochastic online settings.

Where Pith is reading between the lines

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

  • In applied settings even modest historical data may let online rules approach the performance previously thought possible only under strong distributional assumptions.
  • The incompatibility result suggests that algorithm choice should depend on whether the environment is closer to worst-case or random-order once sample size exceeds a threshold.
  • The same sampling technique could be applied to other classic online problems such as online matching to obtain similar trade-off statements.

Load-bearing premise

The model assumes that a random sample of the adversarial input is shown to the player ahead of time and that the player is judged against the expected optimal value on the unseen online part.

What would settle it

An explicit construction, for some large sample size, of an algorithm that meets the optimal worst-case ratio but falls short of the optimal random-order ratio, or vice versa.

Figures

Figures reproduced from arXiv: 1907.05350 by Danny Raz, David Naori, Haim Kaplan.

Figure 1
Figure 1. Figure 1: Overview of our results. 0 1/e 1/2 1 − 1/e 0.745 0.2 0.4 0.567 0.8 1 1.5 1/2 1 − 1/e 0.745 competitive-ratio h/n Theorem 2.6 Theorem 2.4 Theorem 3.7 Corollary 3.10 Theorem 3.8 Theorem 3.6 Theorem 2.3 Theorem 2.2 RO upper bound Algorithm 3 WC upper bound Algorithm 1, 2 (Corollary 3.10). After we study the secretary problem in each model separately, we explore how well can a single algorithm perform in both … view at source ↗
Figure 2
Figure 2. Figure 2: Improvement for the h-IID-PI 0 0.2 1/e 0.5 1 − 1/e 0.8 0 0.2 0.4 0.6 0.8 1 1.5 1 − 1/e competitive-ratio h/n Upper bound Algorithm 3 Correa et al. [5] ‘ A direct implication of Theorem 3.9 is that the upper bound of 1/β ≈ 0.745 by Hill and Kertz [9, 10] on the prophet inequality for i.i.d. random variables from a known distribution applies to the h-RO-SP for any h. 5 Corollary 3.10. Any online algorithm fo… view at source ↗
read the original abstract

We extend the standard online worst-case model to accommodate past experience which is available to the online player in many practical scenarios. We do this by revealing a random sample of the adversarial input to the online player ahead of time. The online player competes with the expected optimal value on the part of the input that arrives online. Our model bridges between existing online stochastic models (e.g., items are drawn i.i.d. from a distribution) and the online worst-case model. We also extend in a similar manner (by revealing a sample) the online random-order model. We study the classical secretary problem in our new models. In the worst-case model we present a simple online algorithm with optimal competitive-ratio for any sample size. In the random-order model, we also give a simple online algorithm with an almost tight competitive-ratio for small sample sizes. Interestingly, we prove that for a large enough sample, no algorithm can be simultaneously optimal both in the worst-cast and random-order models.

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

0 major / 3 minor

Summary. The paper extends the standard online worst-case and random-order models by revealing a random sample of the adversarial input to the algorithm in advance. For the secretary problem, it claims a simple online algorithm achieving the optimal competitive ratio in the worst-case model for any sample size; a simple algorithm with an almost tight competitive ratio in the random-order model for small sample sizes; and an impossibility result showing that sufficiently large samples preclude any algorithm from being simultaneously optimal in both models. The online player competes against the expected optimal value on the remaining (online) portion of the input.

Significance. If the claims hold, the work provides a clean bridge between worst-case competitive analysis and stochastic models via explicit samples, with concrete simple algorithms for the secretary problem and a separation result on simultaneous optimality. The emphasis on simple algorithms and the model definition (competing with expected OPT on the online suffix) are strengths that could inform follow-up work on sample-augmented online selection.

minor comments (3)
  1. [Abstract] Abstract: 'worst-cast' is a typographical error and should read 'worst-case'.
  2. The manuscript would benefit from an explicit statement (perhaps in the model section) of how the competitive ratio is formally defined when the benchmark is the expected OPT on the online suffix only; this would aid reproducibility of the ratio calculations.
  3. Minor notation: ensure consistent use of 'sample size' versus 'sample' throughout; a short table summarizing the achieved ratios as a function of sample size would improve clarity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. The report accurately reflects the paper's contributions on the sampled-input model for the secretary problem. No major comments are listed in the report, so we provide no point-by-point responses below.

Circularity Check

0 steps flagged

No significant circularity; derivations are self-contained proofs

full rationale

The paper introduces an explicit model extension (random sample of adversarial input revealed in advance) and then states existence of algorithms plus an impossibility result for the secretary problem. These are established via direct competitive analysis and proof techniques standard to the field; no equations reduce a claimed prediction or ratio back to a fitted parameter by construction, no load-bearing uniqueness theorem is imported solely via self-citation, and no ansatz is smuggled. The central claims remain independent of the paper's own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions and assumptions from competitive analysis and the secretary problem in prior literature; no free parameters, ad-hoc axioms, or invented entities are mentioned in the abstract.

axioms (1)
  • domain assumption Standard assumptions of competitive analysis in online algorithms and the secretary problem
    The model and results build directly on established definitions of competitive ratio and the secretary problem from prior work.

pith-pipeline@v0.9.0 · 5694 in / 1429 out tokens · 27701 ms · 2026-05-24T22:46:04.933239+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

17 extracted references · 17 canonical work pages

  1. [1]

    Pro phet inequalities with limited information

    Pablo Azar, Robert Kleinberg, and Matthew Weinberg. Pro phet inequalities with limited information. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on D iscrete Algorithms (SODA) , pages 1358–1377, 2014

    work page 2014

  2. [2]

    A knapsack secretary problem with applications

    Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. A knapsack secretary problem with applications. In Approximation, Randomization, and Combinatorial Optimiza - tion. Algorithms and Techniques , pages 16–28. 2007

    work page 2007

  3. [3]

    M atroids, secretary problems, and online mechanisms

    Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. M atroids, secretary problems, and online mechanisms. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Di s- crete Algorithms (SODA) , pages 434–443, 2007

    work page 2007

  4. [4]

    Secretary p roblems via linear programming

    Niv Buchbinder, Kamal Jain, and Mohit Singh. Secretary p roblems via linear programming. Math. Oper. Res. , 39(1):190–206, 2014

    work page 2014

  5. [5]

    Prophet inequalities for I.I.D

    Jos´ e Correa, Paul D¨ utting, Felix Fischer, and Kevin Schewior. Prophet inequalities for I.I.D. random variables from an unknown distribution. In Proceedings of the 2019 ACM Conference on Economics and Computation, (EC) , pages 3–17, 2019

    work page 2019

  6. [6]

    Recent developments in prophet inequalities

    Jos´ e Correa, Patricio Foncea, Ruben Hoeksma, Tim Ooste rwijk, and Tjark Vredeveld. Recent developments in prophet inequalities. SIGecom Exchanges, 17(1):61–70, 2018

    work page 2018

  7. [7]

    The optimum choice of the instant for stop ping a markov process

    Eugene Dynkin. The optimum choice of the instant for stop ping a markov process. Soviet Mathematics, 4:627–629, 1963

    work page 1963

  8. [8]

    Recognizing the m aximum of a sequence

    John Gilbert and Frederick Mosteller. Recognizing the m aximum of a sequence. Journal of the American Statistical Association , pages 35–73, 1966

    work page 1966

  9. [9]

    Comparisons of stop rule and supremum expectations of iid random variables

    Theodore Hill and Robert Kertz. Comparisons of stop rule and supremum expectations of iid random variables. The Annals of Probability , 10(2):336–345, 1982. 20

    work page 1982

  10. [10]

    Stop rule and supremum expectations of ii d random variables: a complete comparison by conjugate duality

    Robert Kertz. Stop rule and supremum expectations of ii d random variables: a complete comparison by conjugate duality. Journal of multivariate analysis , 19(1):88–112, 1986

    work page 1986

  11. [11]

    Secretary problems with non- uniform arrival order

    Thomas Kesselheim, Robert Kleinberg, and Rad Niazadeh . Secretary problems with non- uniform arrival order. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, (STOC) , pages 879–888, 2015

    work page 2015

  12. [12]

    An optimal on- line algorithm for weighted bipartite matching and extensi ons to combinatorial auctions

    Thomas Kesselheim, Klaus Radke, Andreas T¨ onnis, and B erthold V¨ ocking. An optimal on- line algorithm for weighted bipartite matching and extensi ons to combinatorial auctions. In Proceedings of the 21st Annual European Symposium on Algori thms (ESA) , pages 589–600, 2013

    work page 2013

  13. [13]

    A multiple-choice secretary algori thm with applications to online auc- tions

    Robert Kleinberg. A multiple-choice secretary algori thm with applications to online auc- tions. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Dis crete Algorithms, (SODA), pages 630–631, 2005

    work page 2005

  14. [14]

    Dynamic programming and decision theor y

    Denis Lindley. Dynamic programming and decision theor y. Journal of the Royal Statistical Society: Series C (Applied Statistics) , 10(1):39–51, 1961

    work page 1961

  15. [15]

    Online matching and ad allocation

    Aranyak Mehta. Online matching and ad allocation. Found. Trends Theor. Comput. Sci. , 8(4):265–368, 2012

    work page 2012

  16. [16]

    Applications o f ramsey’s theorem to decision tree complexity

    Shlomo Moran, Marc Snir, and Udi Manber. Applications o f ramsey’s theorem to decision tree complexity. J. ACM , 32(4):938–949, 1985

    work page 1985

  17. [17]

    Beyond worst-case analysis

    Tim Roughgarden. Beyond worst-case analysis. Commun. ACM , 62(3):88–96, 2019. 21

    work page 2019