Optimal single-choice prophet inequalities from samples. (English) Zbl 07650408
Vidick, Thomas (ed.), 11th innovations in theoretical computer science conference, ITCS 2020, Seattle, Washington, USA, January 12–14, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 151, Article 60, 10 p. (2020).
Summary: We study the single-choice Prophet Inequality problem when the gambler is given access to samples. We show that the optimal competitive ratio of \(1/2\) can be achieved with a single sample from each distribution. When the distributions are identical, we show that for any constant \(\varepsilon>0\), \(O(n)\) samples from the distribution suffice to achieve the optimal competitive ratio \((\approx 0.745)\) within \((1+\varepsilon)\), resolving an open problem by [J. Correa et al., Math. Oper. Res. 47, No. 2, 1287–1309 (2022; Zbl 1493.62492)].
For the entire collection see [Zbl 1434.68035].
For the entire collection see [Zbl 1434.68035].
MSC:
| 68Qxx | Theory of computing |
