The model of streaming algorithms is motivated by the increasingly common situation in which the sheer amount of available data limits the ways in which the data can be accessed. Streaming algorithms are typically allowed a single pass over the data and can only store a sublinear fraction of the data at any time. We initiate the study of classic online selection problems\dots in a streaming model where the data stream consists of two parts: historical data points that an algorithm can use to learn something about the input; and data points from which a selection can be made. Both types of data points are i.i.d. draws from an unknown distribution . We consider the two canonical objectives for online selection---maximizing the probability of selecting the maximum and maximizing the expected value of the selection---and provide the first performance guarantees for both these objectives in the streaming model .
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 .
R
The model of streaming algorithms is motivated by the increasingly common situation in which the sheer amount of available data limits the ways in which the data can be accessed. Streaming algorithms are typically allowed a single pass over the data and can only store a sublinear fraction of the data at any time. We initiate the study of classic online selection problems
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,
A
,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
R
where the
of computation and thus in situations where the use of relevant data is complicated by the sheer amount of
R
stream consists of two parts: historical data points that an algorithm can use to learn something about the input; and data points from which a selection can be made. Both types of data points are
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
R
draws from an unknown distribution . We consider the two canonical objectives for online selection---maximizing the probability of selecting the maximum and maximizing the expected value of the selection---and provide the first performance guarantees for both these objectives in the streaming model
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