The Secretary Problem with Predictions and a Chosen Order

Fujii and Yoshida restrict their attention to the classic setting in which candidates arrive in a uniform random order. We call this setting the Random Order Secretary Problem (ROSP). However, when predictions of candidate values are available up front, it is natural to use them to modify the arrival order of the candidates. For example, in applications to hiring, the interview order is typically set by the decision-maker and may be chosen based on the available predictions. To capture this setting, we introduce the Chosen Order Secretary Problem (COSP), in which the decision-maker has full control of the candidate arrival sequence. COSP is analogous to existing chosen order settings for prophet inequalities, in which a distribution over each candidate’s value is known up front [43, 21, 62]. However, like the classic secretary problem, COSP is fundamentally worst-case, with no stochastic assumptions made on the inputs.

We design a simple algorithm for COSP inspired by the approach of Fujii and Yoshida [36]. Intuitively, one might imagine that interviewing candidates in e.g., decreasing order of their predicted values, would be optimal. However, it is easy to find simple worst-case instances that defeat these related strategies. Instead, our algorithm only uses the power of COSP in a limited way: letting $\widehat{i}\in [n]$ be the candidate with the highest predicted value, we place $\widehat{i}$ at a fixed position in the arrival sequence, and randomize the order of all other candidates. We optimize the position of $\widehat{i}$ to achieve maximum competitive ratio.

After fixing the interview order, our algorithm proceeds similarly to that of Fujii and Yoshi. It initially operates in a prediction-trusting mode, waiting to hire $\widehat{i}$, the candidate with the highest predicted value. If it encounters a candidate whose true value significantly deviates from its prediction (i.e., exceeds a specified error threshold), it transitions to Dynkin’s classical threshold-based algorithm [32]. This algorithm ignores a fixed fraction of candidates, and then hires the first candidate (if any) it sees that is better than all the ignored candidates. Critically, we modify the approach of Fujii and Yoshida by not always hiring $\widehat{i}$ if it is meant to be hired in the Dynkin mode of the algorithm. We introduce two parameters, $\gamma$ and $\delta$, that determine the probability of hiring $\widehat{i}$ in different cases, and by tuning these parameters, are able to achieve a larger competitive ratio.

We show that our algorithm is robust and consistent, achieving a competitive ratio of at least

recalling that $ϵ$ is the largest multiplicative prediction error. As in the algorithm of Fujii and Yoshida, our method does not require $ϵ$ as input. When $ϵ\to 0$, the competitive ratio approaches 1, and when $ϵ$ is large, it remains bounded below by $0.262$. Importantly, our COSP result surpasses the $0.25$ upper bound that arises in the analysis of the Fujii–Yoshida algorithm in the random-order model.¹¹1Fujii and Yoshida prove a $0.25$ upper bound for the random order setting where the decision-maker only sees the order of candidate arrivals (not their exact random arrival times), and where the decision algorithm is deterministic. By leveraging arrival-order control and randomization, our algorithm exceeds this barrier. See Section Section 5 for discussion.

We show that our approach also applies to the classic ROSP setting, where instead of optimizing the arrival time of the best predicted candidate $\widehat{i}$, we simply average over a uniform random choice of this time. In this case, by optimizing the parameters $\gamma$ and $\delta$, we can show that our algorithm achieves a competitive ratio of at least

improving on the previous bound of $\max \{0.215,\frac{1-ϵ}{1+ϵ}\}$ of Fujii and Yoshida [36]. As in the COSP setting, the algorithm does not require $ϵ$ as input. Our worst-case competitive ratio gets closer to an upper bound of $0.33$, which [25] proves for any consistent algorithm solving ROSP. However, a substantial gap between the best known upper and lower bounds remains.

Interestingly, in the analysis by Fujii and Yoshida, the arrival position of the top-predicted candidate $\widehat{i}$ has a significant impact on the competitive ratio. This observation motivates our focus on COSP, and on strategically fixing the arrival time of $\widehat{i}$ in particular. To illustrate this, suppose we fix $\widehat{i}$’s arrival time to $\beta \approx 0$ and keep all other arrival times uniformly random. The adversary can set all predictions correctly except for the true best candidate $i^{\ast }$, which is underestimated. With probability $\beta$, this candidate arrives before $\widehat{i}$, triggers a switch to secretary mode, and is skipped. With probability $1-\beta$, the algorithm hires $\widehat{i}$ before ever seeing $i^{\ast }$. In either case, the competitive ratio approaches zero. On the other hand, if $\beta \approx 1$, the adversary may overestimate $\widehat{i}$, causing the algorithm to skip all earlier candidates in favor of $\widehat{i}$, which results in success only with probability $1-\beta$ – again close to zero. Therefore, setting $\beta =0$ or $\beta =1$ is provably suboptimal, and we instead optimize over $\beta$ to find a value that balances these trade-offs and maximizes the competitive ratio. We note that placing a distribution over the arrival time $\beta$ of $\widehat{i}$, rather than fixing it deterministically, may further improve performance. However, we leave this possibility for future work. We conjecture that controlling the arrival times of candidates other than $\widehat{i}$ (rather than simply randomizing them) cannot significantly improve our bounds – however, we again leave investigating this question for future work.

