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:
- 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?"
- 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