- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies a secretary problem in which the decision maker receives a content-free stochastic signal that arrives no later than the best item, so the information is provided in the timing. The paper characterizes optimal policies and success probabilities under both random and adversarial arrival orders.
Critical strengths
Their model is a special case of the framework of Dütting et al. (2024), whose structural results already apply. The paper’s contribution is an explicit recursion and a closed-form analysis under the additional assumption that the side information signal comes from the -power distribution family.
I find the paper well written, with a clear problem formulation and a systematic theoretical treatment. The results are presented carefully, and the paper gives a useful characterization of how the timing of a content-free signal can improve the performance of online selection algorithms. Overall, I find the paper a solid theoretical contribution to online algorithms and optimal stopping, and I support its acceptance.
Critical weaknesses
Their model is a special case of the framework of Dütting et al. (2024), whose structural results already apply.
Questions for authors
None
Reply to Reviewer iQXM
Thank you for supporting acceptance.
We agree (see updated Section 1.1) that our random-order model is a special case of the framework of Dütting et al., which assumes random order and a known distribution. Several of our results lie outside it:
Within the framework, their LP computes the optimal value for each instance. The α-specific structure and closed forms require our analysis, just as their own closed forms for samples and noisy binary advice did. The revision makes this explicit.
If this addresses your concern, we would be grateful if you would consider it in your assessment.