Prophet Inequalities with Linear Correlations and Augmentations

Nicole Immorlica, Sahil Singla, Bo Waggoner

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationEC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages159-185
Number of pages27
ISBN (Electronic)9781450379755
DOIs
StatePublished - Jul 13 2020
Event21st ACM Conference on Economics and Computation, EC 2020 - Virtual, Online, Hungary
Duration: Jul 13 2020Jul 17 2020

Publication series

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

Conference

Conference21st ACM Conference on Economics and Computation, EC 2020
CountryHungary
CityVirtual, Online
Period7/13/207/17/20

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Economics and Econometrics
  • Statistics and Probability
  • Computational Mathematics

Keywords

  • online algorithms
  • posted price mechanisms
  • robust stopping time algorithms

Fingerprint Dive into the research topics of 'Prophet Inequalities with Linear Correlations and Augmentations'. Together they form a unique fingerprint.

  • Cite this

    Immorlica, N., Singla, S., & Waggoner, B. (2020). Prophet Inequalities with Linear Correlations and Augmentations. In EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation (pp. 159-185). [3399452] (EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation). Association for Computing Machinery, Inc. https://doi.org/10.1145/3391403.3399452