The Competition Complexity of Prophet Inequalities
<|reference_start|>The Competition Complexity of Prophet Inequalities: We study the classic single-choice prophet inequality problem through a resource augmentation lens. Our goal is to bound the $(1-\varepsilon)$-competition complexity of different types 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-\varepsilon)$-approximation to the expected offline optimum on a single copy.   We show that block threshold algorithms, which set one threshold per copy, are optimal and give a tight bound of $k = \Theta(\log \log 1/\varepsilon)$. This shows that block threshold algorithms approach the offline optimum doubly-exponentially fast. For single threshold algorithms, we give a tight bound of $k = \Theta(\log 1/\varepsilon)$, establishing an exponential gap between block threshold algorithms and single threshold algorithms.   Our model and results pave the way for exploring resource-augmented prophet inequalities in combinatorial settings. In line with this, we present preliminary findings for bipartite matching with one-sided vertex arrivals, as well as in XOS combinatorial auctions. Our results have a natural competition complexity interpretation in mechanism design and pricing applications.<|reference_end|>
@article{brustle2024the,
    title={The Competition Complexity of Prophet Inequalities},
    author={Johannes Brustle, Jos'e Correa, Paul D"utting, Tomer Ezra, Michal
  Feldman, Victor Verdugo},
    journal={arXiv preprint arXiv:2402.11084},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.11084},
    primaryClass={cs.GT cs.DS}
}