Prophet Inequality with Conservative Prediction
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914338928852992 |
|---|---|
| author | Brüstle, Johannes Cohen, Ilan Reuven Leonardi, Stefano |
| author_facet | Brüstle, Johannes Cohen, Ilan Reuven Leonardi, Stefano |
| contents | Prophet inequalities compare online stopping strategies against an omniscient "prophet" using distributional knowledge. In this work, we augment this model with a conservative prediction of the maximum realized value. We quantify the quality of this prediction using a parameter $α\in [0,1]$, ranging from inaccurate to perfect. Our goal is to improve performance when predictions are accurate (consistency) while maintaining theoretical guarantees when they are not (robustness). We propose a threshold-based strategy oblivious to $α$ (i.e., with $α$ unknown to the algorithm) that matches the classic competitive ratio of $1/2$ at $α=0$ and improves smoothly to $3/4$ at $α=1$. We further prove that simultaneously achieving better than $3/4$ at $α=1$ while maintaining $1/2$ at $α=0$ is impossible. Finally, when $α$ is known in advance, we present a strategy achieving a tight competitive ratio of $\frac{1}{2-α}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_17358 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Prophet Inequality with Conservative Prediction Brüstle, Johannes Cohen, Ilan Reuven Leonardi, Stefano Computer Science and Game Theory 68W27, 62L15, 60G40 Prophet inequalities compare online stopping strategies against an omniscient "prophet" using distributional knowledge. In this work, we augment this model with a conservative prediction of the maximum realized value. We quantify the quality of this prediction using a parameter $α\in [0,1]$, ranging from inaccurate to perfect. Our goal is to improve performance when predictions are accurate (consistency) while maintaining theoretical guarantees when they are not (robustness). We propose a threshold-based strategy oblivious to $α$ (i.e., with $α$ unknown to the algorithm) that matches the classic competitive ratio of $1/2$ at $α=0$ and improves smoothly to $3/4$ at $α=1$. We further prove that simultaneously achieving better than $3/4$ at $α=1$ while maintaining $1/2$ at $α=0$ is impossible. Finally, when $α$ is known in advance, we present a strategy achieving a tight competitive ratio of $\frac{1}{2-α}$. |
| title | Prophet Inequality with Conservative Prediction |
| topic | Computer Science and Game Theory 68W27, 62L15, 60G40 |
| url | https://arxiv.org/abs/2602.17358 |