Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility
Preprint
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.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic InputsSIAM Journal on Computing, 2020
- Matroid prophet inequalities and applications to multi-dimensional mechanism designGames and Economic Behavior, 2019
- A PAC Approach to Application-Specific Algorithm SelectionSIAM Journal on Computing, 2017
- Dynamic pricing and learning: Historical origins, current research, and new directionsSurveys in Operations Research and Management Science, 2015
- Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many BuyersSIAM Journal on Computing, 2014
- Self-Improving AlgorithmsSIAM Journal on Computing, 2011
- Hypergraph Ramsey numbersJournal of the American Mathematical Society, 2009
- Stream Order and Order Statistics: Quantile Estimation in Random-Order StreamsSIAM Journal on Computing, 2009
- Comparison of stop rule and maximum expectations for finite sequences of exchangeable random variablesStochastic Analysis and Applications, 1991
- Semiamarts and finite valuesBulletin of the American Mathematical Society, 1977