betaFeedback

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 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/\sqrt{k},\eps\}), where kk 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 kk 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 1−O(k−1/2)1-O(k^{-1/2}) against the sum of the kk 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-kk set until it observes a sufficiently large error, then switches to a classical secretary algorithm. They prove competitive loss O(min⁡{log⁡k/k,ε})O(\min\{\log k/\sqrt{k},\varepsilon\}), where ε\varepsilon is the maximum multiplicative prediction error, and ask whether the logarithmic factor can be removed.

Our result. We resolve this question by proving loss O(min⁡{k−1/2,ε})O(\min\{k^{-1/2},\varepsilon\}) for the same switching algorithm with a different monitoring threshold. This algorithm does not need to know ε\varepsilon. The explicit guarantee is

E[v(A)]≥max⁡{0,1−min⁡{32k,4ε}}OPT.\mathbb{E}[v(A)] \ge\max\left\{0,1-\min\left\{\frac{32}{\sqrt{k}},4\varepsilon\right\}\right\}\mathrm{OPT}.

Our algorithm matches the classical Ω(k−1/2)\Omega(k^{-1/2}) 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.

WorkPredictionCompetitive guarantee
Kleinberg [14]None1−O(k−1/2)1-O(k^{-1/2})
Qiao–Zhang [17]None1−O(k−1/2)1-O(k^{-1/2}) with O(log⁡k)O(\log k) memory
Fujii–Yoshida [11]Candidate values1−O(min⁡{log⁡k/k,ε})1-O(\min\{\log k/\sqrt{k},\varepsilon\})
This paperCandidate values1−O(min⁡{k−1/2,ε})1-O(\min\{k^{-1/2},\varepsilon\})

Table 1. Competitive ratios for random-order multiple-choice selection.

Problem and algorithm

Model and prediction error

Let N={1,…,n}N=\{1,\ldots,n\} and 1≤k≤n1\le k\le n. Candidate ii has a nonnegative value viv_i and a nonnegative prediction v^i\hat{v}_i. Both vectors are fixed before a uniformly random permutation of NN is drawn. The algorithm initially knows nn, kk, the labels, and all predictions. It observes viv_i when ii arrives and must accept or reject ii immediately. Acceptances are irrevocable, and at most kk are allowed.

For D⊆ND\subseteq N, write v(D)=∑i∈Dviv(D)=\sum_{i\in D}v_i and v^(D)=∑i∈Dv^i\hat{v}(D)=\sum_{i\in D}\hat{v}_i. Fix a label-based rule for breaking ties. Let PP be the predicted top-kk set and OO the true top-kk set, so OPT=v(O)\mathrm{OPT}=v(O). The prediction error is ε=max⁡iei\varepsilon=\max_i e_i, where

