# The Stationary Prophet Inequality Problem

arXiv: https://arxiv.org/abs/2107.10516 · HTML: https://mlsanity.com/paper/2107.10516/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jul 2021.

## Built on by (most cited first, 1 of 1)

- [The Competition Complexity of Prophet Inequalities with Correlations](https://mlsanity.com/paper/2409.06868/) (2024)

## Abstract (arXiv)

We study a continuous and infinite time horizon counterpart to the classic prophet inequality, which we term the stationary prophet inequality problem. Here, copies of a good arrive and perish according to Poisson point processes. Buyers arrive similarly and make take-it-or-leave-it offers for unsold items. The objective is to maximize the (infinite) time average revenue of the seller. Our main results are pricing-based policies which (i) achieve a 1/2-approximation of the optimal offline policy, which is best possible, and (ii) achieve a better than (1-1/e)-approximation of the optimal online policy. Result (i) improves upon bounds implied by recent work of Collina et al. (WINE'20), and is the first optimal prophet inequality for a stationary problem. Result (ii) improves upon a 1-1/e bound implied by recent work of Aouad and Saritacc (EC'20), and shows that this prevalent bound in online algorithms is not optimal for this problem.