Abstract: We consider the secretary problem through the lens of learning-augmented algorithms. As it is known that the best possible expected competitive ratio is $1/e$ in the classic setting without predictions, a natural goal is to design algorithms that are 1-consistent and $1/e$-robust. Unfortunately, [FY24] provided hardness constructions showing that such a goal is not attainable when the candidates' true values are allowed to scale with $n$. Here, we provide a simple and explicit alternative hardness construction showing that such a goal is not achievable even when the candidates' true values are constants that do not scale with $n$.
Introduction
The classic secretary problem is a fundamental model for online decision-making under uncertainty. In this setting, $n$ candidates arrive in a random order, and a decision-maker must either hire or reject each candidate immediately upon arrival. The objective is to maximize the value of the hired candidate relative to the maximum value in the set, known as the competitive ratio. It is well-established that the optimal expected competitive ratio in the classic setting is $1/e \approx 0.367$.
With the rise of learning-augmented algorithms, researchers have sought to incorporate external "advice" or predictions to surpass this $1/e$ barrier. Ideally, such algorithms should be consistent (performing perfectly if predictions are accurate) and robust (maintaining the classic $1/e$ performance if predictions are adversarial). While previous work by Fujii and Yoshida (2024) demonstrated that achieving both 1-consistency and $1/e$-robustness is impossible when candidate values can scale exponentially with $n$, this note provides a simpler proof showing this impossibility holds even for small constant values.
The Hardness Construction
The authors establish their result using a specific hardness construction for $n=3$ candidates. This construction acts as a mathematical "trap" that forces any 1-consistent algorithm to sacrifice its robustness. The proof relies on a set of $2k-1$ possible scenarios, where each scenario represents a different sequence of realized candidate values.
In this construction, the algorithm is provided with a prediction corresponding to the first row of the table. Because a 1-consistent algorithm must achieve a competitive ratio of 1 when the prediction is correct, it is "handcuffed": if it encounters a candidate whose value matches the predicted maximum, it must accept that candidate immediately.
Key Insights and Results
The core of the impossibility result lies in the "Price of Perfection." By demanding 1-consistency, the algorithm loses the ability to "wait and see"—the very strategy that provides robustness in the classic secretary problem.
- Indistinguishability: The construction utilizes a "ladder" of values ($s, s^2, s^3, \dots$). Due to the random arrival order, an algorithm often cannot distinguish between a "good" scenario where it should accept a candidate and a "bad" scenario where it should wait.
- The 1/3 Limit: The authors prove that any 1-consistent algorithm cannot achieve a robustness better than $1/3 + o(1)$. Since $1/3 < 1/e$, it is mathematically impossible to match the classic $1/e$ benchmark while remaining perfectly consistent.
- Constant Values: Crucially, this proof shows that the trade-off is fundamental and does not depend on extreme value scaling. The conflict exists even when values are manageable constants (e.g., $s=19$).
Conclusion
This work clarifies the fundamental limits of learning-augmented algorithms for the secretary problem. While the proof focuses on $n=3$, it generalizes to larger $n$ by padding instances with low-value candidates.
Future research may explore the trade-off curve for "relaxed consistency"—investigating how much robustness can be recovered if one settles for a consistency slightly less than 1.0. Additionally, exploring different prediction models or the "optimal stopping" variant (maximizing the probability of picking the single best candidate) remains an open area for further refinement of these bounds.
Summary updated