Additively Competitive Secretaries
Mohammad Mahdian, Jieming Mao, Enze Sun, Kangning Wang, Yifan Wang
Abstract
In the secretary problem, a set of secretary candidates arrive in a uniformly random order and reveal their values one by one. A company, who can only hire one candidate and hopes to maximize the expected value of its hire, needs to make irrevocable online decisions about whether to hire the current candidate. The classical framework of evaluating a policy is to compute its worst-case competitive ratio against the optimal solution in hindsight, and there the best policy -the "1/e law" -has a competitive ratio of 1/e. We propose an alternative evaluation framework through the lens of regret -the worst-case additive difference between the optimal hindsight solution and the expected performance of the policy, assuming that each value is normalized between 0 and 1. The 1/e law for the classical framework has a regret of 1 -1/e ≈ 0.632; by contrast, we show that the class of "pricing curves" algorithms can guarantee a regret of at most 1/4 = 0.25 (which is tight within the class), and the class of "best-only pricing curves" algorithms can guarantee a regret of at most 0.190 (with a lower bound of 0.171). In addition, we show that in general, no policy can give a regret guarantee better than 0.152. Finally, we discuss other objectives in our regret-minimization framework, such as selecting the top-k candidates for k > 1, or maximizing revenue during the selection process.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on1
Related papers
- Prophet Inequalities: Competing with the Top ℓ Items is EasyMathieu Molina, Nicolas Gast, Patrick Loiseau, Vianney PerchetSODA 2025
- The Secretary Problem with Independent SamplingJosé Correa, Andrés Cristi, Laurent Feuilloley, Tim Oosterwijk et al.SODA 2021 · 18 citations
- Ordinal Secretaries with AdviceHasti Nourmohammadi Sigaroudi, Ying Cao, Bo Sun, Xiaoqi TanAAAI 2026
- The Secretary Problem with Competing Employers on Random Edge ArrivalsXiaohui Bei, Shengyu ZhangAAAI 2022 · 1 citation
- The Secretary Problem with Predicted Additive GapAlexander Braun, Sherry SarkarNeurIPS 2024 · 7 citations
