2024/06/25 by Johannes Brustle, Brustle, Johannes, Sebastian Perez-Salazar +3 · 2 citations
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Inequalities and Applications #Optimization and Control (math.OC) #Optimization and Variational Analysis
paper · pdf · doi:10.48550/arxiv.2406.17767
openalex publication_date 2024/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The prophet inequality is one of the cornerstone problems in optimal stopping theory and has become a crucial tool for designing sequential algorithms in Bayesian settings. In the i.i.d. k-selection prophet inequality problem, we sequentially observe n non-negative random values sampled from a known distribution. Each time, a decision is made to accept or reject the value, and under the constraint of accepting at most k. For k=1, Hill and Kertz [Ann. Probab. 1982] provided an upper bound on the worst-case approximation ratio that was later matched by an algorithm of Correa et al. [Math. Oper. Res. 2021]. The worst-case tight approximation ratio for k=1 is computed by studying a differential equation that naturally appears when analyzing the optimal dynamic programming policy. A similar result for k>1 has remained elusive. In this work, we introduce a nonlinear system of differential equations for the i.i.d. k-selection prophet inequality that generalizes Hill and Kertz's equation when k=1. Our nonlinear system is defined by k constants that determine its functional structure, and their summation provides a lower bound on the optimal policy's asymptotic approximation ratio for the i.i.d. k-selection prophet inequality. To obtain this result, we introduce for every k an infinite-dimensional linear programming formulation that fully characterizes the worst-case tight approximation ratio of the k-selection prophet inequality problem for every n, and then we follow a dual-fitting approach to link with our nonlinear system for sufficiently large values of n. As a corollary, we use our provable lower bounds to establish a tight approximation ratio for the stochastic sequential assignment problem in the i.i.d. non-negative regime.