The Competition Complexity of Prophet Inequalities
Abstract
augmentation lens. Our goal is to bound the (1 - ε)-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 - ε)-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 = Θ(log log 1/ε). This shows that block threshold algorithms approach the offline optimum doubly-exponentially fast. For single threshold algorithms, we give a tight bound of k = Θ(log 1/ε), 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.
We show that block threshold algorithms, which set one threshold per copy, are optimal and give a tight bound of k = Θ(log log 1/ε). This shows that block threshold algorithms approach the offline optimum doubly-exponentially fast. For single threshold algorithms, we give a tight bound of k = Θ(log 1/ε), 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.
