Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
Abstract
We study prophet inequalities for n i.i.d. base rewards subject to multiplicative discounts across S phases. For equal-length phases and a common discount factor γ̃, we characterize the optimal competitive ratio of single-quantile policies as n→∞ with S and γ̃ fixed. The resulting sharp guarantee describes the dependence on the phase parameters: it recovers 1−1/e without discounting and approaches 1/2 in the worst-case regime. We also establish a distribution-free comparison that bounds the discounted prophet by a fractional i.i.d. maximum with effective horizon B, the sum of the discount weights across all observations. The comparison yields acceptance probability 1/B, determined only by the phase profile. This calibration attains the canonical optimum even among single-quantile policies that may choose their acceptance probability using the known base distribution. The comparison also gives guarantees for heterogeneous discounts and unequal phase lengths. A complementary optimal-stopping upper bound establishes the same limiting optimum of 1/2 for arbitrary stopping rules in the canonical model. Finally, the same effective-horizon calibration sets acceptance probability 1−γ̃ under infinite-horizon geometric discounting. This explicit quantile rule attains Boshuizen's (1994) known optimal worst-case ratio 1/(1+γ̃) without solving a Bellman equation.
Related
BibTeX
@misc{kim2026effective,
title = {{Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards}},
author = {Jung-Hun Kim and Vianney Perchet},
howpublished = {HAL},
year = {2026},
month = nov,
eprint = {2606.30118},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05855084v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
AU - Jung-Hun Kim
AU - Vianney Perchet
PY - 2026
DA - 2026/11/06
PB - HAL
UR - https://hal.science/hal-05855084v1
AB - We study prophet inequalities for n i.i.d. base rewards subject to multiplicative discounts across S phases. For equal-length phases and a common discount factor γ̃, we characterize the optimal competitive ratio of single-quantile policies as n→∞ with S and γ̃ fixed. The resulting sharp guarantee describes the dependence on the phase parameters: it recovers 1−1/e without discounting and approaches 1/2 in the worst-case regime. We also establish a distribution-free comparison that bounds the discounted prophet by a fractional i.i.d. maximum with effective horizon B, the sum of the discount weights across all observations. The comparison yields acceptance probability 1/B, determined only by the phase profile. This calibration attains the canonical optimum even among single-quantile policies that may choose their acceptance probability using the known base distribution. The comparison also gives guarantees for heterogeneous discounts and unequal phase lengths. A complementary optimal-stopping upper bound establishes the same limiting optimum of 1/2 for arbitrary stopping rules in the canonical model. Finally, the same effective-horizon calibration sets acceptance probability 1−γ̃ under infinite-horizon geometric discounting. This explicit quantile rule attains Boshuizen's (1994) known optimal worst-case ratio 1/(1+γ̃) without solving a Bellman equation.
ER -