  There is a rising interest for studying the online benchmark as an
alternative of the classical offline benchmark in online stochastic settings.
Ezra, Feldman, Gravin, and Tang (SODA 2023) introduced the notion of
order-competitive ratio, defined as the worst-case ratio between the
performance of the best order-unaware algorithm and the best order-aware
algorithm, to quantify the loss incurred by the lack of knowledge of the
arrival order. They showed in the online single selection setting (a.k.a. the
prophet problem), the optimal order-competitive ratio achieved by deterministic
algorithms is $1/\varphi \approx 0.618$, and left with an open question whether
randomized algorithms can do better.
  We answer the open question firmly by introducing a novel family of
algorithms called \emph{targeted value algorithms}. We show that the task of
online selection is as easy as guessing the optimal online benchmark.
Specifically, we provide 1) an alternative optimal $1/\varphi$
order-competitive algorithm by setting the targeted value deterministically,
and 2) a $0.732$ order-competitive algorithm by setting the targeted value
randomly. We further provide a $0.758$ upper bound on the order-competitive
ratio of our algorithm, showing that our analysis is close to the best
possible, and establish an upper bound of $0.829$ on the order-competitive
ratio for general randomized order-unaware algorithms.
