pipette
ESEspañol

Mean-only Prophet Inequalities

Yilong Feng, Yaonan Jin, Xiaowei Wu, Xinyue Xiang

Preprint

In the authors' words

We study mean-based algorithms for single-choice prophet inequalities: the algorithm knows the number of variables and the mean of their maximum, but not their distributions. For arbitrary independent variables in a fixed order, we can already achieve the optimal competitive ratio using only this mean. For i.i.d. variables and prophet secretary, however, we previously knew only a guarantee, which is far away from the ratios with full distribution information. We improve the guarantees in both settings using a simple and natural algorithm: we fix a continuous decreasing threshold function that depends only on the mean and accept the first variable exceeding its threshold. For i.i.d. variables, we prove a competitive ratio. For the prophet secretary, we prove a competitive ratio.

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 50 pages