  In the prophet inequality problem, a gambler faces a sequence of items
arriving online with values drawn independently from known distributions. On
seeing an item, the gambler must choose whether to accept its value as her
reward and quit the game, or reject it and continue. The gambler's aim is to
maximize her expected reward relative to the expected maximum of the values of
all items. Since the seventies, a tight bound of 1/2 has been known for this
competitive ratio in the setting where the items arrive in an adversarial order
(Krengel and Sucheston, 1977, 1978). However, the optimum ratio still remains
unknown in the order selection setting, where the gambler selects the arrival
order, as well as in prophet secretary, where the items arrive in a random
order. Moreover, it is not even known whether a separation exists between the
two settings.
  In this paper, we show that the power of order selection allows the gambler
to guarantee a strictly better competitive ratio than if the items arrive
randomly. For the order selection setting, we identify an instance for which
Peng and Tang's (FOCS'22) state-of-the-art algorithm performs no better than
their claimed competitive ratio of (approximately) 0.7251, thus illustrating
the need for an improved approach. We therefore extend their design and provide
a more general algorithm design framework, using which we show that their ratio
can be beaten, by designing a 0.7258-competitive algorithm. For the random
order setting, we improve upon Correa, Saona and Ziliotto's (SODA'19)
0.732-hardness result to show a hardness of 0.7254 for general algorithms -
even in the setting where the gambler knows the arrival order beforehand, thus
establishing a separation between the order selection and random order
settings.
