Secretary Problem with Predictions and Ordering

The classic secretary problem, a cornerstone of optimal stopping theory, assumes a random, immutable arrival order of candidates. While recent work has integrated machine-learned predictions to improve selection, the power to set the arrival order based on these predictions remains largely untapped. This paper introduces a novel framework for the secretary problem that leverages predictions for both valuation and strategic scheduling. We propose an algorithm that strategically controls the arrival time of the top-predicted candidate and dynamically adapts its hiring policy based on observed prediction accuracy. Our analysis shows that this approach achieves a worst-case competitive ratio of 0.229, surpassing the 0.215 bound of state-of-the-art algorithms that do not control ordering, bringing it closer to the upper bound of $1/e \approx 0.368$ while maintaining consistency guarantees. Furthermore, we demonstrate that our ordering framework can be adapted to improve fairness guarantees, doubling the success probability in a known fair algorithm from 1/16 to 1/8. Our results highlight that controlling the sequence is a powerful tool for building more robust and fair learning-augmented online algorithms.