Unfortunately, simply optimizing the arrival time of $\widehat{i}$ and applying the algorithm of Fujii and Yoshida [36] directly can fail. Recall that Dynkin’s worst-case algorithm ignores all candidates before some threshold time $\tau$, and then hires the first candidate that arrives after $\tau$ and is better than all preceding candidates. If we set and the top predicted candidate $\widehat{i}$ is in fact the true best candidate, but its prediction deviates significantly from its value, the algorithm switches to secretary mode upon its arrival and rejects $\widehat{i}$ since it arrives before $\tau$. This can result in a near zero competitive ratio. Conversely, if we fix $\beta >\tau$, consider a scenario with no deviation between the predictions and the true values, except that $\widehat{i}$ is predicted to be the best candidate but is actually the second-best candidate (and by a wide margin). If the true best candidate $i^{\ast }$ arrives before $\beta$, it will be ignored since the algorithm remains in prediction mode. If it arrives after $\beta$, the algorithm will have already selected $\widehat{i}$ as it would be the best candidate seen after $\tau$ and after switching to secretary mode. Again, we have a competitive ratio of near zero.

The handle the above issues, we set $\beta >\tau$, but modify the algorithm to not always hire $\widehat{i}$ when it is the first mistake and the best candidate observed so far. Instead, we introduce a parameter $\gamma$ that specifies the probability of hiring $\widehat{i}$ in this case. This change ensures that the algorithm retains flexibility in handling situations where blindly trusting $\widehat{i}$ could lead to poor outcomes. Optimizing $\gamma$ allows us to avoid deterministic failure while still preserving good performance in other cases.

We introduce a second parameter $\delta$ to handle the case where $\widehat{i}$ is not the first observed mistake. It does not make sense to use the same hiring probability $\gamma$ in this setting, as the context is different: the algorithm has already seen one or more mistakes and switched to secretary mode before seeing $\widehat{i}$. The likelihood that $\widehat{i}$ is truly optimal may be lower or higher than the case when it is the first mistake , so we allow a separate hiring probability $\delta$ This additional degree of freedom enables us to optimize the algorithm’s behavior even further.

As in the work of Fujii and Yoshida, a key technical challenge is to analyze the competitive ratio against all possible adversarial inputs. This requires accounting for every configuration of the true best candidate $i^{\ast }$, the top-predicted candidate $\widehat{i}$, and the locations of all large-deviation candidates. As in their analysis, this leads to a detailed case decomposition. Following their notation, let $M$ be the set of large-deviation candidates, and let $m=|M|$. We further refine the structure of the high-deviation set $M$ by comparing the true values of its members to the true value of the best–predicted candidate $\widehat{i}$. Specifically, we define

so $m_2$ counts the number of “mistakes” whose true value is smaller than the true value of $\widehat{i}$. Although both quantities are well defined, only $m_2$ plays a role in our competitive-ratio bounds. In addition, we define

which is the number of candidates whose true value exceeds that of the best–predicted candidate $\widehat{i}$. The parameter $k$ captures how many truly better candidates the adversary places relative to $\widehat{i}$, and therefore directly influences the worst-case behavior of the algorithm in prediction mode.

These parameters allow us to partition the analysis into fine-grained subcases, each capturing a distinct adversarial structure. We then optimize over $\beta$, $\gamma$, and $\delta$ to obtain the worst-case competitive ratio.

Despite the added generality, the algorithm retains a simple structure amenable to analysis. By carefully organizing the cases based on the parameters, we are able to compute the worst-case competitive ratio numerically. Through this analysis, we obtain a provable lower bound of $\max \{0.262,\frac{1-ϵ}{1+ϵ}\}$ for COSP, demonstrating the benefit of tuning $\beta$, $\gamma$, and $\delta$.

In the COSP setting, for each fixed value of $\beta$, we evaluate the competitive ratio across all adversarial configurations and then optimize the parameters $\gamma$ and $\delta$ for that fixed $\beta$. We then optimize over $\beta$ to obtain the final COSP bound.

