Technical Summary: The Secretary Problem with a Stochastic Precursor

Problem Definition

This paper investigates a variation of the classic Secretary Problem (an optimal stopping problem) augmented with a specific form of asynchronous side information. In the standard setting, $n$ items arrive sequentially in either random or adversarial order, and the goal is to stop exactly at the unique best item. Without side information, the optimal success probability in the random-order model is $1/e$, while deterministic algorithms in the adversarial-order model cannot guarantee positive success probability.

The authors introduce a stochastic precursor model. After the arrival order is fixed, a signal time $S$ is drawn from a distribution dependent on the arrival time $I$ of the best item. Crucially, the signal is content-free: it carries no information about the values or ranks of the items. Its sole utility is temporal; it guarantees that $S \le I$ (the signal arrives no later than the best item) but provides no direct instruction on when to stop. The paper isolates the algorithmic value of this "timing-only" information.

The signal distribution is modeled using an $\alpha$-power family. Conditioned on $I=i$, the signal time $S$ follows a distribution where $P[S=s|I=i] = \frac{s^\alpha - (s-1)^\alpha}{i^\alpha}$ for $s \in [i]$.

• $\alpha = 1$: $S$ is uniformly distributed on $[I]$.
• $\alpha > 1$: The signal tends to occur later, closer to $I$.
• $\alpha < 1$: The signal tends to occur earlier.

Methodology

The authors employ a combination of dynamic programming, probabilistic analysis, and integer linear programming to characterize optimal policies under two arrival models: Random Order and Adversarial Order.

1. Random-Order Model

• Dynamic Programming: The authors derive a Bellman recursion (Lemma 1) to determine the optimal policy. They define the state by the current time $t$ and whether a record (an item better than all previous ones) has been observed.
• Threshold Policies: The analysis focuses on policies of the form $A(k)$, which reject all items before time $k$ and accept the first record thereafter. The optimal policy is shown to be of the form $A(\max\{S, k_n\})$, where the threshold depends on the signal $S$ and potentially a deterministic cutoff $k_n$.
• Asymptotic Analysis: The authors analyze the success probability as $n \to \infty$, deriving closed-form expressions for the optimal success rate based on the parameter $\alpha$.

2. Adversarial-Order Model

• Hard Instances: To establish upper bounds, the authors utilize a family of "hard instances" $I_i = (1, 2, \dots, i, 0, \dots, 0)$, where the maximum is at position $i$.
• Randomized vs. Deterministic:
  • For randomized policies, the authors construct a specific random threshold $R$ independent of $S$ to maximize the worst-case success probability.
  • For deterministic policies, they prove that the optimal strategy is simply $A(S)$ (stop at the first record after the signal).
• Full Signal History: The paper extends the model to cases where $m$ independent uniform signals are observed (equivalent to an $\alpha=m$ power signal). They distinguish between observing only the maximum signal time $L = \max(S_1, \dots, S_m)$ versus observing the full history of all $m$ signal times. This is analyzed using an Integer Linear Program (ILP) for deterministic policies.

Key Contributions and Results

1. Random-Order Results

• Optimal Policies: The paper fully characterizes the optimal policy for all $\alpha > 0$.
  • If $\alpha \ge 1$, the optimal policy is $A(S)$: wait for the signal, then accept the first record. This policy does not require knowledge of $n$.
  • If $0 < \alpha < 1$, the optimal policy is $A(\max\{S, k_n\})$, where $k_n/n \to (1-\alpha)^{1/\alpha}$. This requires knowledge of $n$ (or an estimate).
• Performance Gains:
  • Even with a single uniform signal ($\alpha=1$), the success probability exceeds $1/2$, significantly improving upon the classic $1/e \approx 0.37$ benchmark.
  • As $\alpha \to \infty$ (signals arrive very close to the optimum), the success probability approaches 1.
  • As $\alpha \to 0$, the probability approaches $1/e$.
• Robustness: The authors show that if the parameter $\alpha$ is unknown but a conservative estimate $\hat{\alpha} \le \alpha$ is available, the policy tuned to $\hat{\alpha}$ still guarantees a success probability strictly greater than $1/e$. Overestimating $\alpha$ can be harmful if the true signal is early, but the degradation is smooth.

2. Adversarial-Order Results

• Breaking the Zero-Guarantee Barrier: In the standard adversarial setting, deterministic algorithms have 0 success probability. With the stochastic precursor:
  • Deterministic Policies: The policy $A(S)$ achieves a success probability of $1 - (1 - 1/n)^\alpha$. Asymptotically, if $\alpha/n \to c$, the success probability approaches $1 - e^{-c}$.
  • Randomized Policies: The optimal success probability is $n^\alpha / \sum_{j=1}^n j^\alpha$, which also converges to $1 - e^{-c}$ when $\alpha/n \to c$.
• Full History vs. Last Signal:
  • Randomized Policies: Observing the full history of $m$ signals provides no additional worst-case power compared to observing only the maximum signal time $L$ (Theorem 8).
  • Deterministic Policies: Observing the full history strictly improves the worst-case guarantee. For $m=2$ and $n=4$, the full-history guarantee is $1/2$, whereas the last-signal guarantee is $7/16$. Asymptotically for $m=2$, the full-history success probability scales as $3/n$, compared to $2/n$ for the last-signal baseline.

3. Experimental Validation

The paper includes numerical experiments confirming the theoretical asymptotic regimes.

• In random order, the gains over the $1/e$ benchmark are visible even for moderate $n$.
• The policies are robust to misspecification of $\alpha$ when the estimate is conservative.
• In adversarial order, the empirical results match the predicted $1 - e^{-c}$ limit for $\alpha = cn$.
• Experiments on corrupted signals (missed, false alarms, delayed) show that a simple fallback policy (reverting to the classic $n/e$ rule if the signal is late) provides a smooth interpolation between the learned and prediction-free regimes.

Significance and Claims

The paper claims to isolate a distinct and powerful form of advice in online decision-making: predictive timing rather than predictive content.

• Novel Information Model: Unlike standard learning-augmented algorithms that rely on predictions of values, ranks, or thresholds, this model relies solely on an asynchronous, content-free signal. The authors argue that this timing information alone is sufficient to fundamentally alter the structure of optimal stopping.
• Overcoming Hard Regimes: The results demonstrate that even in the notoriously difficult adversarial-order setting, a sufficiently concentrated temporal signal allows for constant success guarantees (or $O(1/n)$ for deterministic policies) where none existed before.
• Practical Relevance: The authors motivate the model with applications where side information arrives asynchronously, such as delayed hiring recommendations, early attention metrics in popularity forecasting, or evolving user-behavior signals in recommendation systems. In these scenarios, the signal may not predict the exact value of a candidate but can indicate that a "strong candidate" is still ahead.

The paper concludes that asynchronous temporal information is a tractable resource that can be effectively leveraged to improve online decision-making, even when the signal carries no direct instructional value about the current item's quality.