ei={∣v^i−vi∣/vi,vi>0,0,vi=v^i=0,+∞,vi=0<v^i.e_i= \begin{cases} |\hat{v}_i-v_i|/v_i, & v_i>0,\\ 0, & v_i=\hat{v}_i=0,\\ +\infty, & v_i=0<\hat{v}_i. \end{cases}

For finite ε\varepsilon,

(1−ε)vi≤v^i≤(1+ε)vi.(1)(1-\varepsilon)v_i\le\hat{v}_i\le(1+\varepsilon)v_i. \tag*{(1)}

A competitive guarantee g(k,ε)g(k,\varepsilon) means E[v(A)]≥g(k,ε)OPT\mathbb{E}[v(A)]\ge g(k,\varepsilon)\mathrm{OPT} 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 OPT\mathrm{OPT} when ε=0\varepsilon=0, while robustness requires a competitive guarantee that holds for every prediction vector, regardless of its accuracy.

Algorithm design

For a fixed candidate set ZZ, let OPT⁡q(Z)\operatorname{OPT}_{q}(Z) be the sum of its largest min⁡{q,∣Z∣}\min\{q, |Z|\} values, with OPT⁡0(Z)=0\operatorname{OPT}_{0}(Z)=0. For the classical multiple-choice secretary problem without predictions, Kleinberg [14] provides a randomized algorithm KqK_q that selects at most qq candidates from a uniformly ordered stream ZZ and satisfies

E[v(Kq(Z))]≥cqOPT⁡q(Z),cq=max⁡{0,1−5/q},q≥1.(2)\mathbb{E}[v(K_q(Z))] \ge c_q \operatorname{OPT}_{q}(Z), \qquad c_q=\max\{0,1-5/\sqrt{q}\}, \qquad q\ge1. \tag*{(2)}

For zero capacity or an empty stream, it selects nothing; when q≥∣Z∣q\ge|Z|, it accepts all remaining candidates. We use KqK_q as a black-box fallback in the algorithm below.

Specifically, we adopt Fujii and Yoshida’s Learned Kleinberg algorithm [11] with a retuned threshold θ\theta, as shown in Algorithm 1. It accepts candidates in the predicted top-kk set PP until the first prediction error exceeds θ\theta or capacity is exhausted. If capacity remains, it accepts the candidate that triggers the switch and runs Kleinberg’s algorithm KqK_q [14] on subsequent arrivals with the remaining slots.

Algorithm 1. Learned Kleinberg with threshold θ\theta [11]

Input: predictions v^\hat{v}, capacity kk, and 0≤θ<10\le\theta<1.

  1. Compute the predicted top-kk set PP and initialize A=∅A=\varnothing.

  2. On arrival of ii, stop if ∣A∣=k|A|=k.

  3. If ∣v^i−vi∣>θvi|\hat{v}_i-v_i|>\theta v_i, add ii to AA, set q=k−∣A∣q=k-|A|, and run a fresh KqK_q on all subsequent arrivals. Return AA together with the fallback KqK_q’s selections.

  4. Otherwise, add ii to AA if i∈Pi\in P, and continue.

Main guarantees

Theorem 1. With threshold

θ=min⁡{12,8k},(3)\theta=\min\left\{\frac{1}{2},\frac{8}{\sqrt{k}}\right\}, \tag*{(3)}

Algorithm 1 satisfies

E[v(A)]≥max⁡{0,1−min⁡{32k,4ε}}OPT⁡.(4)\mathbb{E}[v(A)]\ge\max\left\{0,1-\min\left\{\frac{32}{\sqrt{k}},4\varepsilon\right\}\right\}\operatorname{OPT}. \tag*{(4)}

When ε=0\varepsilon=0, it obtains OPT⁡\operatorname{OPT} on every arrival order.

The result follows from the next threshold-dependent bound and the accuracy guarantee of selecting PP when no error triggers a switch.

Theorem 2. For every 0≤θ<10\le\theta<1, Algorithm 1 satisfies

E[v(A)]≥(1−2θ−16k)OPT⁡.(5)\mathbb{E}[v(A)]\ge\left(1-2\theta-\frac{16}{\sqrt{k}}\right)\operatorname{OPT}. \tag*{(5)}

The remainder of the paper develops the analysis needed to prove Theorems 2 and 1.

Proof overview and stopping-time setup

Fix a threshold θ\theta and let

M={i:∣v^i−vi∣>θvi},m=∣M∣.(6)M = \{i : |\hat{v}_i - v_i| > \theta v_i\}, \qquad m = |M|. \tag*{(6)}

The set MM is fixed before the arrival permutation. If m=0m = 0, the algorithm selects PP, and

v(P)≥v^(P)1+θ≥v^(O)1+θ≥1−θ1+θOPT⁡≥(1−2θ)OPT⁡.(7)v(P) \ge\frac{\hat{v}(P)}{1+\theta} \ge\frac{\hat{v}(O)}{1+\theta} \ge\frac{1-\theta}{1+\theta}\operatorname{OPT} \ge(1-2\theta)\operatorname{OPT}. \tag*{(7)}

We therefore focus on m≥1m \ge1.

The fixed benchmark. Let

B=(P∖M)∪(O∩M),α=1−θ1+θ.(8)B = (P \setminus M) \cup(O \cap M), \qquad\alpha= \frac{1-\theta}{1+\theta}. \tag*{(8)}

The set BB combines the accurately predicted part of PP 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:

  1. Compare v(B)v(B) with OPT.

  2. Condition on the switch and bound prefix value plus expected fallback value by a capacity-dependent fraction of v(B)v(B).

  3. Average that fraction over the remaining capacity.

Representing the random order. Assign independent times Ui∼Unif⁡[0,1]U_i \sim\operatorname{Unif}[0,1] and process candidates in increasing time order. This standard representation [6, 14] also underlies Fujii and Yoshida’s analysis [11]. Define

T=min⁡i∈MUi,J=arg⁡min⁡i∈M Ui,(9)T = \min_{i \in M} U_i, \qquad J = \underset{i \in M}{\arg\min}\ U_i, \tag*{(9)}

and

S=P∩{i:Ui<T},s=∣S∣,r=k−s,Z={i:Ui>T}.(10)S = P \cap\{i : U_i < T\}, \qquad s = |S|, \qquad r = k-s, \qquad Z = \{i : U_i > T\}. \tag*{(10)}

Here SS is the set of candidates accepted before the trigger candidate JJ arrives, rr is the number of unfilled selection slots immediately before JJ’s arrival, and ZZ is the suffix. For r>0r > 0, the algorithm accepts JJ and gives q=r−1q = r-1 slots to the fallback. For r=0r = 0, it has already accepted all of PP.

Let H\mathcal{H} record the ordered prefix through the trigger, the trigger time TT and identity JJ, and the remaining set ZZ. Conditional on H\mathcal{H}, the arrival times of candidates in ZZ are independent and uniform on (T,1)(T,1), so their relative order is uniform. Thus, for r≥2r \ge2, the fallback guarantee in (2) applies with capacity q=r−1q = r-1; for r≤1r \le1, no capacity remains for the fallback.

Since TT is the earliest arrival time among the mm erroneous candidates, whose arrival times are independent and uniform on [0,1][0,1], P(T>t)=(1−t)m\mathbb{P}(T > t) = (1-t)^m, 0≤t≤10 \le t \le1. Consequently, the remaining-time fraction p:=1−Tp := 1-T satisfies P(p≤u)=um\mathbb{P}(p \le u) = u^m, 0≤u≤10 \le u \le1, and has density mum−1m u^{m-1} on (0,1)(0,1).

Following the error-count decomposition in Fujii and Yoshida [11], we distinguish two regimes, with the split now at k\sqrt{k}. When m>km > \sqrt{k}, the first error arrives early enough in expectation that little value or capacity has been lost. When 1≤m≤k1 \le m \le\sqrt{k}, the switch may occur late, and the value collected before switching becomes essential.

Few erroneous candidates: 1≤m≤k1 \le m \le\sqrt{k}

We first consider the few-error case, 1≤m≤k1 \le m \le\sqrt{k}. We show that the benchmark set BB retains most of the optimal value, then bound how much of this value the algorithm recovers across its two phases.

Recall that every i∉Mi \notin M satisfies

(1−θ)vi≤v^i≤(1+θ)vi.(11)(1-\theta)v_i \le\hat{v}_i \le(1+\theta)v_i. \tag*{(11)}

The next lemma adapts the value comparison in the proof of Lemma 6 of Fujii and Yoshida [11] to bound v(B)v(B) in terms of the number mm of erroneous candidates.

Lemma 1. The set in (8) satisfies

v(B)≥α(1−mk)OPT.(12)v(B) \ge\alpha\left(1-\frac{m}{k}\right)\mathrm{OPT}. \tag*{(12)}

Proof. Let a=∣P∖M∣a=|P\setminus M| and d=∣O∖M∣d=|O\setminus M|. Removing MM from a predicted top-kk set leaves the top aa predictions among N∖MN\setminus M. To see this, any candidate in P∖MP\setminus M has predicted rank ahead of every candidate outside PP, under the fixed tie rule.

If d>0d>0, the top-aa predicted sum in N∖MN\setminus M is at least min⁡{1,a/d}v^(O∖M)\min\{1,a/d\}\hat{v}(O\setminus M). When a≥da\ge d, take the best dd predictions and add nonnegative terms. When a<da<d, the largest aa predictions within O∖MO\setminus M have average at least its overall average. Since a≥k−ma\ge k-m, d≤kd\le k, and m≤km\le k, this proves v^(P∖M)≥(1−m/k)v^(O∖M)\hat{v}(P\setminus M)\ge(1-m/k)\hat{v}(O\setminus M). Applying (4.1) to both sets yields v(P∖M)≥α(1−m/k)v(O∖M)v(P\setminus M)\ge\alpha(1-m/k)v(O\setminus M). This inequality also holds when d=0d=0, since its right-hand side is zero. Adding v(O∩M)v(O\cap M) and using 0≤α(1−m/k)≤10\le\alpha(1-m/k)\le1 gives v(B)≥α(1−m/k)v(O)=α(1−m/k)OPTv(B)\ge\alpha(1-m/k)v(O)=\alpha(1-m/k)\mathrm{OPT}, as claimed. □\square

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

gm(r)={0,r≤1,cr−1r−1r+m,r≥2,(13)g_m(r)= \begin{cases} 0, & r\le1,\\ c_{r-1}\dfrac{r-1}{r+m}, & r\ge2, \end{cases} \tag*{(13)}

where cqc_q is the fallback ratio in (2.2). The factor cr−1c_{r-1} accounts for the classical fallback, and (r−1)/(r+m)(r-1)/(r+m) accounts for the benchmark’s possible excess size.

Lemma 2. For the conditioning information H\mathcal{H} defined in § 3,

E[v(A)∣H]≥gm(r)v(B).(14)\mathbb{E}[v(A)\mid\mathcal{H}] \ge g_m(r)v(B). \tag*{(14)}

Consequently, E[v(A)]≥E[gm(r)]v(B)\mathbb{E}[v(A)]\ge\mathbb{E}[g_m(r)]v(B).

Proof. When r≤1r\le1, the right side is zero. Suppose r≥2r\ge2, and put q=r−1q=r-1. Recall that S=P∩{i:Ui<T}S=P\cap\{i:U_i<T\} is the set of candidates accepted before the first erroneous candidate arrives at time TT. All members of BB arriving before TT belong to P∖MP\setminus M, so they are in SS. The trigger is also accepted. Thus

C=B∖(S∪{J})⊆Z.(15)C=B\setminus(S\cup\{J\})\subseteq Z. \tag*{(15)}

Write b=∣P∩M∣b = |P \cap M| and c=∣O∩M∣c = |O \cap M|. Since ∣P∖M∣=k−b|P \setminus M| = k - b,

∣C∣=k−b−s+c−1{J∈O}=q+1+c−b−1{J∈O}≤q+m+1.|C| = k - b - s + c - \mathbf{1}_{\{J \in O\}} = q + 1 + c - b - \mathbf{1}_{\{J \in O\}} \le q + m + 1.

The largest qq values of CC, or all of CC if it is smaller, therefore give

OPT⁡q(Z)≥qq+m+1v(C).(16)\operatorname{OPT}_{q}(Z) \ge\frac{q}{q+m+1}v(C). \tag*{(16)}

The fallback contributes at least gm(r)v(C)g_m(r)v(C) conditionally on H\mathcal{H}. The already accepted candidates contribute v(S)+vJ≥v(B∖C)v(S) + v_J \ge v(B \setminus C). Since 0≤gm(r)≤10 \le g_m(r) \le1,

E[v(A)∣H]≥v(B∖C)+gm(r)v(C)≥gm(r)v(B).\mathbb{E}[v(A) \mid\mathcal{H}] \ge v(B \setminus C) + g_m(r)v(C) \ge g_m(r)v(B).

Finally, BB is fixed before the arrival times are sampled, so v(B)v(B) can be taken outside the expectation. □\square

Lower bounding E[gm(r)]\mathbb{E}[g_m(r)]

Lemma 2 reduces the few-error analysis to bounding E[gm(r)]\mathbb{E}[g_m(r)]. We first compare rr 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 b=∣P∩M∣b = |P \cap M|. Conditional on p=1−Tp = 1 - T, all bb erroneous members of PP are still unprocessed just before TT. Each of its other k−bk-b members remains independently with probability pp. Hence

r∣p=db+Bin⁡(k−b,p).(17)r \mid p \overset{d}{=} b + \operatorname{Bin}(k-b,p). \tag*{(17)}

To obtain a simpler lower bound on rr, condition on pp and let B1,…,BkB_1,\ldots,B_k be independent Bernoulli random variables, each equal to 1 with probability pp. We can represent r=b+∑i=b+1kBir = b + \sum_{i=b+1}^{k} B_i and define X=∑i=1kBiX = \sum_{i=1}^{k} B_i. Since ∑i=1bBi≤b\sum_{i=1}^{b} B_i \le b, this construction ensures

r≥X,X∣p∼Bin⁡(k,p).(18)r \ge X, \qquad X \mid p \sim\operatorname{Bin}(k,p). \tag*{(18)}

Thus, conditional on pp, this capacity lower bound XX has a binomial distribution with kk trials and success probability pp.

Fujii and Yoshida [11] bound a reciprocal-capacity expectation by comparing it with the case m=1m = 1. We use the same reference case, make the comparison explicit through a coupling, and apply it directly to the clipped square-root loss.

Let VV be uniform on [0,1][0,1]. When m=1m = 1, the remaining-time fraction p=1−Tp = 1 - T is uniform, so we define the reference variable by X0∣V∼Bin⁡(k,V)X_0 \mid V \sim\operatorname{Bin}(k,V). Averaging over VV gives

P(X0=x)=∫01(kx)vx(1−v)k−x dv=1k+1,x=0,…,k.\mathbb{P}(X_0 = x) = \int_{0}^{1} \binom{k}{x}v^x(1-v)^{k-x}\,\mathrm{d}v = \frac{1}{k+1}, \qquad x = 0,\ldots,k.

Thus, although X0X_0 is binomial conditional on VV, its unconditional distribution is uniform on {0,…,k}\{0,\ldots,k\}.

For general m≥1m \ge1, retain p=1−Tp = 1 - T and define V:=pmV := p^m. Since P(p≤u)=um\mathbb{P}(p \le u) = u^m, the variable VV is uniform on [0,1][0,1], and p=V1/m≥Vp = V^{1/m} \ge V. To compare the two conditional binomial distributions XX and X0X_0, take auxiliary independent uniform random variables W1,…,WkW_1,\ldots,W_k, independent of pp, and set X=∑i=1k1{Wi≤V1/m}X=\sum_{i=1}^k\mathbf{1}\{W_i\le V^{1/m}\}, X0=∑i=1k1{Wi≤V}X_0=\sum_{i=1}^k\mathbf{1}\{W_i\le V\}. These variables have the required conditional binomial distributions. Since V1/m≥VV^{1/m}\ge V, every success counted by X0X_0 is also counted by XX, and hence X≥X0X\ge X_0. Consequently, for every nonincreasing function f:{0,…,k}→Rf:\{0,\ldots,k\}\to\mathbb{R}, we have f(X)≤f(X0)f(X)\le f(X_0) and therefore

E[f(X)]≤E[f(X0)]=1k+1∑x=0kf(x).(19)\mathbb{E}[f(X)]\le\mathbb{E}[f(X_0)]=\frac{1}{k+1}\sum_{x=0}^{k}f(x). \tag*{(19)}

We now derive a lower bound on E[gm(r)]\mathbb{E}[g_m(r)].

Lemma 3. For 1≤m≤k1\le m\le\sqrt{k},

E[gm(r)]≥1−15k.(20)\mathbb{E}[g_m(r)]\ge1-\frac{15}{\sqrt{k}}. \tag*{(20)}

Proof. There are two losses in (13): the fraction of the remaining benchmark that fits, and the classical fallback’s approximation loss. Define

h(x)={1,x=0,1,min⁡{1,5/x−1},x≥2.(21)h(x)= \begin{cases} 1, & x=0,1,\\ \min\{1,5/\sqrt{x-1}\}, & x\ge2. \end{cases} \tag*{(21)}

Using r≥Xr\ge X from (18),

1−gm(r)≤m+1X+m+h(X).(22)1-g_m(r)\le\frac{m+1}{X+m}+h(X). \tag*{(22)}

Indeed, for X≥2X\ge2, write gm(r)=(1−u)(1−w)g_m(r)=(1-u)(1-w) with u=(m+1)/(r+m)u=(m+1)/(r+m) and w=min⁡{1,5/r−1}w=\min\{1,5/\sqrt{r-1}\}. Then 1−gm(r)≤u+w1-g_m(r)\le u+w, and r≥Xr\ge X gives (22). For X≤1X\le1, the right side is at least one.

The function hh is nonincreasing. Applying (19) directly to this square-root penalty yields

E[h(X)]≤2+5∑j=1k−1j−1/2k+1≤11k.(23)\mathbb{E}[h(X)]\le\frac{2+5\sum_{j=1}^{k-1}j^{-1/2}}{k+1}\le\frac{11}{\sqrt{k}}. \tag*{(23)}

The last inequality uses ∑j=1k−1j−1/2≤2k−1\sum_{j=1}^{k-1}j^{-1/2}\le2\sqrt{k-1}, 2/(k+1)≤1/k2/(k+1)\le1/\sqrt{k}, and k−1/(k+1)≤1/k\sqrt{k-1}/(k+1)\le1/\sqrt{k}, with an empty sum when k=1k=1. We bound the capacity-excess term separately for m=1m=1 and 2≤m≤k2\le m\le\sqrt{k}. When m=1m=1, XX is uniform on {0,…,k}\{0,\ldots,k\}, so

E[2X+1]=2k+1∑x=0k1x+1=2Hk+1k+1≤4k,\mathbb{E}\left[\frac{2}{X+1}\right]=\frac{2}{k+1}\sum_{x=0}^{k}\frac{1}{x+1}=\frac{2H_{k+1}}{k+1}\le\frac{4}{\sqrt{k}},

where Hℓ=∑j=1ℓ1/jH_\ell=\sum_{j=1}^{\ell}1/j and we used Hℓ≤2ℓH_\ell\le2\sqrt{\ell}.

For m≥2m\ge2, we use the classical binomial reciprocal identity [7], following Fujii and Yoshida [11 Lemma 4]. Since X∣p∼Bin⁡(k,p)X\mid p\sim\operatorname{Bin}(k,p),

E[1X+1∣p]=1−(1−p)k+1(k+1)p≤1(k+1)p.\mathbb{E}\left[\left.\frac{1}{X+1}\right|p\right]=\frac{1-(1-p)^{k+1}}{(k+1)p}\le\frac{1}{(k+1)p}.

Moreover, p=1−Tp = 1 - T has density mpm−1m p^{m-1}, and hence E[1p]=∫01mpm−2 dp=mm−1\mathbb{E}\left[\frac{1}{p}\right] = \int_0^1 m p^{m-2}\,dp = \frac{m}{m-1}.

Using X+m≥X+1X + m \ge X + 1 and averaging over pp, we obtain

E[m+1X+m]≤(m+1)E[1X+1]≤m+1k+1E[1p]=m(m+1)(k+1)(m−1)≤3mk+1≤3k≤4k.(24)\begin{aligned} \mathbb{E}\left[\frac{m+1}{X+m}\right] &\le(m+1)\mathbb{E}\left[\frac{1}{X+1}\right] \le\frac{m+1}{k+1}\mathbb{E}\left[\frac{1}{p}\right] = \frac{m(m+1)}{(k+1)(m-1)} \\ &\le\frac{3m}{k+1} \le\frac{3}{\sqrt{k}} \le\frac{4}{\sqrt{k}}. \tag*{(24)} \end{aligned}

Here (m+1)/(m−1)≤3(m+1)/(m-1) \le3 for m≥2m \ge2, and m≤km \le\sqrt{k}. Combining (22)–(24) proves the lemma.

Combining the few-error bounds

Corollary 1. If 1≤m≤k1 \le m \le\sqrt{k}, then E[v(A)]≥(1−2θ−16k)OPT⁡\mathbb{E}[v(A)] \ge\left(1 - 2\theta- \frac{16}{\sqrt{k}}\right)\operatorname{OPT}.

Proof. If 1−2θ−16/k≤01 - 2\theta- 16/\sqrt{k} \le0, the claim follows from nonnegativity. Otherwise, 1−15/k>01 - 15/\sqrt{k} > 0. Lemmas 2 and 3 give E[v(A)]≥E[gm(r)]v(B)≥(1−15k)v(B)\mathbb{E}[v(A)] \ge\mathbb{E}[g_m(r)]v(B) \ge\left(1 - \frac{15}{\sqrt{k}}\right)v(B). Applying Lemma 1, we obtain

E[v(A)]≥(1−15k)1−θ1+θ(1−mk)OPT⁡≥(1−15k−2θ1+θ−mk)OPT⁡≥(1−2θ−16k)OPT⁡.(25)\begin{aligned} \mathbb{E}[v(A)] \ge\left(1-\frac{15}{\sqrt{k}}\right)\frac{1-\theta}{1+\theta}\left(1-\frac{m}{k}\right)\operatorname{OPT} \\ &\ge\left(1-\frac{15}{\sqrt{k}}-\frac{2\theta}{1+\theta}-\frac{m}{k}\right)\operatorname{OPT} \\ &\ge\left(1-2\theta-\frac{16}{\sqrt{k}}\right)\operatorname{OPT}. \tag*{(25)} \end{aligned}

The second inequality uses (1−a)(1−b)(1−c)≥1−a−b−c(1-a)(1-b)(1-c) \ge1-a-b-c for a,b,c∈[0,1]a,b,c \in[0,1]. The last inequality follows from 2θ/(1+θ)≤2θ2\theta/(1+\theta) \le2\theta and m/k≤1/km/k \le1/\sqrt{k}.

Many erroneous candidates: m>km > \sqrt{k}

We now consider the many-error case, m>km > \sqrt{k}, 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 m>km > \sqrt{k}, then

E[v(A)]≥(1−8k)OPT⁡.(26)\mathbb{E}[v(A)] \ge\left(1-\frac{8}{\sqrt{k}}\right)\operatorname{OPT}. \tag*{(26)}

Proof. Recall that Z={i:Ui>T}Z = \{i : U_i > T\} is the set of candidates arriving strictly after the trigger at time TT. Let W=v(O∩Z)W = v(O \cap Z). When r≥2r \ge2, the fallback has q=k−s−1q = k-s-1 slots.

Since ∣O∩Z∣≤k|O \cap Z| \le k, we have OPT⁡q(Z)≥(q/k)W\operatorname{OPT}_q(Z) \ge(q/k)W. Applying (2) conditionally on H\mathcal{H} gives

E[v(A)∣H]≥(qk−5qk)W=W−(s+1k+5qk)W≥W−(s+1k+5k)OPT⁡,(27)\mathbb{E}[v(A)\mid\mathcal{H}] \ge\left(\frac{q}{k}-\frac{5\sqrt{q}}{k}\right)W = W-\left(\frac{s+1}{k}+\frac{5\sqrt{q}}{k}\right)W \ge W-\left(\frac{s+1}{k}+\frac{5}{\sqrt{k}}\right)\operatorname{OPT}, \tag*{(27)}

using W≤OPT⁡W \le\operatorname{OPT} and q≤kq \le k. For r≤1r \le1, we have s+1≥ks+1 \ge k, so the final right-hand side is nonpositive and the same bound follows from nonnegativity.

A candidate in O∖MO \setminus M is absent from ZZ with probability 1/(m+1)1/(m+1); a candidate in O∩MO \cap M is absent precisely when it is the trigger, with probability 1/m1/m. Similarly, each member of P∖MP \setminus M precedes the trigger with probability 1/(m+1)1/(m+1). Thus

E[W]=mm+1v(O∖M)+(1−1m)v(O∩M)≥(1−1m)OPT⁡,(28)\mathbb{E}[W] = \frac{m}{m+1}v(O \setminus M)+\left(1-\frac{1}{m}\right)v(O \cap M) \ge\left(1-\frac{1}{m}\right)\operatorname{OPT}, \tag*{(28)}
E[s]=∣P∖M∣m+1≤km+1.(29)\mathbb{E}[s] = \frac{|P \setminus M|}{m+1} \le\frac{k}{m+1}. \tag*{(29)}

Taking expectations in (27) gives

E[v(A)]OPT⁡≥1−1m−1m+1−1k−5k≥1−8k,\frac{\mathbb{E}[v(A)]}{\operatorname{OPT}} \ge1-\frac{1}{m}-\frac{1}{m+1}-\frac{1}{k}-\frac{5}{\sqrt{k}} \ge1-\frac{8}{\sqrt{k}},

using m>km>\sqrt{k}. □\square

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 ε≤θ\varepsilon\le\theta and the robustness bound when ε>θ\varepsilon> \theta to establish Theorem 1.

Proof of Theorem 2

Proof (Proof of Theorem 2). If m=0m=0, equation (7) gives the stronger bound E[v(A)]≥(1−2θ)OPT⁡\mathbb{E}[v(A)] \ge(1-2\theta)\operatorname{OPT}. If 1≤m≤k1 \le m \le\sqrt{k}, the result follows from Corollary 1. If m>km>\sqrt{k}, Lemma 4 gives

E[v(A)]≥(1−8k)OPT⁡≥(1−2θ−16k)OPT⁡.\mathbb{E}[v(A)] \ge\left(1-\frac{8}{\sqrt{k}}\right)\operatorname{OPT} \ge\left(1-2\theta-\frac{16}{\sqrt{k}}\right)\operatorname{OPT}.

These cases exhaust all possible values of mm. □\square

Proof of Theorem 1

When all prediction errors are at most θ\theta, the algorithm never leaves the predicted shortlist. The following bound is the consistency argument from [11].

Lemma 5. [11 Lemma 1] If ε≤θ<1\varepsilon\le\theta< 1, then A=PA = P and

v(A)≥1−ε1+εOPT⁡≥(1−2ε)OPT⁡.(30)v(A) \ge\frac{1-\varepsilon}{1+\varepsilon}\operatorname{OPT} \ge(1-2\varepsilon)\operatorname{OPT}. \tag*{(30)}

Now we are ready to prove Theorem 1.

Proof (Proof of Theorem 1). Recall that θ=min⁡{1/2,8/k}\theta= \min\{1/2, 8/\sqrt{k}\}. We first prove the bound without clipping it at zero.

Suppose k≥256k \ge256, so θ=8/k\theta= 8/\sqrt{k}. Theorem 2 gives, for arbitrary predictions,

E[v(A)]≥(1−2θ−16k)OPT⁡=(1−32k)OPT⁡.\mathbb{E}[v(A)] \ge\left(1-2\theta-\frac{16}{\sqrt{k}}\right)\operatorname{OPT} = \left(1-\frac{32}{\sqrt{k}}\right)\operatorname{OPT}.

If ε>θ\varepsilon> \theta, then 4ε>32/k4\varepsilon> 32/\sqrt{k}, so this is exactly the desired bound

E[v(A)]≥(1−min⁡{32k,4ε})OPT⁡.\mathbb{E}[v(A)] \ge\left(1-\min\left\{\frac{32}{\sqrt{k}},4\varepsilon\right\}\right)\operatorname{OPT}.

If ε≤θ\varepsilon\le\theta, no error exceeds the switching threshold, and Lemma 5 also gives E[v(A)]≥(1−2ε)OPT⁡\mathbb{E}[v(A)] \ge(1-2\varepsilon)\operatorname{OPT}. Combining the two guarantees yields

E[v(A)]≥max⁡{1−32k,1−2ε}OPT⁡≥(1−min⁡{32k,4ε})OPT⁡.\mathbb{E}[v(A)] \ge\max\left\{1-\frac{32}{\sqrt{k}},1-2\varepsilon\right\}\operatorname{OPT} \ge\left(1-\min\left\{\frac{32}{\sqrt{k}},4\varepsilon\right\}\right)\operatorname{OPT}.

Now suppose k<256k < 256, so θ=1/2\theta= 1/2 and 32/k>232/\sqrt{k} > 2. If ε≤1/2\varepsilon\le1/2, then min⁡{32/k,4ε}=4ε\min\{32/\sqrt{k},4\varepsilon\} = 4\varepsilon. Lemma 5 therefore gives

E[v(A)]≥(1−2ε)OPT⁡≥(1−4ε)OPT⁡.\mathbb{E}[v(A)] \ge(1-2\varepsilon)\operatorname{OPT} \ge(1-4\varepsilon)\operatorname{OPT}.

If ε>1/2\varepsilon> 1/2, both 32/k32/\sqrt{k} and 4ε4\varepsilon exceed two, so the desired bound before clipping is negative and follows from v(A)≥0v(A) \ge0.

Finally, nonnegativity allows us to replace the bound by its maximum with zero, proving (2.4), including when ε=∞\varepsilon= \infty. With exact predictions, no switch occurs and PP is a true top-kk set, so v(A)=OPT⁡v(A) = \operatorname{OPT} for every arrival order. □\square

Extension: Measuring prediction error at the selection boundary

The maximum prediction error ε\varepsilon can be large even when the predicted top-kk set PP is optimal. For example, if a candidate in PP 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-kk set PP with its predicted cutoff τ=min⁡i∈Pv^i\tau= \min_{i\in P}\hat{v}_i, while measuring error inside PP 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 τ\tau, and an excluded candidate is a concern only if its true value exceeds τ\tau.

Cutoff error and switching rule. Define the cutoff error by

η=inf⁡{δ≥0:τ≤(1+δ)vifor every i∈P,τ≥(1−δ)vifor every i∉P},(31)\eta=\inf\left\{\delta\ge0:\begin{array}{ll} \tau\le(1+\delta)v_i & \text{for every }i\in P,\\ \tau\ge(1-\delta)v_i & \text{for every }i\notin P \end{array}\right\}, \tag*{(31)}

with inf⁡∅=+∞\inf\varnothing=+\infty. In particular, η=0\eta=0 precisely when every shortlisted candidate has value at least τ\tau and every excluded candidate has value at most τ\tau. In that case, PP is a true top-kk set. The cutoff error satisfies η≤ε\eta\le\varepsilon: for i∈Pi\in P we have τ≤v^i\tau\le\widehat{v}_i, while for i∉Pi\notin P we have τ≥v^i\tau\ge\widehat{v}_i. 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 ii, switch precisely when

(i∈P and τ>(1+θ)vi)or(i∉P and τ<(1−θ)vi).(32)(i\in P\text{ and }\tau>(1+\theta)v_i)\quad\text{or}\quad(i\notin P\text{ and }\tau<(1-\theta)v_i). \tag*{(32)}

As before, the algorithm accepts the trigger if a slot remains and runs Kleinberg’s algorithm on subsequent arrivals with the remaining capacity. Once PP and τ\tau 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

E[v(A)]≥max⁡{0,1−min⁡{32k,4η}}OPT⁡.\mathbb{E}[v(A)]\ge\max\left\{0,1-\min\left\{\frac{32}{\sqrt{k}},4\eta\right\}\right\}\operatorname{OPT}.

If η≤θ\eta\le\theta, no switch occurs and v(A)≥(1−η)OPT⁡/(1+η)v(A)\ge(1-\eta)\operatorname{OPT}/(1+\eta). In particular, if η=0\eta=0, the algorithm obtains OPT⁡\operatorname{OPT} on every arrival order.

Proof. Fix 0≤θ<10\le\theta<1, let MM be the set of candidates satisfying (7.2), and write m=∣M∣m=|M| and α=(1−θ)/(1+θ)\alpha=(1-\theta)/(1+\theta). The key observation is that any nontriggering shortlisted candidate i∈P∖Mi\in P\setminus M and any nontriggering excluded candidate j∉P∪Mj\notin P\cup M satisfy

vi≥τ1+θ≥αvj.(33)v_i\ge\frac{\tau}{1+\theta}\ge\alpha v_j. \tag*{(33)}

This pairwise value comparison replaces the bounds (1−θ)vi≤v^i≤(1+θ)vi(1-\theta)v_i\le\widehat{v}_i\le(1+\theta)v_i used in the proof of Lemma 1.

To see this, suppose m≤km\le\sqrt{k}. Let G=P∖MG=P\setminus M, H=O∖MH=O\setminus M, and let H′H' consist of the min⁡{∣G∣,∣H∣}\min\{|G|,|H|\} highest-value candidates in HH. Since ∣G∣≥k−m|G|\ge k-m and ∣H∣≤k|H|\le k, we have v(H′)≥(1−m/k)v(H)v(H')\ge(1-m/k)v(H). Match each member of H′∖GH'\setminus G to a distinct member of G∖H′G\setminus H'; this is possible because ∣H′∣≤∣G∣|H'|\le|G|. Each matched member of GG has value at least α\alpha times that of its partner by (7.3). Members of G∩H′G\cap H' contribute their own value. Hence

v(G)≥αv(H′)≥α(1−m/k)v(H).v(G)\ge\alpha v(H')\ge\alpha(1-m/k)v(H).

Adding v(O∩M)v(O\cap M) recovers the bound of Lemma 1 for B=G∪(O∩M)B=G\cup(O\cap M).

The remaining analysis uses only that MM is fixed before arrivals and that the algorithm follows PP until the first member of MM arrives or capacity is exhausted. Thus the conditional completion, capacity averaging, and many-error bounds apply unchanged. For m=0m=0, the comparison above gives v(P)≥αOPT⁡v(P)\ge\alpha\operatorname{OPT} directly. This proves Theorem 2 for the modified rule, regardless of η\eta.

Finally, if η≤θ\eta\le\theta, the strict trigger never fires. Applying the same matching argument at threshold η\eta with M=∅M=\varnothing gives v(A)=v(P)≥(1−η)OPT⁡/(1+η)v(A)=v(P)\ge(1-\eta)\operatorname{OPT}/(1+\eta). 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 1−O(k−1/2)1-O(k^{-1/2}). His algorithm supplies our fallback after a prediction error is detected. Babaioff et al. [3] study knapsack secretary selection, including a 1/e1/e 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 O(log⁡k)O(\log k) 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 O(min⁡{log⁡k/k,ε})O(\min\{\log k/\sqrt{k},\varepsilon\}); 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 0.40.4 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-kk sum.

Single-choice guarantees and arrival control. Karisani et al. [13] improve single-choice random-order robustness from 0.2150.215 to 0.2210.221, while retaining the accuracy term (1−ε)/(1+ε)(1-\varepsilon)/(1+\varepsilon). They obtain 0.2620.262 robustness when predictions can be used to choose the arrival order. Yiming [18] studies prediction-based ordering, with 0.2290.229 robustness and improved fairness bounds in that setting. Choo and Ling [8] establish a limiting 1/31/3 upper bound for perfectly consistent single-choice algorithms. These works study single-choice robustness; we study how robustness improves with kk 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 OPT−4kΔ\mathrm{OPT}-4k\Delta, where Δ=max⁡i∣vi−v~i∣\Delta=\max_i\lvert v_i-\tilde{v}_i\rvert, 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-kk 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. [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. [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. [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. [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. [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. [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. [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. [8]Choo, D., Ling, C.K.: A short note about the learning-augmented secretary problem (2024), https://arxiv.org/abs/2410.06583
  9. [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. [10]Dynkin, E.B.: The optimum choice of the instant for stopping a Markov process. Soviet Mathematics Doklady 4, 627–629 (1963)
  11. [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. [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. [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. [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. [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. [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. [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. [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

Paper details

vlnc:W_ayzyd4ug
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT

View statement
Looking for related papers…
Contents