In the ROSP setting, however, the arrival time of $\widehat{i}$ is itself a uniform random variable in $[0,1]$, and cannot be chosen by the algorithm. Accordingly, the analysis must first take the expectation of the competitive ratio over $\beta \sim \mathrm{Unif}[0,1]$. We then optimize the parameters $\gamma$ and $\delta$ with respect to this new competitive ratio objective. This yields a lower bound of

slightly improving on the prior bound of [36].

One natural question is whether introducing additional parameters – for example, tuning the algorithm’s behavior when encountering the second- or third-highest predicted candidates – could further improve the robustness. Our analysis, as well as the structure of [36], suggests that this is unlikely: in all adversarial instances that determine the worst-case competitive ratio, the only critical decision point is when the algorithm reaches $\widehat{i}$ or first mistake(deviated prediction) while still following the classical secretary rule. Lower-predicted candidates never influence these worst-case configurations in a meaningful way unless they are mistakes (deviated predictions). By contrast, in extensions of the secretary problem where the goal is to select the top $k>1$ individuals or where multiple high-valued candidates may be accepted, controlling the arrival times of several top-predicted candidates could indeed be beneficial. Developing such multi-candidate scheduling strategies is an interesting direction for future work.

The classical secretary problem, popularized by Gardner [37] and others [32, 39, 54, 34, 55, 46, 27, 67, 28, 9], has inspired a broad and influential line of work in online algorithms, economics, and decision theory. Numerous extensions have been studied, including multiple-choice variants [49], matroid and knapsack constraints [11], online matching and graphic/transversal matroids [50], submodular objectives under cardinality and packing constraints [48], and structured feasibility systems such as packing integer programs [8]. We refer the reader to the survey by Gupta and Singla [42] for a broader overview of results in random-order models.

Recent work incorporates predictions into the secretary problem to enable improved performance. In the model that we adopt, each candidate comes with a predicted value ${\widehat{v}}_i$ estimating their true value $v_i$, as in [36, 25]. Other forms of predictive feedback include binary comparisons [15], probabilistic signals about candidate quality [61, 31], single-shot predictions of the best candidate [6], and predictions of the value difference between the best and the k-th best candidate [19]. Some work has studied algorithms that ensure fairness by guaranteeing the best candidate is accepted with constant probability, even under biased predictions [12]. Additionally, Amanatidis et al. [4] study value maximization with predictions in an online budget-feasible mechanism design setting, using techniques related to the secretary problem.

Prophet inequalities are a classical model in optimal stopping theory that can be seen as a stochastic version of the secretary problem. A decision-maker observes a sequence of values drawn from known distributions and aims to compete with a benchmark that selects the maximum in hindsight. The classical result guarantees a $1/2$ competitive ratio [51, 69], which has inspired a rich body of work in theoretical computer science and economics; see surveys such as [44, 56, 26]. Numerous variants have been studied, including the adversarial order model [51], the random order (prophet secretary) model [33], and the order-selection (free-order) model [43]. This model is especially related to our Chosen Order Secretary Problem (COSP), in which the arrival order is determined by predicted candidate values. Relevant works in the order-selection model include [23, 16, 62, 21]. Intuitively, prophet inequalities capture similar scenarios in which the decision-maker has in advance information about candidate values; however, they operate under stochastic assumptions (values drawn from known distributions), whereas our setting is fully worst-case, with no distributional assumptions. Interestingly, until recently, it was unclear whether the order-selection and random-arrival models for profit inequalities differed in their achievable competitive ratios. A separation has now been established for prophet inequalities [21], but in our setting, the relationship remains open: the best upper bound for the random-arrival variant (ROSP) currently exceeds the best known competitive ratio for order selection (COSP).

A growing literature studies learning-augmented online algorithms in which predictions guide online decisions without compromising worst-case robustness. Notable examples include caching [57, 66, 73], ski rental [63, 41, 74, 30], online scheduling [52], and metrical task systems [5]. Learning-augmented approaches have also been applied in online primal-dual methods [14], speed scaling [13], online bidding [1], and auctions [40]. We refer the reader to surveys such as [60] for comprehensive overviews. Moreover, learning-augmented approaches have also been applied to online purchasing-type problems with prediction, such as one-way trading, online conversion [2, 72, 53], and online knapsack problems with prediction [45, 38, 17, 29]. These problems often share structural similarities with secretary problems – e.g., online knapsack with unit-size items and unit capacity resembles the secretary problem under random arrival.

