Optimal single threshold stopping rules and sharp prophet inequalities
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914578631229440 |
|---|---|
| author | Goldenshluger, Alexander Malinovsky, Yaakov Zeevi, Assaf |
| author_facet | Goldenshluger, Alexander Malinovsky, Yaakov Zeevi, Assaf |
| contents | This paper considers a finite horizon optimal stopping problem for a sequence of independent and identically distributed random variables, where the objective is to design stopping rules that attempt to select the random variable with the highest value in the sequence. The performance of any stopping rule may be benchmarked relative to the selection of a ``prophet" that has perfect foreknowledge of the largest value. Such comparisons are typically stated in the form of ``prophet inequalities." In this paper we develop a game-theoretic characterization that supports a principled approach for deriving sharp non-asymptotic prophet inequalities for single threshold stopping rules. We demonstrate that sharp constants in the ratio- and difference-type prophet inequalities are determined by the optimal values of infinite two-person zero-sum game on the unit square with particular payoff kernels, while the the solutions to the game provide optimal stopping rules and least favorable distributions. Among other things, this formulation also allows a systematic way to tackle restricted classes of distributions. The proposed framework leads to a numerically efficient algorithmic paradigm that allows computing sharp constants in prophet inequalities with any prescribed level of accuracy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_12949 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimal single threshold stopping rules and sharp prophet inequalities Goldenshluger, Alexander Malinovsky, Yaakov Zeevi, Assaf Probability Computer Science and Game Theory Optimization and Control Statistics Theory 60G40, 62L12, 91A05 This paper considers a finite horizon optimal stopping problem for a sequence of independent and identically distributed random variables, where the objective is to design stopping rules that attempt to select the random variable with the highest value in the sequence. The performance of any stopping rule may be benchmarked relative to the selection of a ``prophet" that has perfect foreknowledge of the largest value. Such comparisons are typically stated in the form of ``prophet inequalities." In this paper we develop a game-theoretic characterization that supports a principled approach for deriving sharp non-asymptotic prophet inequalities for single threshold stopping rules. We demonstrate that sharp constants in the ratio- and difference-type prophet inequalities are determined by the optimal values of infinite two-person zero-sum game on the unit square with particular payoff kernels, while the the solutions to the game provide optimal stopping rules and least favorable distributions. Among other things, this formulation also allows a systematic way to tackle restricted classes of distributions. The proposed framework leads to a numerically efficient algorithmic paradigm that allows computing sharp constants in prophet inequalities with any prescribed level of accuracy. |
| title | Optimal single threshold stopping rules and sharp prophet inequalities |
| topic | Probability Computer Science and Game Theory Optimization and Control Statistics Theory 60G40, 62L12, 91A05 |
| url | https://arxiv.org/abs/2404.12949 |