pipette
ENEnglish

Mean-only Prophet Inequalities

Yilong Feng, Yaonan Jin, Xiaowei Wu, Xinyue Xiang

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 50 pages