Following the case-based analysis of Fujii and Yoshida [36], we divide the proof into seven cases, depending on the structure of the high-deviation set $M$, which contains all candidates whose predictions deviate from their actual values by more than the threshold $\theta$ used to switch from Prediction to Secretary mode in Line 5 of Algorithm 1 . Formally, we define this set as:

Our cases will consider whether the candidate with the highest predicted value $\widehat{i}$ and/or the candidate with the highest true value $i^{\ast }$ belong to $M$. Also, we define $i_M$ as the first candidate’s index to be seen that falls in $M$ and we denote its arrival time as $t_M$. We also let $k=\left|\{i\in [n]\mid v_i>v_{\widehat{i}}\}\right|$ denote the number of candidates with true value greater than $\widehat{i}$, and let denote the number of candidates in set $M$ with true value less than $\widehat{i}$.

Throughout the analysis, we discuss the regime where the fixed arrival time $\beta$ of $\widehat{i}$ satisfies $\beta >\tau$, as this aligns with parameters obtained in our optimization over parameters $\tau ,\beta ,\gamma ,\delta$ ( Theorem 1). This focus simplifies the presentation, but both conditions $\beta >\tau$ and are fully analyzed in the next section to establish guarantees across all parameter choices. We denote the worst-case competitive ratio achieved in each case $j\in \{0,1,\mathrm{\dots },6\}$ by $C_j(\cdot )$ respect to any input set by the adversary, where $C_j(\cdot )$ is a function of parameters set by the adversary (i.e., $m$, $k$, $v_i$, and ${\widehat{v}}_i$). The case ordering follows the structure introduced in [36].

We will formally verify that our algorithm achieves a competitive ratio of at least $\max \{0.262,\frac{1-ϵ}{1+ϵ}\}$ across all cases. For clarity of presentation, we defer the technical lemmas used in the analysis to the appendix, while the main text focuses on the case-by-case argument structure.

To organize the argument, we present each of the seven cases as a separate part, analyzing the conditions under which the algorithm hires a candidate and deriving a lower bound on the competitive ratio in each scenario.

In this case, all predictions fall within the acceptable error threshold (i.e., ), so the high-deviation set $M$ is empty, and the algorithm remains in prediction mode throughout.

This implies that the maximum multiplicative prediction error satisfies $ϵ\le \theta$, and by the Multiplicative Error Guarantee (Equation (1)), all predicted values remain within the $(1\pm ϵ)$ bound.

Since the algorithm selects $\widehat{i}=\arg {\max }_i{\widehat{v}}_i$, it follows that

and moreover,

Together, these inequalities imply a competitive ratio of at least $\frac{1-ϵ}{1+ϵ}$. Since $ϵ\le \theta =0.58$, we have

Thus, in this case the algorithm achieves a competitive ratio of $\frac{1-ϵ}{1+ϵ}$, which is at least $\max \{0.262,\frac{1-ϵ}{1+ϵ}\}$, as claimed, since $ϵ\le \theta$.

Here, the top predicted candidate $\widehat{i}$ is also the true optimum $i^{\ast }$, but it lies in the high-deviation set $M$. The algorithm switches to secretary mode upon encountering the first candidate in $M$, which may or may not be $i^{\ast }$ itself.

We analyze two subcases, depending on whether $i^{\ast }$ triggers the mode switch or not:
Case(1.1) $\beta =t_M$: That is, $i^{\ast }$ is the first candidate in $M$, and it arrives at time $\beta$. The probability of this subcase occurring is equal to the probability that all other candidates in $M$ arrive after $\beta$, which is ${(1-\beta )}^{m-1}$. Also, the probability of successfully selecting $i^{\ast }$ is $\gamma$ since $i^{\ast }$ is the first observed error. Thus, the contribution of subcase Case(1.1) to the competitive ratio of this case is $\gamma {(1-\beta )}^{m-1}$: the event that $i^{\ast }$ is the first observed member of $M$ with probability ${(1-\beta )}^{m-1}$, and conditioned on this event the algorithm selects it with probability $\gamma$ ( Algorithm 1, Line 11).
Case(1.2) $\beta \ne t_M$: Here, some other candidate in $M$ arrived before $\widehat{i}$, so we are already in Secretary mode by the time $i^{\ast }$ arrives at time $\beta >\tau$. The probability of this subcase happening is equal to $1-{(1-\beta )}^{m-1}$ which is at least one candidate in $M$ arrives before $\widehat{i}$. Now, assuming we are in this subcase, in order to reach $\widehat{i}$ (to accept it), the algorithm must not accept anyone before $\widehat{i}$. It is sufficient (but not necessary) that the best candidate in the interval $[0,\beta )$ came before $\tau$, as then no one would be hired before it. The probability of this scenario is $\tau /\beta$. Furthermore, the Algorithm accepts $\widehat{i}$ with probability $\delta$ according to Line 13 of Algorithm 1. It is worth mentioning that the arrival of the best candidate in $[0,\beta )$ before $\tau$ is independent of whether a candidate in $M$ arrives before $\widehat{i}$, since candidates in $M$ arriving before $\beta$ are also uniformly distributed in $[0,\beta )$.

