The Competition Complexity of Prophet Inequalities

Johannes Brustle, José Correa, Paul Dütting, Tomer Ezra, Michal Feldman, Victor Verdugo

TL;DR

This paper introduces and analyzes the "competition complexity" of online algorithms, specifically for the prophet inequality problem. They show that by augmenting an online algorithm with a limited number of "copies" of the input instance, we can achieve near-optimal performance. Notably, they establish an exponential gap between simple "single threshold" algorithms and more sophisticated "block threshold" algorithms, with the latter achieving near-optimal results much faster.

What Problem Does This Paper Address?

The classic "prophet inequality" problem deals with an online algorithm trying to maximize its gain from a sequence of items, each with a value drawn from a known distribution. The algorithm must decide whether to take an item as it arrives or wait for a potentially better one, without knowing future values. The "offline optimum" (a clairvoyant algorithm) can see all values and simply pick the best. The standard prophet inequality quantifies how far the online algorithm is from this optimum.

This paper tackles a related question: how much "resource augmentation" does an online algorithm need to perform almost as well as the offline optimum? Specifically, they consider giving the online algorithm k copies of the original instance. The "competition complexity" is the minimum k required to guarantee the online algorithm achieves at least a $(1-\epsilon)$ fraction of the offline optimum's expected value. This is motivated by scenarios in mechanism design and pricing where simpler online mechanisms might attract more "buyers" (copies of the instance) than a complex optimal mechanism.

Methods

The core of the paper is the analysis of different types of online algorithms under this resource augmentation framework. They focus on:

  • Single Threshold Algorithms: These algorithms set a single price (threshold) and accept the first item whose value exceeds this price.
  • Block Threshold Algorithms: These algorithms can set a different threshold for each of the k copies (blocks) of the instance. They accept the first item in a block that exceeds that block's threshold.
  • General Threshold Algorithms: The most general class, which can set a threshold for every single arrival.

The authors use a combination of techniques:

  • Approximate Stochastic Dominance: A key technical tool to relate the expected performance of the online algorithm to the expected value of the offline optimum. This allows them to bound the performance of algorithms based on thresholds.
  • Max-Min Optimization: To find the best possible thresholds for block threshold algorithms, they formulate and analyze a max-min optimization problem.
  • Reduction and Proof by Induction: They reduce the problem to simpler cases (like k=2) and use inductive arguments to generalize their findings.
  • Analysis of Arrival Order: They explore how the results change if the order of items within blocks is arbitrary or if items can "displace" across blocks, introducing the "y-displacement model."

Datasets

Not discussed in the paper. The paper deals with theoretical models and distributions, not empirical datasets.

Key Insights and Ideas

  • Resource Augmentation is Powerful: Even a limited number of "copies" of the input instance can dramatically improve the performance of online algorithms, bringing them close to the offline optimum.
  • Block Thresholds are Key: The ability to set different thresholds for different "blocks" (copies of the instance) is crucial. Block threshold algorithms achieve near-optimal performance with a surprisingly small number of copies, scaling as $O(\log \log(1/\epsilon))$.
  • Exponential Gap: There's an exponential difference in performance between simple single-threshold algorithms and block threshold algorithms. Single-threshold algorithms require $O(\log(1/\epsilon))$ copies to achieve a similar $(1-\epsilon)$ approximation, highlighting the advantage of dynamic pricing (or block-specific pricing).
  • Combinatorial Extensions: The framework extends naturally to more complex settings like combinatorial auctions and bipartite matching, showing its broad applicability.

Key Results

  • Block Threshold Algorithms: The $(1-\epsilon)$-competition complexity is $\Theta(\log \log(1/\epsilon))$. This means these algorithms approach the offline optimum "doubly exponentially fast" with increasing copies.
  • Single Threshold Algorithms: The $(1-\epsilon)$-competition complexity is $\Theta(\log(1/\epsilon))$. This establishes an exponential gap compared to block threshold algorithms.
  • Combinatorial Auctions: For XOS and submodular auctions, block-consistent pricing achieves $O(\log(1/\epsilon))$ complexity, while static pricing achieves $O(1/\epsilon)$.
  • Bipartite Matching: The online algorithm presented achieves $O(\log(1/\epsilon))$ competition complexity.

Limitations and Future Work

  • Point Masses: The paper primarily assumes continuous distributions for simplicity. While they discuss how to handle point masses, the analysis is more complex.
  • Adversarial Arrival Orders: While they analyze some relaxed arrival order models, the fully adversarial case (where an adversary can choose any permutation of all $nk$ items) still shows a lower bound of $\Omega(1/\epsilon)$ for single-threshold algorithms, suggesting that even with resource augmentation, performance can degrade significantly in highly adversarial settings.
  • General Combinatorial Settings: The paper presents preliminary results for combinatorial auctions and matching. Further exploration of other combinatorial settings (e.g., matroids) and different notions of resource augmentation is suggested.
  • Dynamic vs. Static Prices: The paper highlights the advantage of dynamic pricing (or block-consistent pricing) over static pricing. Further formalizing this separation and exploring dynamic pricing in more complex scenarios is an open direction.

Summary updated

Abstract

We study the classic single-choice prophet inequality problem through a resource 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.
BibTeX
@inproceedings{brustle2024competition,
  author = {Johannes Brustle and José Correa and Paul Dütting and Tomer Ezra and Michal Feldman and Victor Verdugo},
  title = {{The Competition Complexity of Prophet Inequalities}},
  booktitle = {EC},
  year = {2024},
  doi = {10.1145/3670865.3673467},
}
Figure