Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2406.17767 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917989091115008 |
|---|---|
| author | Brustle, Johannes Perez-Salazar, Sebastian Verdugo, Victor |
| author_facet | Brustle, Johannes Perez-Salazar, Sebastian Verdugo, Victor |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_17767 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Splitting Guarantees for Prophet Inequalities via Nonlinear Systems Brustle, Johannes Perez-Salazar, Sebastian Verdugo, Victor Computer Science and Game Theory Optimization and Control 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. |
| title | Splitting Guarantees for Prophet Inequalities via Nonlinear Systems |
| topic | Computer Science and Game Theory Optimization and Control |
| url | https://arxiv.org/abs/2406.17767 |