Combining both subcases, the competitive ratio in Case 1 for any $m$ is lower-bounded by:

Under this condition, the top predicted candidate $\widehat{i}$ is also the true optimum $i^{\ast }$, and its prediction is accurate enough that it does not belong to the high-deviation set $M$. The algorithm may or may not have entered secretary mode before observing $i^{\ast }$, depending on whether another candidate in $M$ has been seen earlier.

To obtain a pessimistic lower bound in this case, we assume that $i^{\ast }\in M$, even though by the conditions of case 2 we know $i^{\ast }\notin M$. This assumption decreases the chance of hiring $i^{\ast }$. If the algorithm is already in secretary mode when it sees $i^{\ast }$, then whether or not $i^{\ast }\in M$ has no effect – the selection behavior and probabilities are the same (see Line 13 of Algorithm 1). However, if the algorithm is still in prediction mode when $i^{\ast }$ arrives, then: (1) If $i^{\ast }\notin M$, the algorithm selects it deterministically. (2) If $i^{\ast }\in M$, the algorithm does not select it immediately and instead switches to secretary mode, where it will only be selected with probability $\gamma \le 1$. Thus, the pessimistic assumption $i^{\ast }\in M$ reduces the chance of hiring $i^{\ast }$, and we conclude the result is always better than Case 1, presented above, with one extra candidate in $M$:

In this situation, both the top predicted candidate $\widehat{i}$ and the true optimum $i^{\ast }$ belong to the high-deviation set $M$. We lower bound this case by Case 4, where $\widehat{i}\ne i^{\ast }$, $\widehat{i}\in M$, and $\widehat{i}\notin M$. The only difference between the two cases is that here $i^{\ast }\in M$. We further analyze this case by considering two subcases depending on whether $t^{\ast }$ is greater than or less than $\beta$.
Case(3.1): If $t^{\ast }>\beta$, the algorithm is already in secretary mode when $i^{\ast }$ arrives because $\widehat{i}$ arrives at time $\beta$ is in set $M$, so whether or not $i^{\ast }\in M$ does not affect its eligibility for hiring. The algorithm selects $i^{\ast }$ if it is the best seen so far and no better candidate has already been selected in Line 16 of Algorithm 1.
Case(3.2): If , then for $i^{\ast }$ to be selected, the algorithm must already be in secretary mode at or before time $t^{\ast }$. When $i^{\ast }\in M$, it can itself trigger this mode switch. However, if $i^{\ast }\notin M$, it can only be selected if another candidate in $M$ appears earlier. Hence, in all scenarios, $i^{\ast }\notin M$ is selected with probability no greater than when $i^{\ast }\in M$.

Therefore, Case 3 is no harder than Case 4 with one fewer member in $M$ (because of removing $i^{\ast }$ from $M$ and thus decreasing its size by $1$), and we conclude that for a fixed $m$, the worst-case competitive ratios of the two cases satisfy the following relation:

Under this condition, the top predicted candidate $\widehat{i}$ belongs to the high-deviation set $M$, while the true optimum $i^{\ast }\notin M$ has a reliable prediction. Therefore, the algorithm never selects a candidate in prediction mode and switches to secretary mode upon encountering the first candidate $i\in M$. We analyze two main subcases based on the arrival time $t^{\ast }$ of $i^{\ast }$. The first subcase occurs when $t^{\ast }\in (\tau ,\beta )$, and the second when $t^{\ast }\in (\beta ,1]$. We further divide the second subcase into two parts: (i) the best candidate in $[0,t^{\ast })$ is not $\widehat{i}$, and (ii) the best candidate in $[0,t^{\ast })$ is $\widehat{i}$. Combining the analyses of all these subcases yields the overall competitive ratio for Case 4.
Case(4.1) When $t^{\ast }\in (\tau ,\beta )$: In this subcase, the algorithm can only consider $i^{\ast }$ if it has already switched to secretary mode by time $t^{\ast }$. This requires that at least one candidate from $M$ to have arrived before $t^{\ast }$, which occurs with probability $1-{(1-t^{\ast })}^{m-1}$, also, it is sufficient (but not necessary) that the best candidate in $[0,t^{\ast })$ arrives before $\tau$ as then no one would be hired before $i^{\ast }$, which happens with probability $\tau /t^{\ast }$. Similar to Case 1, these two probabilities are independent since any candidate in $M$ which comes before $t^{\ast }$ also uniformly arrives between $[0,t^{\ast })$. We obtain the bound:

