WorksComputer Science
Multiple-Choice Secretary Problem with Predictions
Abstract
We study the multiple-choice secretary problem, in which candidates arrive in uniformly random order and the goal is to select at most 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/\sqrt{k},\eps\}), where is the selection capacity and \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/\sqrt{k},4\eps\}\}. In particular, exact predictions (\eps=0) achieve the offline optimum on every arrival order.
Introduction
Online algorithms make decisions under uncertainty about future inputs. Advances in machine learning allow predictions to guide these decisions, raising the question of how to exploit accurate predictions while remaining robust to errors. The multiple-choice secretary problem models online selection under a capacity constraint. Candidates arrive in uniformly random order, and each candidate’s value is revealed upon arrival. The algorithm must immediately accept or reject each candidate, selecting at most to maximize their total value. The challenge is to balance accepting valuable candidates now against reserving capacity for better candidates later. Without predictions, Kleinberg [14] achieves competitive ratio against the sum of the largest values. With predictions, we additionally seek perfect consistency: recovering the offline optimum when predictions are exact, while retaining a strong guarantee under arbitrary errors. These objectives follow the consistency–robustness framework [15].
Fujii and Yoshida [11] introduced the candidate-value prediction model studied here, in which predictions of all candidates’ values are available before arrivals. A motivating application is hiring: machine learning models can estimate candidates’ abilities from their résumés or publicly available information before interviews. These estimates may be inaccurate because the information is incomplete, misleading, or deliberately manipulated. Interviews reveal the candidates’ true values, and the decision maker must immediately accept or reject each candidate, as an offer may no longer be possible later. The model assumes that candidates arrive in uniformly random order, as in the classical secretary problem. Their Learned Kleinberg algorithm follows the predicted top- set until it observes a sufficiently large error, then switches to a classical secretary algorithm. They prove competitive loss , where is the maximum multiplicative prediction error, and ask whether the logarithmic factor can be removed.
Our result. We resolve this question by proving loss for the same switching algorithm with a different monitoring threshold. This algorithm does not need to know . The explicit guarantee is
Our algorithm matches the classical lower bound on worst-case loss [14, 17] up to a constant factor, while recovering the offline optimum on every arrival order when predictions are exact. Table 1 places the result alongside the closest multiple-choice guarantees.
Table 1. Competitive ratios for random-order multiple-choice selection.
Problem and algorithm
Model and prediction error
Let and . Candidate has a nonnegative value and a nonnegative prediction . Both vectors are fixed before a uniformly random permutation of is drawn. The algorithm initially knows , , the labels, and all predictions. It observes when arrives and must accept or reject immediately. Acceptances are irrevocable, and at most are allowed.
For , write and . Fix a label-based rule for breaking ties. Let be the predicted top- set and the true top- set, so . The prediction error is , where
For finite ,
A competitive guarantee means on every fixed input, with expectation over arrival order and internal randomness. Following the consistency–robustness framework for algorithms with predictions [15, 11], perfect consistency means achieving when , while robustness requires a competitive guarantee that holds for every prediction vector, regardless of its accuracy.
Algorithm design
For a fixed candidate set , let be the sum of its largest values, with . For the classical multiple-choice secretary problem without predictions, Kleinberg [14] provides a randomized algorithm that selects at most candidates from a uniformly ordered stream and satisfies
For zero capacity or an empty stream, it selects nothing; when , it accepts all remaining candidates. We use as a black-box fallback in the algorithm below.
Specifically, we adopt Fujii and Yoshida’s Learned Kleinberg algorithm [11] with a retuned threshold , as shown in Algorithm 1. It accepts candidates in the predicted top- set until the first prediction error exceeds or capacity is exhausted. If capacity remains, it accepts the candidate that triggers the switch and runs Kleinberg’s algorithm [14] on subsequent arrivals with the remaining slots.
Algorithm 1. Learned Kleinberg with threshold [11]
Input: predictions , capacity , and .
Compute the predicted top- set and initialize .
On arrival of , stop if .
If , add to , set , and run a fresh on all subsequent arrivals. Return together with the fallback ’s selections.
Otherwise, add to if , and continue.
Main guarantees
Theorem 1. With threshold
Algorithm 1 satisfies
When , it obtains on every arrival order.
The result follows from the next threshold-dependent bound and the accuracy guarantee of selecting when no error triggers a switch.
Theorem 2. For every , Algorithm 1 satisfies
The remainder of the paper develops the analysis needed to prove Theorems 2 and 1.
Proof overview and stopping-time setup
Fix a threshold and let
The set is fixed before the arrival permutation. If , the algorithm selects , and
We therefore focus on .
The fixed benchmark. Let
The set combines the accurately predicted part of with the erroneous part of the optimum. Its value is close to OPT, and all its members arriving before the first error are accepted. The proof has three steps:
Compare with OPT.
Condition on the switch and bound prefix value plus expected fallback value by a capacity-dependent fraction of .
Average that fraction over the remaining capacity.
Representing the random order. Assign independent times and process candidates in increasing time order. This standard representation [6, 14] also underlies Fujii and Yoshida’s analysis [11]. Define
and
Here is the set of candidates accepted before the trigger candidate arrives, is the number of unfilled selection slots immediately before ’s arrival, and is the suffix. For , the algorithm accepts and gives slots to the fallback. For , it has already accepted all of .
Let record the ordered prefix through the trigger, the trigger time and identity , and the remaining set . Conditional on , the arrival times of candidates in are independent and uniform on , so their relative order is uniform. Thus, for , the fallback guarantee in (2) applies with capacity ; for , no capacity remains for the fallback.
Since is the earliest arrival time among the erroneous candidates, whose arrival times are independent and uniform on , , . Consequently, the remaining-time fraction satisfies , , and has density on .
Following the error-count decomposition in Fujii and Yoshida [11], we distinguish two regimes, with the split now at . When , the first error arrives early enough in expectation that little value or capacity has been lost. When , the switch may occur late, and the value collected before switching becomes essential.
Few erroneous candidates:
We first consider the few-error case, . We show that the benchmark set retains most of the optimal value, then bound how much of this value the algorithm recovers across its two phases.
Recall that every satisfies
The next lemma adapts the value comparison in the proof of Lemma 6 of Fujii and Yoshida [11] to bound in terms of the number of erroneous candidates.
Lemma 1. The set in (8) satisfies
Proof. Let and . Removing from a predicted top- set leaves the top predictions among . To see this, any candidate in has predicted rank ahead of every candidate outside , under the fixed tie rule.
If , the top- predicted sum in is at least . When , take the best predictions and add nonnegative terms. When , the largest predictions within have average at least its overall average. Since , , and , this proves . Applying (4.1) to both sets yields . This inequality also holds when , since its right-hand side is zero. Adding and using gives , as claimed.
To turn this comparison into a performance bound, we must account for the fact that a late switch may leave only a few slots. The next result makes the value already collected compensate for that loss of capacity.
Define
where is the fallback ratio in (2.2). The factor accounts for the classical fallback, and accounts for the benchmark’s possible excess size.
Proof. When , the right side is zero. Suppose , and put . Recall that is the set of candidates accepted before the first erroneous candidate arrives at time . All members of arriving before belong to , so they are in . The trigger is also accepted. Thus
Write and . Since ,
The largest values of , or all of if it is smaller, therefore give
The fallback contributes at least conditionally on . The already accepted candidates contribute . Since ,
Finally, is fixed before the arrival times are sampled, so can be taken outside the expectation.
Lower bounding
Lemma 2 reduces the few-error analysis to bounding . We first compare with a binomial mixture, then average the two losses in (13).
We use the same conditional binomial description of the predicted candidates as in Fujii and Yoshida [11, Lemma 3]. Let . Conditional on , all erroneous members of are still unprocessed just before . Each of its other members remains independently with probability . Hence
To obtain a simpler lower bound on , condition on and let be independent Bernoulli random variables, each equal to 1 with probability . We can represent and define . Since , this construction ensures
Thus, conditional on , this capacity lower bound has a binomial distribution with trials and success probability .
Fujii and Yoshida [11] bound a reciprocal-capacity expectation by comparing it with the case . We use the same reference case, make the comparison explicit through a coupling, and apply it directly to the clipped square-root loss.
Let be uniform on . When , the remaining-time fraction is uniform, so we define the reference variable by . Averaging over gives
Thus, although is binomial conditional on , its unconditional distribution is uniform on .
For general , retain and define . Since , the variable is uniform on , and . To compare the two conditional binomial distributions and , take auxiliary independent uniform random variables , independent of , and set , . These variables have the required conditional binomial distributions. Since , every success counted by is also counted by , and hence . Consequently, for every nonincreasing function , we have and therefore
We now derive a lower bound on .
Lemma 3. For ,
Proof. There are two losses in (13): the fraction of the remaining benchmark that fits, and the classical fallback’s approximation loss. Define
Using from (18),
Indeed, for , write with and . Then , and gives (22). For , the right side is at least one.
The function is nonincreasing. Applying (19) directly to this square-root penalty yields
The last inequality uses , , and , with an empty sum when . We bound the capacity-excess term separately for and . When , is uniform on , so
where and we used .
For , we use the classical binomial reciprocal identity [7], following Fujii and Yoshida [11 Lemma 4]. Since ,
Moreover, has density , and hence .
Using and averaging over , we obtain
Here for , and . Combining (22)–(24) proves the lemma.
Combining the few-error bounds
Corollary 1. If , then .
Proof. If , the claim follows from nonnegativity. Otherwise, . Lemmas 2 and 3 give . Applying Lemma 1, we obtain
The second inequality uses for . The last inequality follows from and .
Many erroneous candidates:
We now consider the many-error case, , in which the algorithm tends to switch early. Following the early-switch analysis of Fujii and Yoshida [11], we control the losses due to the switch time and the capacity used before switching. Our argument bounds these losses directly in expectation, replacing their high-probability bounds.
Lemma 4. If , then
Proof. Recall that is the set of candidates arriving strictly after the trigger at time . Let . When , the fallback has slots.
Since , we have . Applying (2) conditionally on gives
using and . For , we have , so the final right-hand side is nonpositive and the same bound follows from nonnegativity.
A candidate in is absent from with probability ; a candidate in is absent precisely when it is the trigger, with probability . Similarly, each member of precedes the trigger with probability . Thus
Taking expectations in (27) gives
using .
Completing the main proof
We combine the few-error analysis with the many-error analysis to prove Theorem 2. We then choose the threshold and apply the no-switch accuracy bound when and the robustness bound when to establish Theorem 1.
Proof of Theorem 2
Proof (Proof of Theorem 2). If , equation (7) gives the stronger bound . If , the result follows from Corollary 1. If , Lemma 4 gives
These cases exhaust all possible values of .
Proof of Theorem 1
When all prediction errors are at most , the algorithm never leaves the predicted shortlist. The following bound is the consistency argument from [11].
Lemma 5. [11 Lemma 1] If , then and
Now we are ready to prove Theorem 1.
Proof (Proof of Theorem 1). Recall that . We first prove the bound without clipping it at zero.
Suppose , so . Theorem 2 gives, for arbitrary predictions,
If , then , so this is exactly the desired bound
If , no error exceeds the switching threshold, and Lemma 5 also gives . Combining the two guarantees yields
Now suppose , so and . If , then . Lemma 5 therefore gives
If , both and exceed two, so the desired bound before clipping is negative and follows from .
Finally, nonnegativity allows us to replace the bound by its maximum with zero, proving (2.4), including when . With exact predictions, no switch occurs and is a true top- set, so for every arrival order.
Extension: Measuring prediction error at the selection boundary
The maximum prediction error can be large even when the predicted top- set is optimal. For example, if a candidate in turns out to be worth more than predicted, this strengthens the case for selecting that candidate. Yet the original monitoring rule can switch on precisely such an error. We therefore ask whether the algorithm can retain its guarantee while ignoring errors of this kind.
Fujii and Yoshida [11] compare candidates outside the predicted top- set with its predicted cutoff , while measuring error inside against each candidate’s own prediction. We use the same cutoff on both sides: a shortlisted candidate is a concern only if its true value falls below , and an excluded candidate is a concern only if its true value exceeds .
Cutoff error and switching rule. Define the cutoff error by
with . In particular, precisely when every shortlisted candidate has value at least and every excluded candidate has value at most . In that case, is a true top- set. The cutoff error satisfies : for we have , while for we have . It is also no larger than Fujii and Yoshida’s boundary-sensitive error whenever their relative errors are defined.
Modify only the trigger in Algorithm 1. On the arrival of candidate , switch precisely when
As before, the algorithm accepts the trigger if a slot remains and runs Kleinberg’s algorithm on subsequent arrivals with the remaining capacity. Once and have been computed, this rule no longer needs the individual predictions.
Theorem 3. With the trigger (7.2) and threshold (2.3), the algorithm satisfies
If , no switch occurs and . In particular, if , the algorithm obtains on every arrival order.
Proof. Fix , let be the set of candidates satisfying (7.2), and write and . The key observation is that any nontriggering shortlisted candidate and any nontriggering excluded candidate satisfy
This pairwise value comparison replaces the bounds used in the proof of Lemma 1.
To see this, suppose . Let , , and let consist of the highest-value candidates in . Since and , we have . Match each member of to a distinct member of ; this is possible because . Each matched member of has value at least times that of its partner by (7.3). Members of contribute their own value. Hence
Adding recovers the bound of Lemma 1 for .
The remaining analysis uses only that is fixed before arrivals and that the algorithm follows until the first member of arrives or capacity is exhausted. Thus the conditional completion, capacity averaging, and many-error bounds apply unchanged. For , the comparison above gives directly. This proves Theorem 2 for the modified rule, regardless of .
Finally, if , the strict trigger never fires. Applying the same matching argument at threshold with gives . Combining this accuracy bound with Theorem 2, which also holds for the modified rule, and following the argument in the proof of Theorem 1 yields the stated guarantee.
Related work
Classical secretary selection. The single-choice secretary problem dates to Dynkin [10]; Gupta and Singla [12] survey the broader random-order setting. Independent uniform arrival times provide a standard analytical representation [6]. For the additive multiple-choice objective, Kleinberg [14] established the optimal robustness order . His algorithm supplies our fallback after a prediction error is detected. Babaioff et al. [3] study knapsack secretary selection, including a value guarantee for equal costs, while Albers and Ladewig [1] develop simple algorithms with stronger guarantees at small capacities. Qiao and Zhang [17] achieve the optimal asymptotic ratio using memory. Their focus is prediction-free memory efficiency; our focus is retaining that robustness order while obtaining the optimum with exact predictions.
Predictions and advice interfaces. Learning-augmented algorithms seek guarantees that combine accuracy-dependent performance with worst-case robustness; see Mitzenmacher and Vassilvitskii [15]. Fujii and Yoshida [11] introduce the per-candidate prediction model studied here. Their Learned Kleinberg algorithm achieves loss ; our analysis removes the logarithmic factor with a different monitoring threshold. Antoniadis et al. [2] predict the optimum value in secretary selection and also study online matching and graphic matroids. Braun and Sarkar [5] use a predicted additive gap, obtaining a guarantee when that gap is exact. Dütting et al. [9] develop an advice framework and factor-revealing linear programs for success probabilities, encompassing samples, known distributions, and noisy binary advice. Nourmohammadi et al. [16] study Ordinal Secretaries with Advice, including multiple-choice and rehiring variants. Their advice concerns the best candidate’s arrival position, and their multiple-choice objective is the probability of including that candidate among those selected. Our advice instead gives numerical predictions for labeled candidates, and our objective compares total selected value with the true top- sum.
Single-choice guarantees and arrival control. Karisani et al. [13] improve single-choice random-order robustness from to , while retaining the accuracy term . They obtain robustness when predictions can be used to choose the arrival order. Yiming [18] studies prediction-based ordering, with robustness and improved fairness bounds in that setting. Choo and Ling [8] establish a limiting upper bound for perfectly consistent single-choice algorithms. These works study single-choice robustness; we study how robustness improves with under random arrivals.
Fairness and boundary-sensitive error. Balkanski, Ma, and Maggiori [4] combine utility guarantees with individual selection-probability guarantees. Their multiple-choice result gives expected value at least , where , together with rank-dependent fairness bounds. We analyze relative total value under multiplicative prediction error. Fujii and Yoshida [11] also introduce a boundary-sensitive error: candidates outside the predicted top- set are compared with its predicted cutoff, while candidates inside retain two-sided multiplicative error.
AI Disclosure
We used ChatGPT to help audit and revise the manuscript.
References
References
- [1]Albers, S., Ladewig, L.: New results for the k-secretary problem. Theoretical Computer Science 863, 102–119 (2021). https://doi.org/10.1016/j.tcs.2021.02.022
- [2]Antoniadis, A., Goulekakis, T., Kleer, P., Kolev, P.: Secretary and online matching problems with machine learned advice. Discrete Optimization 48, 100778 (2023). https://doi.org/10.1016/j.disopt.2023.100778
- [3]Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: A knapsack secretary problem with applications. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM). pp. 16–28 (2007). https://doi.org/10.1007/978-3-540-74208-1_2
- [4]Balkanski, E., Ma, W., Maggiori, A.: Fair secretaries with unfair predictions. In: Advances in Neural Information Processing Systems. vol. 37 (2024), https://arxiv.org/abs/2411.09854
- [5]Braun, A., Sarkar, S.: The secretary problem with predicted additive gap. In: Advances in Neural Information Processing Systems. vol. 37 (2024), https://arxiv.org/abs/2409.20460
- [6]Bruss, F.T.: A unified approach to a class of best choice problems with an unknown number of options. The Annals of Probability 12(3), 882–889 (1984). https://doi.org/10.1214/aop/1176993237
- [7]Chao, M.T., Strawderman, W.E.: Negative moments of positive random variables. Journal of the American Statistical Association 67(338), 429–431 (1972). https://doi.org/10.1080/01621459.1972.10482404
- [8]Choo, D., Ling, C.K.: A short note about the learning-augmented secretary problem (2024), https://arxiv.org/abs/2410.06583
- [9]Dü⟩tting, P., Lattanzı, S., Paes Leme, R., Vassilvitskii, S.: Secretaries with advice. Mathematics of Operations Research 49(2), 856–879 (2024). https://doi.org/10.1287/moor.2023.1384
- [10]Dynkin, E.B.: The optimum choice of the instant for stopping a Markov process. Soviet Mathematics Doklady 4, 627–629 (1963)
- [11]Fujii, K., Yoshida, Y.: The secretary problem with predictions. Mathematics of Operations Research 49(2), 1241–1262 (2024). https://doi.org/10.1287/moor.2022.0031, https://arxiv.org/abs/2306.08340
- [12]Gupta, A., Singla, S.: Random-order models. In: Roughgarden, T. (ed.) Beyond the Worst-Case Analysis of Algorithms, chap. 11, pp. 234–258. Cambridge University Press (2021). https://doi.org/10.1017/9781108637435.015
- [13]Karisani, H., Daneshvaramoli, M., Beyhaghi, H., Hajiesmaili, M., Musco, C.: The secretary problem with predictions and a chosen order. In: 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). LIPICs, vol. 362, pp. 86:1–86:24 (2026). https://doi.org/10.4230/LIPIcs.ITCS.2026.86
- [14]Kleinberg, R.D.: A multiple-choice secretary algorithm with applications to online auctions. In: Proceedings of the Sixteenth Annual ACM–SIAM Symposium on Discrete Algorithms (SODA). pp. 630–631 (2005), https://www.cs.cornell.edu/~rdk/papers/MultSec.pdf
- [15]Mitzenmacher, M., Vassilvitskii, S.: Algorithms with predictions. Communications of the ACM 65(7), 33–35 (2022). https://doi.org/10.1145/3528087 Jing Yuan, Qi Cai, Xin Gao, and Shaojie Tang
- [16]Nourmohammadi, H., Cao, Y., Sun, B., Tan, X.: Ordinal secretaries with advice. Proceedings of the AAAI Conference on Artificial Intelligence 40(43), 37108–37116 (2026). https://doi.org/10.1609/aaai.v40i43.41040
- [17]Qiao, M., Zhang, W.: Optimal k-secretary with logarithmic memory. In: 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). LIPIcs, vol. 374, pp. 150:1–150:17 (2026). https://doi.org/10.4230/LIPIcs.ICALP.2026.150
- [18]Yiming, K.: Secretary problem with predictions and ordering. In: Proceedings of the 29th International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research, vol. 300, pp. 352–360 (2026), https://proceedings.mlr.press/v300/yiming26a.html