Splitting Guarantees for Prophet Inequalities via Nonlinear Systems

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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-06
Main Authors: Brustle, Johannes, Perez-Salazar, Sebastian, Verdugo, Victor
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Differential equations
Dynamic programming
Inequality
Linear programming
Lower bounds
Nonlinear systems
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422