---
_id: '17100'
abstract:
- lang: eng
  text: "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.\r\nThe 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."
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'
article_processing_charge: No
arxiv: 1
author:
- first_name: Giordano
  full_name: Giambartolomei, Giordano
  last_name: Giambartolomei
- first_name: Frederik Mallmann-Trenn
  full_name: Frederik Mallmann-Trenn, Frederik Mallmann-Trenn
  last_name: Frederik Mallmann-Trenn
- first_name: Raimundo J
  full_name: Saona Urmeneta, Raimundo J
  id: BD1DF4C4-D767-11E9-B658-BC13E6697425
  last_name: Saona Urmeneta
  orcid: 0000-0001-5103-038X
citation:
  ama: 'Giambartolomei G, Frederik Mallmann-Trenn FM-T, Saona Urmeneta RJ. Prophet
    inequalities: Separating random order from order selection. <i>arXiv</i>. doi:<a
    href="https://doi.org/10.48550/arXiv.2304.04024">10.48550/arXiv.2304.04024</a>'
  apa: 'Giambartolomei, G., Frederik Mallmann-Trenn, F. M.-T., &#38; Saona Urmeneta,
    R. J. (n.d.). Prophet inequalities: Separating random order from order selection.
    <i>arXiv</i>. <a href="https://doi.org/10.48550/arXiv.2304.04024">https://doi.org/10.48550/arXiv.2304.04024</a>'
  chicago: 'Giambartolomei, Giordano, Frederik Mallmann-Trenn Frederik Mallmann-Trenn,
    and Raimundo J Saona Urmeneta. “Prophet Inequalities: Separating Random Order
    from Order Selection.” <i>ArXiv</i>, n.d. <a href="https://doi.org/10.48550/arXiv.2304.04024">https://doi.org/10.48550/arXiv.2304.04024</a>.'
  ieee: 'G. Giambartolomei, F. M.-T. Frederik Mallmann-Trenn, and R. J. Saona Urmeneta,
    “Prophet inequalities: Separating random order from order selection,” <i>arXiv</i>.
    .'
  ista: 'Giambartolomei G, Frederik Mallmann-Trenn FM-T, Saona Urmeneta RJ. Prophet
    inequalities: Separating random order from order selection. arXiv, 2304.04024.'
  mla: 'Giambartolomei, Giordano, et al. “Prophet Inequalities: Separating Random
    Order from Order Selection.” <i>ArXiv</i>, 2304.04024, doi:<a href="https://doi.org/10.48550/arXiv.2304.04024">10.48550/arXiv.2304.04024</a>.'
  short: G. Giambartolomei, F.M.-T. Frederik Mallmann-Trenn, R.J. Saona Urmeneta,
    ArXiv (n.d.).
date_created: 2024-06-03T07:44:54Z
date_published: 2023-04-08T00:00:00Z
date_updated: 2025-04-14T07:52:47Z
day: '08'
department:
- _id: KrCh
doi: 10.48550/arXiv.2304.04024
ec_funded: 1
external_id:
  arxiv:
  - '2304.04024'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2304.04024
month: '04'
oa: 1
oa_version: Preprint
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: arXiv
publication_status: submitted
status: public
title: 'Prophet inequalities: Separating random order from order selection'
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...