Prophet Inequalities for Independent and Identically Distributed Random Variables from an Unknown Distribution

José Correa (), Paul Dütting (), Felix Fischer () and Kevin Schewior ()
Additional contact information
José Correa: Departamento de Ingeniería Industrial, Universidad de Chile, Santiago 8320000, Chile
Paul Dütting: Department of Mathematics, London School of Economics, London WC2A 2AE, United Kingdom
Felix Fischer: School of Mathematical Sciences, Queen Mary University of London, London E1 4NS, United Kingdom
Kevin Schewior: Department Mathematik/Informatik, Universität zu Köln, Köln 50931, Germany

Mathematics of Operations Research, 2022, vol. 47, issue 2, 1287-1309

Abstract: A central object of study in optimal stopping theory is the single-choice prophet inequality for independent and identically distributed random variables: given a sequence of random variables X 1 , … , X n drawn independently from the same distribution, the goal is to choose a stopping time τ such that for the maximum value of α and for all distributions, E [ X τ ] ≥ α · E [ max t X t ] . What makes this problem challenging is that the decision whether τ = t may only depend on the values of the random variables X 1 , … , X t and on the distribution F . For a long time, the best known bound for the problem had been α ≥ 1 − 1 / e ≈ 0.632 , but recently a tight bound of α ≈ 0.745 was obtained. The case where F is unknown, such that the decision whether τ = t may depend only on the values of the random variables X 1 , … , X t , is equally well motivated but has received much less attention. A straightforward guarantee for this case of α ≥ 1 / e ≈ 0.368 can be derived from the well-known optimal solution to the secretary problem, where an arbitrary set of values arrive in random order and the goal is to maximize the probability of selecting the largest value. We show that this bound is in fact tight. We then investigate the case where the stopping time may additionally depend on a limited number of samples from F , and we show that, even with o ( n ) samples, α ≤ 1 / e . On the other hand, n samples allow for a significant improvement, whereas O ( n 2 ) samples are equivalent to knowledge of the distribution: specifically, with n samples, α ≥ 1 − 1 / e ≈ 0.632 and α ≤ ln ( 2 ) ≈ 0.693 , and with O ( n 2 ) samples, α ≥ 0.745 − ε for any ε > 0 .

Keywords: Primary: 62L15; 60G40; 68W27; 91B26; optimal stopping; prophet inequalities; posted pricing; online algorithms (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1167 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:2:p:1287-1309

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().