TY - GEN

T1 - Prophet Inequalities with Linear Correlations and Augmentations

AU - Immorlica, Nicole

AU - Singla, Sahil

AU - Waggoner, Bo

N1 - Funding Information:
S. S. was supported in part by the Schmidt Foundation. We are thankful to the anonymous reviewers of EC 2020 for helpful comments on improving the presentation of this paper.
Publisher Copyright:
© 2020 ACM.

PY - 2020/7/13

Y1 - 2020/7/13

N2 - 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'15] as a generalization of the common-base value model of Chawla et al. [GEB'15]. 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.

AB - 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'15] as a generalization of the common-base value model of Chawla et al. [GEB'15]. 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.

KW - online algorithms

KW - posted price mechanisms

KW - robust stopping time algorithms

UR - http://www.scopus.com/inward/record.url?scp=85089265746&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85089265746&partnerID=8YFLogxK

U2 - 10.1145/3391403.3399452

DO - 10.1145/3391403.3399452

M3 - Conference contribution

AN - SCOPUS:85089265746

T3 - EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation

SP - 159

EP - 185

BT - EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation

PB - Association for Computing Machinery

T2 - 21st ACM Conference on Economics and Computation, EC 2020

Y2 - 13 July 2020 through 17 July 2020

ER -