  Prophet inequalities are a central object of study in optimal stopping
theory. A gambler is sent values in an online fashion, 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$ is attainable for any instance. Recently, this has been improved up to
$0.7258$ by Bubna and Chiplunkar (2023). 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. Through simulations, Bubna and Chiplunkar (2023) also showed that
this ratio is 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,
non-simulation-assisted 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.
