# The Secretary Problem with Predictions and a Chosen Order

arXiv: https://arxiv.org/abs/2601.07482 · HTML: https://mlsanity.com/paper/2601.07482/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 70 references that are in the map.
- First posted on arXiv 12 Jan 2026.

## Builds on (most cited first, 30 of 35)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Secretaries with Advice](https://mlsanity.com/paper/2011.06726/) (2020)
- [Better and Simpler Learning-Augmented Online Caching](https://mlsanity.com/paper/2005.13716/) (2020)
- [Learning Augmented Energy Minimization via Speed Scaling](https://mlsanity.com/paper/2010.11629/) (2020)
- [Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems](https://mlsanity.com/paper/2109.01556/) (2021)
- [Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms](https://mlsanity.com/paper/2310.20598/) (2023)
- [Competitive Analysis with a Sample and the Secretary Problem](https://mlsanity.com/paper/1907.05350/) (2019)
- [Prophet Secretary](https://mlsanity.com/paper/1507.01155/) (2015)
- [Random-Order Models](https://mlsanity.com/paper/2002.12159/) (2020)
- [Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems](https://mlsanity.com/paper/2406.18752/) (2024)
- [Prophet Secretary: Surpassing the 1-1/e Barrier](https://mlsanity.com/paper/1711.01834/) (2017)
- [Robust Algorithms for the Secretary Problem](https://mlsanity.com/paper/1911.07352/) (2019)
- [The Secretary Problem with Predictions](https://mlsanity.com/paper/2306.08340/) (2023)
- [Fair Secretaries with Unfair Predictions](https://mlsanity.com/paper/2411.09854/) (2024)
- [Multi-Platform Autobidding with and without Predictions](https://mlsanity.com/paper/2502.19317/) (2025)
- [Prophet Secretary Through Blind Strategies](https://mlsanity.com/paper/1807.07483/) (2018)
- [The Secretary Problem with Independent Sampling](https://mlsanity.com/paper/2011.07869/) (2020)
- [Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design](https://mlsanity.com/paper/2204.01425/) (2022)
- [Prophets, Secretaries, and Maximizing the Probability of Choosing the Best](https://mlsanity.com/paper/1910.03798/) (2019)
- [New Results for the k-Secretary Problem](https://mlsanity.com/paper/2012.00488/) (2020)
- [Robust Secretary and Prophet Algorithms for Packing Integer Programs](https://mlsanity.com/paper/2112.12920/) (2021)
- [Clock Auctions Augmented with Unreliable Advice](https://mlsanity.com/paper/2408.06483/) (2024)
- [The Secretary Problem with Predicted Additive Gap](https://mlsanity.com/paper/2409.20460/) (2024)

## Built on by (most cited first, 2 of 2)

- [The Secretary Problem with a Stochastic Precursor](https://mlsanity.com/paper/2605.22653/) (2026)
- [Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications](https://mlsanity.com/paper/2609.04787/) (2026)

## Abstract (arXiv)

We study a learning-augmented variant of the secretary problem, recently introduced by Fujii and Yoshida (2023), in which the decision-maker has access to machine-learned predictions of candidate values. The central challenge is to balance consistency and robustness: when predictions are accurate, the algorithm should select a near-optimal secretary, while under inaccurate predictions it should still guarantee a bounded competitive ratio. We consider both the classical Random Order Secretary Problem (ROSP), where candidates arrive in a uniformly random order, and a more natural learning-augmented model in which the decision-maker may choose the arrival order based on predicted values. We call this model the Chosen Order Secretary Problem (COSP), capturing scenarios such as interview schedules set in advance. We propose a new randomized algorithm applicable to both ROSP and COSP. Our method switches from fully trusting predictions to a threshold-based rule once a large prediction deviation is detected. Let ε ∈ [0,1] denote the maximum multiplicative prediction error. For ROSP, our algorithm achieves a competitive ratio of max0.221, (1-ε)/(1+ε), improving upon the prior bound of max0.215, (1-ε)/(1+ε). For COSP, we achieve max0.262, (1-ε)/(1+ε), surpassing the 0.25 worst-case bound for prior approaches and moving closer to the classical secretary benchmark of 1/e ≈ 0.368. These results highlight the benefit of combining predictions with arrival-order control in online decision-making.