cs.DSNov 10, 2026

Multiple-Choice Secretary Problem with Predictions

Authors: Jing Yuan, Qi Cai, Xin Gao, Shaojie Tang

Organizations: University of North Texas · University at Buffalo

Abstract

We study the multiple-choice secretary problem, in which candidates arrive in uniformly random order and the goal is to select at most kk candidates to maximize their total value. We consider a setting where predictions of individual candidate values are available before any candidate arrives. Fujii and Yoshida's Learned Kleinberg algorithm achieves competitive loss O(min⁡{log⁡k/k,\eps})O(\min\{\log k/\sqrt{k},\eps\}), where kk is the selection capacity and \eps\eps is the maximum multiplicative prediction error. We remove the logarithmic factor through a sharper analysis of the same switching algorithm with a retuned threshold. The resulting competitive ratio is at least max⁡{0,1−min⁡{32/k,4\eps}}\max\{0,1-\min\{32/\sqrt{k},4\eps\}\}. In particular, exact predictions (\eps=0\eps=0) achieve the offline optimum on every arrival order.

Figures & tables

Explore similar work

CardsList
  1. The Secretary Problem with a Stochastic Precursor

    May 21, 2026Franziska Eberle, Alexander LindermayrSequential Decision MakingOptimal Stopping

  2. Certify the Decision, Not Every Score: Exact Top-k Selection from Few Evaluations

    Oct 10, 2026Yuhe Sui, Yingzhi TangDecision-Making under UncertaintyAdaptive Sampling

  3. Learning Augmented Exact Exponential Algorithms

    Jun 17, 2026Tatiana Belova, Yuriy Dementiev, Danil SagunovLearning-Augmented Algorithms