Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

Daniel Dadush, László A. Végh, Giacomo Zambelli, Fusco, Federico, Lazos, Philip, Leonardi, Stefano, Papadigenopoulos, Orestis, Pountourakis, Emmanouil, Reiffenhäuser, RebeccaSociety 2022 · DOI · arXiv · OpenAlex

TL;DR

This paper introduces a versatile "greedy-ordered" framework for solving single-sample prophet inequalities (SSPIs) directly, moving away from the standard but "lossy" reductions to secretary problems. By using a direct approach, the authors significantly sharpen competitive guarantees for online matching and matroids, and provide the first-ever constant-factor SSPI for budget-additive combinatorial auctions.

What Problem Does This Paper Address?

In the world of optimal stopping theory, prophet inequalities ask a simple question: how well can an online algorithm perform against a "prophet" who knows the future? Usually, the algorithm knows the underlying probability distributions of the items it sees. However, in many real-world scenarios, we don't have perfect distribution data; we only have historical samples.

The Single-Sample Prophet Inequality (SSPI) model is the most restrictive version of this: you get exactly one sample from each distribution before the game begins.

Previously, most researchers solved this by reducing the problem to an "Order-Oblivious Secretary" (OOS) problem. While elegant, this reduction is inherently wasteful—it essentially throws away half the available information to make the math work. The authors of this paper sought to bridge this gap by developing a direct technique that uses the samples more effectively to set thresholds and make decisions.

Methods

The authors propose a Greedy-Ordered Selection framework. The algorithm operates in two distinct phases:

  1. The Greedy Phase (Offline): The algorithm takes all the single samples and runs a greedy procedure to determine "prices" or thresholds ($\tau_e$) for each element. Essentially, it asks: "If this sample were the real value, would a greedy algorithm have picked it?"
  2. The Online Phase: As items arrive in an adversarial order, the algorithm observes the real reward ($r_e$). It accepts the item if $r_e$ beats the pre-calculated threshold $\tau_e$ and if picking it doesn't violate feasibility (like matching constraints).

To prove this works, they use a clever "two-value" thought experiment: imagine drawing two values for every item and flipping a coin to decide which is the "sample" and which is the "real reward." This symmetry allows them to prove that a significant portion of the "prophet's" value is captured by items that are "safe" to pick, regardless of the order in which they arrive.

Datasets

Not discussed in the paper. As a theoretical work in discrete algorithms, the results are proven mathematically for any independent probability distributions rather than tested on specific empirical datasets.

Key Insights and Ideas

  • Direct vs. Indirect: By avoiding the reduction to secretary problems, the algorithm can use all samples to set thresholds, rather than partitioning the data into "observation" and "selection" phases.
  • Greedy as an Online Proxy: While greedy is typically an offline algorithm, the authors show that when elements are considered in decreasing order of value, greedy decisions are independent of future (smaller) values. This property makes it a perfect tool for setting thresholds in an online setting.
  • The "Safe" Element: A core part of the analysis is identifying "safe" edges—items that are so good they would be picked by the algorithm regardless of the arrival order chosen by an adversary.
  • The Pointwise Limit: The authors define a class called Pointwise-SSPIs (where the algorithm's guarantee holds even if the sample and reward are correlated via a coin flip). They prove a "partial converse" showing that any Pointwise-SSPI implies an OOS policy. This explains why certain problems (like general matroids) remain hard: they are fundamentally tied to the difficulty of the Matroid Secretary Conjecture.

Key Results

The paper provides dramatic improvements over the previous state-of-the-art (SOTA) competitive ratios:

Problem Previous Best This Paper
General Matching (Edge Arrival) 512-competitive 16-competitive
Bipartite Matching (Vertex Arrival) 13.5-competitive 8-competitive
Budget-Additive Auctions N/A 24-competitive
Transversal Matroid 16-competitive 8-competitive
Graphic Matroid 8-competitive 4-competitive

The result for budget-additive combinatorial auctions is particularly noteworthy as it is the first constant-factor guarantee for this setting using only a single sample.

Limitations and Future Work

  • General Matroids: Despite the improvements, a constant-factor SSPI for general matroids remains elusive. The authors' theoretical work suggests this is because such a result would likely solve the famous (and currently open) Matroid Secretary Conjecture.
  • Correlation: The current framework relies heavily on the independence of distributions between different elements. Extending these "greedy-ordered" techniques to settings with correlated distributions remains a major challenge.
  • Beyond Pointwise: Since the authors showed that "Pointwise" algorithms are limited by secretary problem bounds, future breakthroughs might require "non-pointwise" algorithms that use the numerical values of samples in more complex ways than simple comparisons.

Summary updated

Abstract

We study single-sample prophet inequalities (SSPIs), i.e., prophet inequalities where only a single sample from each prior distribution is available. Besides a direct, and optimal, SSPI for the basic single choice problem [Rubinstein et al., 2020], most existing SSPI results were obtained via an elegant, but inherently lossy, reduction to order-oblivious secretary (OOS) policies [Azar et al., 2014]. Motivated by this discrepancy, we develop an intuitive and versatile greedy-based technique that yields SSPIs directly rather than through the reduction to OOSs. Our results can be seen as generalizing and unifying a number of existing results in the area of prophet and secretary problems. Our algorithms significantly improve on the competitive guarantees for a number of interesting scenarios (including general matching with edge arrivals, bipartite matching with vertex arrivals, and certain matroids), and capture new settings (such as budget additive combinatorial auctions). Complementing our algorithmic results, we also consider mechanism design variants. Finally, we analyze the power and limitations of different SSPI approaches by providing a partial converse to the reduction from SSPI to OOS given by Azar et al.
BibTeX
@inproceedings{dadush2022proceedings,
  author = {Daniel Dadush and László A. Végh and Giacomo Zambelli and Fusco, Federico and Lazos, Philip and Leonardi, Stefano and Papadigenopoulos, Orestis and Pountourakis, Emmanouil and Reiffenhäuser, Rebecca},
  title = {{Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)}},
  booktitle = {Society},
  year = {2022},
  doi = {10.1137/1.9781611977073},
}

Loading related content...

Figure