  We introduce a new measure for the performance of online algorithms in
Bayesian settings, where the input is drawn from a known prior, but the
realizations are revealed one-by-one in an online fashion. Our new measure is
called order-competitive ratio. It is defined as the worst case (over all
distribution sequences) ratio between the performance of the best order-unaware
and order-aware algorithms, and quantifies the loss that is incurred due to
lack of knowledge of the arrival order. Despite the growing interest in the
role of the arrival order on the performance of online algorithms, this loss
has been overlooked thus far.
  We study the order-competitive ratio in the paradigmatic prophet inequality
problem, for the two common objective functions of (i) maximizing the expected
value, and (ii) maximizing the probability of obtaining the largest value; and
with respect to two families of algorithms, namely (i) adaptive algorithms, and
(ii) single-threshold algorithms. We provide tight bounds for all four
combinations, with respect to deterministic algorithms. Our analysis requires
new ideas and departs from standard techniques. In particular, our adaptive
algorithms inevitably go beyond single-threshold algorithms. The results with
respect to the order-competitive ratio measure capture the intuition that
adaptive algorithms are stronger than single-threshold ones, and may lead to a
better algorithmic advice than the classical competitive ratio measure.
