Streaming Algorithms for Online Selection Problems

José R. Correa, Paul Dütting, Felix A. Fischer, Kevin Schewior, Bruno ZiliottoarXiv 2020 · arXiv · OpenReview

Abstract

A prophet inequality states, for some $\alpha\in[0,1]$, that the expected value achievable by a gambler who sequentially observes random variables $X_1,\dots,X_n$ and selects one of them is at least an $\alpha$ fraction of the maximum value in the sequence. We obtain three distinct improvements for a setting that was first studied by Correa et al. (EC, 2019) and is particularly relevant to modern applications in algorithmic pricing. In this setting, the random variables are i.i.d. from an unknown distribution and the gambler has access to an additional $\beta n$ samples for some $\beta\geq 0$. We first give improved lower bounds on $\alpha$ for a wide range of values of $\beta$; specifically, $\alpha\geq(1+\beta)/e$ when $\beta\leq 1/(e-1)$, which is tight, and $\alpha\geq 0.648$ when $\beta=1$, which improves on a bound of around $0.635$ due to Correa et al. (SODA, 2020). Adding to their practical appeal, specifically in the context of algorithmic pricing, we then show that the new bounds can be obtained even in a streaming model of computation and thus in situations where the use of relevant data is complicated by the sheer amount of data available. We finally establish that the upper bound of $1/e$ for the case without samples is robust to additional information about the distribution, and applies also to sequences of i.i.d. random variables whose distribution is itself drawn, according to a known distribution, from a finite set of known candidate distributions. This implies a tight prophet inequality for exchangeable sequences of random variables, answering a question of Hill and Kertz (Contemporary Mathematics, 1992), but leaves open the possibility of better guarantees when the number of candidate distributions is small, a setting we believe is of strong interest to applications.

Introduction

In the classic prophet inequality problem, a gambler observes a sequence of random variables and must decide immediately whether to accept the current value or continue. The goal is to maximize the expected value relative to a "prophet" who knows all values in advance. While the optimal competitive ratio $\alpha$ is well-understood for known distributions, the "Unknown I.I.D." setting presents a more realistic challenge: values are drawn from the same distribution, but the distribution itself is unknown.

Without additional information, the best achievable ratio is $1/e \approx 0.368$. This paper investigates how access to $\beta n$ historical samples can bridge the gap toward the known-distribution limit of $\approx 0.745$.

Improved Performance Bounds

The authors provide tighter performance guarantees for gamblers using Maximum-of-Random-Subset (MRS) algorithms. These strategies set thresholds based on the maximum value found in a random subset of available data. By transforming the search for the best MRS algorithm into a variational control problem, the authors derived exact performance bounds for various sample sizes.

Comparison of performance guarantees ($\alpha$) as a function of the sample ratio ($\beta$).

As shown in the figure above, the new bounds (red dots) significantly improve upon previous results (blue crosses). For small sample sizes ($\beta \le 1/(e-1) \approx 0.58$), the competitive ratio is exactly $(1+\beta)/e$, which is proven to be tight. For the case of $n$ samples ($\beta=1$), the lower bound is improved from $0.635$ to $0.648$.

Streaming Algorithms and Practical Implementation

A key contribution of this work is the adaptation of these strategies to the streaming model of computation. In modern algorithmic pricing, the volume of data can be overwhelming. The authors demonstrate that these improved bounds can be achieved using only $O(\log n)$ space. This is accomplished by "recycling" thresholds and employing reservoir-style sampling to construct subsets on the fly, making the algorithms highly practical for large-scale data environments.

Robustness and Impossibility Results

The paper also addresses the robustness of the $1/e$ barrier. The authors prove that even if a gambler has a "prior" (knowing the distribution is one of a finite set of candidates), they cannot beat the $1/e$ bound without actual samples as the sequence length $n$ grows. This result establishes a tight prophet inequality for exchangeable sequences of random variables, resolving a 30-year-old open question in optimal stopping theory.

Conclusion

By quantifying the value of historical data and providing memory-efficient implementations, this work advances both the theoretical understanding and practical application of online selection problems. While MRS algorithms show a performance ceiling around $\alpha \approx 0.653$, they offer a robust and efficient path forward for decision-making under uncertainty.

Summary updated

Abstract

A prophet inequality states, for some $\alpha\in[0,1]$, that the expected value achievable by a gambler who sequentially observes random variables $X_1,\dots,X_n$ and selects one of them is at least an $\alpha$ fraction of the maximum value in the sequence. We obtain three distinct improvements for a setting that was first studied by Correa et al. (EC, 2019) and is particularly relevant to modern applications in algorithmic pricing. In this setting, the random variables are i.i.d. from an unknown distribution and the gambler has access to an additional $\beta n$ samples for some $\beta\geq 0$. We first give improved lower bounds on $\alpha$ for a wide range of values of $\beta$; specifically, $\alpha\geq(1+\beta)/e$ when $\beta\leq 1/(e-1)$, which is tight, and $\alpha\geq 0.648$ when $\beta=1$, which improves on a bound of around $0.635$ due to Correa et al. (SODA, 2020). Adding to their practical appeal, specifically in the context of algorithmic pricing, we then show that the new bounds can be obtained even in a streaming model of computation and thus in situations where the use of relevant data is complicated by the sheer amount of data available. We finally establish that the upper bound of $1/e$ for the case without samples is robust to additional information about the distribution, and applies also to sequences of i.i.d. random variables whose distribution is itself drawn, according to a known distribution, from a finite set of known candidate distributions. This implies a tight prophet inequality for exchangeable sequences of random variables, answering a question of Hill and Kertz (Contemporary Mathematics, 1992), but leaves open the possibility of better guarantees when the number of candidate distributions is small, a setting we believe is of strong interest to applications.
BibTeX
@misc{correa2020streaming,
  author = {José R. Correa and Paul Dütting and Felix A. Fischer and Kevin Schewior and Bruno Ziliotto},
  title = {{Streaming Algorithms for Online Selection Problems}},
  year = {2020},
  eprint = {2007.06110},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2007.06110},
}
Figure