  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.
