Prophet inequalities: Separating random order from order selection

Giambartolomei G, Frederik Mallmann-Trenn FM-T, Saona Urmeneta RJ. Prophet inequalities: Separating random order from order selection. arXiv, 2304.04024.

Download (ext.)

Preprint | Submitted | English
Author
Giambartolomei, Giordano; Frederik Mallmann-Trenn, Frederik Mallmann-Trenn; Saona, RaimundoISTA
Department
Abstract
Prophet inequalities are a central object of study in optimal stopping theory. A gambler is sent values online, sampled from an instance of independent distributions, in an adversarial, random or selected order, depending on the model. When observing each value, the gambler either accepts it as a reward or irrevocably rejects it and proceeds to observe the next value. The goal of the gambler, who cannot see the future, is maximising the expected value of the reward while competing against the expectation of a prophet (the offline maximum). In other words, one seeks to maximise the gambler-to-prophet ratio of the expectations. The model, in which the gambler selects the arrival order first, and then observes the values, is known as Order Selection. In this model a ratio of 0.7251 has been proved to be attainable for any instance. In very recent work, this has been improved up to 0.7258. If the gambler chooses the arrival order (uniformly) at random, we obtain the Random Order model. The worst case ratio over all possible instances has been extensively studied for at least 40 years. In the recent work aforementioned, through simulations, this ratio has been shown to be at most 0.7254 for the Random Order model, thus establishing for the first time that carefully choosing the order, instead of simply taking it at random, benefits the gambler. We give an alternative, more rigorous proof of this fact, by showing mathematically that in the Random Order model, no algorithm can achieve a ratio larger than 0.7235. This sets a new state-of-the-art hardness for this model, and establishes more formally that there is a real benefit in choosing the order.
Publishing Year
Date Published
2023-04-08
Journal Title
arXiv
Acknowledgement
This research was partially supported by the EPSRC grant EP/W005573/1, the ERC CoG 863818 (ForM-SMArt) grant, and the ANID Chile grant ACT210005. We would like to thank Jos´e Correa and Bruno Zilotto for their precious advice, and Mona Mohammadi and Roodabeh Safavi for early conversations.
Article Number
2304.04024
IST-REx-ID

Cite this

Giambartolomei G, Frederik Mallmann-Trenn FM-T, Saona Urmeneta RJ. Prophet inequalities: Separating random order from order selection. arXiv. doi:10.48550/arXiv.2304.04024
Giambartolomei, G., Frederik Mallmann-Trenn, F. M.-T., & Saona Urmeneta, R. J. (n.d.). Prophet inequalities: Separating random order from order selection. arXiv. https://doi.org/10.48550/arXiv.2304.04024
Giambartolomei, Giordano, Frederik Mallmann-Trenn Frederik Mallmann-Trenn, and Raimundo J Saona Urmeneta. “Prophet Inequalities: Separating Random Order from Order Selection.” ArXiv, n.d. https://doi.org/10.48550/arXiv.2304.04024.
G. Giambartolomei, F. M.-T. Frederik Mallmann-Trenn, and R. J. Saona Urmeneta, “Prophet inequalities: Separating random order from order selection,” arXiv. .
Giambartolomei G, Frederik Mallmann-Trenn FM-T, Saona Urmeneta RJ. Prophet inequalities: Separating random order from order selection. arXiv, 2304.04024.
Giambartolomei, Giordano, et al. “Prophet Inequalities: Separating Random Order from Order Selection.” ArXiv, 2304.04024, doi:10.48550/arXiv.2304.04024.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2304.04024

Search this title in

Google Scholar