  In a classical online decision problem, a decision-maker who is trying to
maximize her value inspects a sequence of arriving items to learn their values
(drawn from known distributions), and decides when to stop the process by
taking the current item. The goal is to prove a "prophet inequality": that she
can do approximately as well as a prophet with foreknowledge of all the values.
In this work, we investigate this problem when the values are allowed to be
correlated. Since non-trivial guarantees are impossible for arbitrary
correlations, we consider a natural "linear" correlation structure introduced
by Bateni et al. [ESA 2015] as a generalization of the common-base value model
of Chawla et al. [GEB 2015].
  A key challenge is that threshold-based algorithms, which are commonly used
for prophet inequalities, no longer guarantee good performance for linear
correlations. We relate this roadblock to another "augmentations" challenge
that might be of independent interest: many existing prophet inequality
algorithms are not robust to slight increase in the values of the arriving
items. We leverage this intuition to prove bounds (matching up to constant
factors) that decay gracefully with the amount of correlation of the arriving
items. We extend these results to the case of selecting multiple items by
designing a new $(1+o(1))$ approximation ratio algorithm that is robust to
augmentations.
