Research map / Learning theory and algorithms / Prediction and decision losses
The Secretary Problem with Predicted Additive Gap
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces the secretary problem with a predicted additive gap (w1 - wk) and gives threshold algorithms that beat 1/e (ratio 0.4 with exact gap), plus robust-consistent and bounded-error variants.
Problem
The classical secretary problem has a tight competitive ratio of 1/e; prior prediction work assumed predictions of the largest weight or of every weight. The paper asks what weakest piece of advice (an additive gap between the highest and k-th highest weight) can still beat 1/e.
Approach
Use a predicted additive gap c = w1 - wk as a threshold offset: wait for time tau, then accept the first element exceeding max(best-so-far, c). Analysis splits into small-gap and large-gap cases, yielding a 0.4 ratio with exact gap; a modified version lowers the threshold after time 1-gamma to gain robustness to wrong predictions.
Key results
- With exact additive gap, the algorithm achieves competitive ratio at least 0.4 (vs 1/e ≈ 0.368) for any k and gap, even without knowing k (tau=0.2).
- Robust variant with tau=0.2 and gamma=0.6 is about 0.383-consistent and 0.183-robust.
- In simulations on Pareto weights the gap-aware algorithm achieves roughly 0.8 competitive ratio versus about 1/e for the classical algorithm.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an exact additive gap in the acceptance threshold | Secretary problem · Any additive gap c_k = w_1 − w_k | competitive ratio: 1/e -> 0.4 | Helped |
| Use the exact gap without knowing its index k, with τ = 0.2 | Secretary with Exact Additive Gap · Secretary problem | competitive ratio: at least 0.4 | Helped |
| Lower the threshold after time 1 − γ | Robust-Consistent Algorithm · Secretary problem with accurate or inaccurate predicted gap | competitive ratio: (1/e + O(1))-consistent; O(1)-robust | Mixed |
| Subtract the known error bound ε from the predicted gap | Secretary with Bounded Prediction Error · Secretary problem with gap error bounded by ε | expected weight guarantee: 0.4 · w_1 − 2 ε | Helped |
| Use additive-gap information with τ = 0.2 | Secretary with Exact Additive Gap · Pareto weights | competitive ratio: approximately 1/e -> approximately 0.8 | Helped |
| Use a waiting time depending on k instead of τ = 0.2 (ablation) | Secretary with Exact Additive Gap · Pareto weights | competitive ratio | Mixed |
| Use a waiting time depending on k for k = 2 (ablation) | Secretary with Exact Additive Gap · Exponential and Chi-Squared weights | competitive ratio | Hurt |
| Increase the gap index k, yielding a larger gap (ablation) | Secretary with Exact Additive Gap · Exponential weights | competitive ratio | Helped |
| Underestimate the predicted gap, with σ < 0.5 (ablation) | Secretary gap-prediction algorithms · Exponential weights | competitive ratio: approximately 0.65 | No clear effect |
| Overestimate the gap for k = 100 or k = 200 (ablation) | Secretary with Exact Additive Gap · Exponential weights | competitive ratio: approximately 0.65 -> zero | Hurt |
| Drop the predicted gap from the threshold after time 1 − γ (ablation) | Robust-Consistent Algorithm · Exponential weights with overestimated gap | competitive ratio: zero -> approximately 0.15 | Helped |
| Overestimate the gap by a factor of three for k = 2 (ablation) | Secretary gap-prediction algorithms · Exponential weights | competitive ratio | No clear effect |
Surprising findings
- Knowing an exact additive gap is enough to beat 1/e even when the index k is unknown.
- Overestimating the gap can drive the selection probability to zero, while underestimating degrades smoothly.
Limitations
- Guarantees (0.4) are likely not tight; hardness bound from two-best secretary gives about 0.5736 as an upper limit for exact gap.
- Robust variant trades consistency for robustness; the robustness constant is only about 0.183 at the chosen parameters.
- Simulations use synthetic weight distributions and n=200 only.
Experimental setup
Benchmarks: simulated secretary instances (Pareto, Exponential, Chi-squared, Exponential with superstar)
Metrics: competitive ratio
Baselines: classical secretary algorithm (waiting time 1/e)
Builds on: classical secretary threshold algorithm two-best secretary problem robustness-consistency framework for algorithms with predictions
Closest papers by meaning
- Fair Secretaries with Unfair Predictions (NeurIPS 2024 · similarity 0.90)
- Ordinal Secretaries with Advice (AAAI 2026 · similarity 0.89)
- Secretary and Online Matching Problems with Machine Learned Advice (NeurIPS 2020 · similarity 0.88)
- Secretary Ranking with Minimal Inversions (NeurIPS 2019 · similarity 0.85)
- The Secretary Problem with Competing Employers on Random Edge Arrivals (AAAI 2022 · similarity 0.85)
- Communication Bounds for the Distributed Experts Problem (NeurIPS 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.