2024/11/16 by Tomer Ezra, Ezra, Tomer, Tamar Garbuz +1
Economics, Econometrics and Finance · #Computer Science and Game Theory (cs.GT) #Economic and Technological Innovation #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2411.10892
openalex publication_date 2024/11/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
We study the classic single-choice prophet secretary problem through a resource augmentation lens. Our goal is to bound the (1-ε)-competition complexity for different classes of online algorithms. This metric asks for the smallest k such that the expected value of the online algorithm on k copies of the original instance, is at least a (1 - ε)-approximation to the expected offline optimum on the original instance (without added copies). We consider four natural classes of online algorithms: single-threshold, time-based threshold, activation-based, and general algorithms. We show that for single-threshold algorithms the (1-ε)-competition complexity is Θ(ln(\frac1ε)) (as in the i.i.d. case). Additionally, we demonstrate that time-based threshold and activation-based algorithms (which cover all previous approaches for obtaining competitive-ratios for the classic prophet secretary problem) yield a sub-optimal (1-ε)-competition complexity of Θ(\fracln(\frac1ε)lnln(\frac1ε)), which is strictly better than the class of single-threshold algorithms. Finally, we find that the (1-ε)-competition complexity of general adaptive algorithms is Θ(√ln(\frac1ε)), which is in sharp contrast to Θ(lnln(\frac1ε)) in the i.i.d. case.