2021/07/22 by Kristen Kessel, Amin Saberi, Kessel, Kristen +5 · 1 citation
Computer Science · Decision Sciences · #Auction Theory and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Mobile Crowdsensing and Crowdsourcing #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2107.10516
openalex publication_date 2021/07/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Saritaç (EC'20), and shows that this prevalent bound in online algorithms is not optimal for this problem.