The Competition Complexity of Prophet Secretary

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(\frac{1}ε))$ (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 $Θ\left(\frac{\ln(\frac{1}ε)}{\ln\ln(\frac{1}ε)}\right)$, which is strictly better than the class of single-threshold algorithms. Finally, we find that the $(1-ε)$-competition complexity of general adaptive algorithms is $Θ(\sqrt{\ln(\frac{1}ε)})$, which is in sharp contrast to $Θ(\ln\ln(\frac{1}ε))$ in the i.i.d. case.