(see full version for details) To calculate this integral, we get:

Case(4.2) When $t^{\ast }\in (\beta ,1]$: In this subcase, the algorithm has already seen $\widehat{i}\in M$, and we examine whether $i^{\ast }$ can still be observed and selected under different conditions. We further divide this case into two subcases:
Case(4.2.1) The best candidate in $[0,t^{\ast })$ is not $\widehat{i}$: This occurs with probability $1-{(1-t^{\ast })}^k$, where $k$ is the number of candidates whose true value exceeds that of $\widehat{i}$. For $i^{\ast }$ to be selected, it is sufficient that the best candidate in $[0,t^{\ast })$ arrives before $\tau$, which happens with probability $\tau /t^{\ast }$. Similar to previous cases, these two events are independent, since knowing that some candidate better than $\widehat{i}$ arrives before $t^{\ast }$ does not affect the fact that all arrivals before $t^{\ast }$ are uniformly distributed over $[0,t^{\ast })$. Thus, we obtain the following equation:

(see full version for details) to calculate the integral, we have:

Case(4.2.2) The best candidate in $[0,t^{\ast })$ is $\widehat{i}$: In this scenario, which occurs with probability ${(1-t^{\ast })}^k$, the algorithm must reach time $t^{\ast }$ without hiring $\widehat{i}$ in order for $i^{\ast }$ to be selected. This leads to two possible outcomes:
Case(4.2.2.1) A candidate in $M$ other than $\widehat{i}$ triggers the switch to secretary mode before $\beta$: This occurs with probability $1-{(1-\beta )}^{m_2}$, where $m_2$ is the number of candidates in $M$ whose values are less than that of $\widehat{i}$. We use $m_2$ here because all candidates in $M$ with values greater than $\widehat{i}$ must arrive after $t^{\ast }$, given that $\widehat{i}$ is assumed to be the best candidate in $[0,t^{\ast })$. It is further required that the best candidate in $[0,\beta )$ arrives before $\tau$, which happens with probability $\tau /\beta$. In this case, we do not select any candidate before seeing $\widehat{i}$, and when $\widehat{i}$ arrives, it must also not be hired, which occurs with probability $1-\delta$ (Line 13 of Algorithm 1). Since the event of having a candidate arrive before $\beta$ is independent of the fact that arrivals in $[0,\beta )$ are uniformly distributed, any best candidate in $[0,\beta )$ arrives uniformly at random. Considering statement Case(4.2.2) and multiplying these independent probabilities, we have:

Case(4.2.2.2) Candidate $\widehat{i}$ itself triggers the switch to secretary mode: This event occurs with probability ${(1-\beta )}^{m_2}$, and is not hired with probability $1-\gamma$. Therefore, incorporating the factor ${(1-t^{\ast })}^k$ from (4.2.2), we have:

Combining Equations (11) and (12) and (see full version for details) to solve the integrals, we have:

Combining Equations (8), (10), and (13) from the subcases, we obtain the total lower bound for this case:

In this case, the top predicted candidate $\widehat{i}$ is accurate and not in the high-deviation set $M$, while the true optimum $i^{\ast }\in M$. The algorithm switches to secretary mode upon observing the first candidate from $M$. We analyze the outcome based on the arrival time $t^{\ast }$ of $i^{\ast }$, and the timing of the best candidate before $t^{\ast }$.
Case(5.1) $t^{\ast }\in [\tau ,\beta ]$: In this subcase, the competitive ratio depends on whether $i^{\ast }$ is the first candidate in $M$, i.e., whether it triggers the switch to secretary mode. This subcase is further divided into two subcases:
Case(5.1.1) $i^{\ast }=t_M$: Under this condition, no other candidate in $M$ arrives before $t^{\ast }$, and $i^{\ast }$ is the first observed candidate in $M$. In this case, the algorithm switches to secretary mode at $t^{\ast }$, and immediately selects $i^{\ast }$. This happens with probability ${(1-t^{\ast })}^{m-1}$, since all other $m-1$ candidates in $M$ must arrive after $t^{\ast }$.
Case(5.1.2) $i^{\ast }\ne t_M$: In this scenario, some other candidate from $M$ must arrive before $t^{\ast }$, causing the algorithm to switch modes before seeing $i^{\ast }$. In order for $i^{\ast }$ to be selected, it must arrive after the switch, and the best candidate in $[0,t^{\ast })$ must have arrived before $\tau$, which occurs with probability $\tau /t^{\ast }$. Also, the probability that at least one candidate in $M$ arrives before $t^{\ast }$ is $1-{(1-t^{\ast })}^{m-1}$. Hence, the contribution of this case is $\left(1-{(1-t^{\ast })}^{m-1}\right)\cdot \frac{\tau }{t^{\ast }}.$ Combining both subcases Case(5.1.1) and Case(5.1.2) and (see full version for details) to solve the integral, we have:

