# The Competition Complexity of Prophet Inequalities with Correlations

arXiv: https://arxiv.org/abs/2409.06868 · HTML: https://mlsanity.com/paper/2409.06868/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 50 references that are in the map.
- First posted on arXiv 10 Sep 2024.

## Builds on (most cited first, 27 of 27)

- [Prophet Inequalities with Limited Information](https://mlsanity.com/paper/1307.3736/) (2013)
- [Combinatorial Auctions via Posted Prices](https://mlsanity.com/paper/1411.4916/) (2014)
- [Prophet Secretary](https://mlsanity.com/paper/1507.01155/) (2015)
- [Online Contention Resolution Schemes](https://mlsanity.com/paper/1508.00142/) (2015)
- [Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs](https://mlsanity.com/paper/1612.03161/) (2016)
- [Prophet Secretary: Surpassing the 1-1/e Barrier](https://mlsanity.com/paper/1711.01834/) (2017)
- [Prophet Secretary for Combinatorial Auctions and Matroids](https://mlsanity.com/paper/1710.11213/) (2017)
- [Improved Revenue Bounds for Posted-Price and Second-Price Mechanisms](https://mlsanity.com/paper/1807.03435/) (2018)
- [Prophet Secretary Through Blind Strategies](https://mlsanity.com/paper/1807.07483/) (2018)
- [Prophet inequality for bipartite matching: merits of being simple and non adaptive](https://mlsanity.com/paper/1902.06243/) (2019)
- [Prophet Inequalities with Linear Correlations and Augmentations](https://mlsanity.com/paper/2001.10600/) (2020)
- [An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions](https://mlsanity.com/paper/2004.09784/) (2020)
- [Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities](https://mlsanity.com/paper/2102.10261/) (2021)
- [Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design](https://mlsanity.com/paper/2204.01425/) (2022)
- [Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark](https://mlsanity.com/paper/2206.01270/) (2022)
- [Beyond matroids: Secretary Problem and Prophet Inequality with general constraints](https://mlsanity.com/paper/1604.00357/) (2016)
- [Polymatroid Prophet Inequalities](https://mlsanity.com/paper/1307.5299/) (2013)
- [Prophets and Secretaries with Overbooking](https://mlsanity.com/paper/1805.05094/) (2018)
- [On Simple Mechanisms for Dependent Items](https://mlsanity.com/paper/2106.10814/) (2021)
- [The Stationary Prophet Inequality Problem](https://mlsanity.com/paper/2107.10516/) (2021)
- ["Who Is Next in Line?'' On the Significance of Knowing the Arrival Order in Bayesian Online Settings](https://mlsanity.com/paper/2202.09215/) (2022)
- [Prophet Inequalities via the Expected Competitive Ratio](https://mlsanity.com/paper/2207.03361/) (2022)
- [The Importance of Knowing the Arrival Order in Combinatorial Bayesian Settings](https://mlsanity.com/paper/2307.02610/) (2023)
- [The Competition Complexity of Prophet Inequalities](https://mlsanity.com/paper/2402.11084/) (2024)
- [Choosing Behind the Veil: Tight Bounds for Identity-Blind Online Algorithms](https://mlsanity.com/paper/2402.17160/) (2024)
- [Improved Mechanisms and Prophet Inequalities for Graphical Dependencies](https://mlsanity.com/paper/2406.05077/) (2024)
- [New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling](https://mlsanity.com/paper/2407.15285/) (2024)

## Abstract (arXiv)

We initiate the study of the prophet inequality problem through the resource augmentation framework in scenarios when the values of the rewards are correlated. Our goal is to determine the number of additional rewards an online algorithm requires to approximate the maximum value of the original instance. While the independent reward case is well understood, we extend this research to account for correlations among rewards. Our results demonstrate that, unlike in the independent case, the required number of additional rewards for approximation depends on the number of original rewards, and that block-threshold algorithms, which are optimal in the independent case, may require 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 the original instance; (2) where rewards across all copies are arbitrarily shuffled; and (3) where rewards arrive in blocks corresponding to the different copies of the original instance, and values within each block are pairwise independent rather than fully correlated.