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-\epsilon )$-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-\epsilon )$-approximation to the expected off-line 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=\mathrm{\Theta }(\log \hspace{0.17em}\log 1/\epsilon )$. This shows that block threshold algorithms approach the off-line optimum doubly exponentially fast. For single threshold algorithms, we give a tight bound of $k=\mathrm{\Theta }(\log 1/\epsilon )$, 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.

Funding: J. Correa was partially funded by Anillo Information and Computation in Market Design [Agencia Nacional de Investigación y Desarrollo (ANID) Grant ACT210005] and the Center for Mathematical Modeling [ANID Grant FB210005]. T. Ezra is supported by the Harvard University Center of Mathematical Sciences and Applications. M. Feldman was partially funded by the European Research Council under the European Union’s Horizon 2020 research and innovation program [Grant 866132], by an Amazon Research Award, by the United States-Israel Binational Science Foundation [Grant 2020788], and by a grant from the TAU Center for AI and Data Science. V. Verdugo was partially funded by Anillo ICMD [ANID Grant ACT210005] and Fondecyt [ANID Grant 1241846].