Case(5.2) $t^{\ast }\in [\beta ,1]$: Here the optimal candidate arrives after the predicted top candidate. We distinguish two subcases based on whether the best candidate in $[0,t^{\ast })$ is $\widehat{i}$ or not.
Case(5.2.1) The best candidate in $[0,t^{\ast })$ is not $\widehat{i}$: In this subcase the algorithm may still consider $i^{\ast }$ under certain favorable conditions. First, let us analyze the probability that $\widehat{i}$ is not the best candidate in $[0,t^{\ast })$. This occurs with probability $1-{(1-t^{\ast })}^k$, where $k$ is the number of candidates with true value exceeding that of $\widehat{i}$. Now, conditioned on this event, there must exist some candidate in $M$ arriving before $\beta$. Knowing this, the probability that at least one candidate in $M$ arrives before $\beta$ is at least $1-{(1-\beta )}^{m-1}$. This is because:

The presence of a better candidate than $\widehat{i}$ before $t^{\ast }$ can only increase the likelihood that a candidate from $M$ also appears before $\beta$, or at worst, leaves it unchanged.

Therefore, even under this conditioning, we can safely lower-bound the probability of having some candidate in $M$ before $\beta$ by $1-{(1-\beta )}^{m-1}$.

Finally, in order to observe $i^{\ast }$, the best candidate in $[0,t^{\ast })$ must arrive before $\tau$, which occurs independently with probability $\tau /t^{\ast }$. Thus, the combined lower bound is (which can be rewritten (see full version for details)):

Case(5.2.2): The best candidate in $[0,t^{\ast })$ is $\widehat{i}$: In this subcase, the algorithm must avoid selecting $\widehat{i}$ during secretary mode in order to eventually observe and select $i^{\ast }$. This happens with the following conditions are met:

1. 1.

   The probability that $\widehat{i}$ is the best candidate in $[0,t^{\ast })$ is ${(1-t^{\ast })}^k$, where $k$ is the number of candidates with true value greater than $v_{\widehat{i}}$.

2. 2.

   For the algorithm to enter secretary mode before seeing $\widehat{i}$, at least one candidate in $M$ from the subset of $M$ with value below $v_{\widehat{i}}$ must arrive before $\beta$. This happens with probability $1-{(1-\beta )}^{m_2}$, where $m_2$ is the number of such candidates.

3. 3.

   To avoid selecting $\widehat{i}$, the algorithm must skip it, which happens with probability $1-\delta$.

4. 4.

   Finally, the best candidate before $\beta$ must have arrived before $\tau$, so that the algorithm does not terminate before observing $\widehat{i}$. This occurs with probability $\tau /\beta$.

Combining all these probabilities using the contribution from this setting is lower-bounded by:

Summing the contributions from cases Case(5.1) and Case(5.2) in Equations (3.2), (3.2), and (3.2), the total competitive ratio for Case 5 is lower-bounded by:

In this case, neither the top-predicted candidate $\widehat{i}$ nor the true optimal candidate $i^{\ast }$ belongs to the high-deviation set $M$. Consequently, the algorithm may either remain entirely in prediction mode or switch to secretary mode, depending on whether any element of $M$ arrives before $\widehat{i}$. The overall analysis thus combines contributions from Case 4 (when $t^{\ast }\in [\tau ,\beta ]$), Case 5 (when $t^{\ast }\in [\beta ,1]$), together with an additional term accounting for successful selection in prediction mode.
Case(6.1): If the algorithm stays in prediction mode and hires $\widehat{i}$, this occurs when all members of $M$ arrive after $\beta$, which happens with probability ${(1-\beta )}^m$. Since $\widehat{i}\notin M$, its predicted value is within a multiplicative factor $ϵ$ of its true value. Thus, by Equation (1), the competitive ratio is at least $\frac{1-ϵ}{1+ϵ}$. Therefore, the contribution to the competitive ratio from this event is:

