Abstract
We initiate the study of the prophet inequality problem through the resourceaugmentation framework in scenarios when the values of the rewards arecorrelated. Our goal is to determine the number of additional rewards an onlinealgorithm requires to approximate the maximum value of the original instance.While the independent reward case is well understood, we extend this researchto account for correlations among rewards. Our results demonstrate that, unlikein the independent case, the required number of additional rewards forapproximation depends on the number of original rewards, and thatblock-threshold algorithms, which are optimal in the independent case, mayrequire an infinite number of additional rewards when correlations are present.We develop asymptotically optimal algorithms for the following three scenarios:(1) where rewards arrive in blocks corresponding to the different copies of theoriginal instance; (2) where rewards across all copies are arbitrarilyshuffled; and (3) where rewards arrive in blocks corresponding to the differentcopies of the original instance, and values within each block are pairwiseindependent rather than fully correlated.