Prophet Inequalities over Time
Open Access
- 13 November 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Economics and Computation
- Vol. 13 (4) , 1-36
Abstract
In this article, we introduce an over-time variant of the well-known prophet inequality with i.i.d. random variables. Instead of stopping with one realized value at some point in the process, we decide for each step how long we select the value. Then we cannot select another value until this period is over. The goal is to maximize the expectation of the sum of selected values. We describe the structure of the optimal stopping rule and give upper and lower bounds on the prophet inequality. In online algorithms terminology, this corresponds to bounds on the competitive ratio of an online algorithm. We give a surprisingly simple algorithm with a single threshold that results in a prophet inequality of ≈ 0.396 for all input lengths n . Additionally, as our main result, we present a more advanced algorithm resulting in a prophet inequality of ≈ 0.598 when the number of steps tends to infinity. We complement our results by an upper bound that shows that the best possible prophet inequality is at most 1/φ ≈ 0.618, where φ denotes the golden ratio.Keywords
This publication has 15 references indexed in Scilit:
- Sample-Driven Optimal Stopping: From the Secretary Problem to the i.i.d. Prophet InequalityMathematics of Operations Research, 2024
- Learning To Maximize Welfare with a Reusable ResourceProceedings of the ACM on Measurement and Analysis of Computing Systems, 2022
- Prophet Inequalities for Independent and Identically Distributed Random Variables from an Unknown DistributionMathematics of Operations Research, 2022
- Hiring Secretaries over Time: The Benefit of Concurrent EmploymentMathematics of Operations Research, 2020
- 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
- Prophet SecretarySIAM Journal on Discrete Mathematics, 2017
- Stop rule and supremum expectations of i.i.d. random variables: A complete comparison by conjugate dualityJournal of Multivariate Analysis, 1986
- Semiamarts and finite valuesBulletin of the American Mathematical Society, 1977
- Recognizing the Maximum of a SequenceJournal of the American Statistical Association, 1966