Case(6.2): If the algorithm switches to secretary mode before encountering $\widehat{i}$, then the selection of $i^{\ast }$ depends on its arrival time $t^{\ast }$.
Case(6.2.1): $t^{\ast }\in [\tau ,\beta ]$: Here, the algorithm is already in secretary mode, and the same logic as Equation (8) from case 4 applies:

Case(6.2.2) $t^{\ast }\in [\beta ,1]$: Here, we follow the same analysis as in Equations (3.2) and (3.2) from Case 5, where $m$ denotes the number of candidates in $M$, and $m_2$ denotes the number of candidates in $M$ whose true values are less than $v_{\widehat{i}}$, respectively. We obtain the following two contributions:

Summing the contributions from Case(6.1), Case(6.2.1), and Case(6.2.2), we obtain the overall lower bound for Case 6:

Recall that for each of the structural cases analyzed above, we derived an explicit competitive-ratio expression $C_j(m,k,m_2)$, parameterized by the integers $m$, $k$, and $m_2$ that describe the adversarial instance. The algorithm’s overall guarantee on a given instance is

and our goal is to show that

A direct minimization of $C(m,k,m_2)$ over all integer triples $(m,k,m_2)$ is not tractable: the closed-form expressions contain alternating sums and exponentially small terms such as ${(1-\beta )}^m$ and ${(1-t^{\ast })}^k$, which makes it difficult to analyze these formulas simultaneously for all integers. However, these expressions simplify dramatically once $m$, $k$, or $m_2$ becomes sufficiently large. For the remaining small values of $(m,k,m_2)$, the minimum of the case formulas can be computed exactly using a finite grid, following an approach similar to that of [36].

This motivates a structured enumeration strategy: we partition the parameter space into eight “regimes” depending on whether each variable is small (at most $20$) or large (greater than $20$). Regime 1 corresponds to all three parameters being small, while Regimes 2–8 cover all remaining combinations in which at least one parameter is large.

For small values ($m,m_2,k\le 20$), we can evaluate each $C_j(m,k,m_2)$ exactly using its closed form. For large values, terms such as ${(1-\beta )}^m$ become negligible (e.g., for $m>20$ and $\beta =0.64$, we have ), and can be conservatively replaced by zero. These replacements only decrease the computed competitive ratio, so they yield valid symbolic lower bounds. With this approach, the verification reduces to a finite enumeration over the eight regimes, as summarized in Algorithm 2.

The enumeration confirms that for all instances the competitive ratio is at least $\max \{0.262,\frac{1-ϵ}{1+ϵ}\}$, when using the parameters $\theta =0.58,\tau =0.37,\beta =0.64,\gamma =0.27,\delta =0.46.$

We now list the symbolic simplifications for large $m$, $k$, and $m_2$ used in Regimes 2–8 (regimes to 8 cases based on $m$, $k$, and $m_2$ being small or large, i.e. regime 1 is all of them being small) of Algorithm 2. We have to calculate other regimes cause formulas are dependent to $m,m_2$ and $k$ and we should bound them. For example, assuming a large $m>20$ in the Equation Equation 5, we can ignore the right-hand side and left-hand side ${(1-\beta )}^{m-1}$ is less than 0.0001, so the left-hand side will be bounded by $(\tau /\beta )\times \delta \times 0.9999$ same idea works for Equation Equation 7 and other similar equations. In general, in the following formulas, we rounded down all small numbers to $0$. and All $1-\text{small number}$ to 0.9999. As we can show, all these small numbers are less than $0.0001$. Similarly, for other large $m>20$ in the exponent, the corresponding terms approach zero, allowing us to simplify the equations as follows:

For large $m>20$:

The next parameter to discuss is $k$. Similar to $m$, when we raise fixed numbers to the power of $k>20$, the result will be close to zero.

For large $k>20$:

The last parameter is $m_2$, which is bounded by $m$. However, when $m$ is large, this parameter can also become large. By rewriting the equation for large $m_2$, in the same way as in the previous two parts, we obtain:

For large $m_2$:

We should also consider the case where both $m$ and $k$ are large, and determine which formula to examine. It is worth mentioning that we do not need to calculate the case where both $m_2$ and $k$ are large separately, since $m_2$ being large implies that $m$ is large, which simplifies all equations sufficiently to compute.

For large $m$ and $k$:

Using all the above observations in Algorithm 2 establishes that the chosen parameters guarantee the competitive ratio, and thus the theorem holds. $◀$