research-article

Prophet Inequalities with Linear Correlations and Augmentations

Authors:

Nicole Immorlica,

Bo WaggonerAuthors Info & Claims

EC '20: Proceedings of the 21st ACM Conference on Economics and Computation

Pages 159 - 185

https://doi.org/10.1145/3391403.3399452

Published: 13 July 2020 Publication History

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.

References

[1]

Melika Abolhasani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghi HajiAghayi, Robert Kleinberg, and Brendan Lucier. 2017. Beating 1--1/e for ordered prophets. In Proceedings of STOC. ACM, 61--71.

Digital Library

[2]

Shipra Agrawal, Yichuan Ding, Amin Saberi, and Yinyu Ye. 2012. Price of correlations in stochastic optimization. Operations Research, Vol. 60, 1 (2012), 150--162.

Digital Library

[3]

Saeed Alaei. 2011. Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers. In Proceedings of FOCS.

Digital Library

[4]

Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahid Liaghat. 2012. Online prophet-inequality matching with applications to ad allocation. In Proceedings of EC. 18--35.

Digital Library

[5]

Pablo Daniel Azar, Robert Kleinberg, and S. Matthew Weinberg. 2014. Prophet Inequalities with Limited Information. In Proceedings of SODA.

[6]

Yossi Azar, Ashish Chiplunkar, and Haim Kaplan. 2018. Prophet Secretary: Surpassing the 1--1/e Barrier. In Proceedings of EC.

Digital Library

[7]

Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S Matthew Weinberg. 2014. A simple and approximately optimal mechanism for an additive buyer. In Proceedings of FOCS.

Digital Library

[8]

MohammadHossein Bateni, Sina Dehghani, MohammadTaghi Hajiaghayi, and Saeed Seddighin. 2015. Revenue maximization for selling multiple correlated items. In Algorithms-ESA 2015. Springer, 95--105.

[9]

Domagoj Bradac, Anupam Gupta, Sahil Singla, and Goran Zuzic. 2020. Robust Algorithms for the Secretary Problem. In 11th Innovations in Theoretical Computer Science Conference.

[10]

Moses Charikar, Jacob Steinhardt, and Gregory Valiant. 2017. Learning from untrusted data. In Proceedings of STOC.

Digital Library

[11]

Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. 2010. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of STOC.

[12]

Shuchi Chawla, David Malec, and Balasubramanian Sivan. 2015. The power of randomness in bayesian optimal mechanism design. Games and Economic Behavior, Vol. 91 (2015), 297--317.

[13]

José Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. 2017. Posted Price Mechanisms for a Random Stream of Customers. In Proceedings of EC. 169--186.

Digital Library

[14]

José R. Correa, Paul Dü tting, Felix A. Fischer, and Kevin Schewior. 2019 a. Prophet Inequalities for I.I.D. Random Variables from an Unknown Distribution. In Proceedings of EC. 3--17.

Digital Library

[15]

José R. Correa, Raimundo Saona, and Bruno Ziliotto. 2019 b. Prophet Secretary Through Blind Strategies. In Proceedings of SODA. 1946--1961.

[16]

Ilias Diakonikolas. 2018. Algorithmic High-Dimensional Robust Statistics. Webpage http://www.iliasdiakonikolas.org/simons-tutorial-robust.html. Tutorial at Foundations of Data Science bootcamp.

[17]

Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. 2016. Robust Estimators in High Dimensions without the Computational Intractability. In Proceedings of FOCS.

[18]

Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. 2018. Robustly Learning a Gaussian: Getting Optimal Error, Efficiently. In Proceedings of SODA. 2683--2702.

[19]

Paul Dütting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier. 2017. Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs. In Proceedings of FOCS. 540--551.

[20]

Paul Dü tting and Thomas Kesselheim. 2019. Posted Pricing and Prophet Inequalities with Inaccurate Priors. In Proceedings of EC. 111--129.

[21]

Soheil Ehsani, Mohammad Hajiaghayi, Thomas Kesselheim, and Sahil Singla. 2018. Prophet Secretary for Combinatorial Auctions and Matroids. In Proceedings of SODA.

[22]

Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Morteza Monemizadeh. 2017. Prophet secretary. SIAM Journal on Discrete Mathematics, Vol. 31, 3 (2017), 1685--1701.

Digital Library

[23]

Hossein Esfandiari, Nitish Korula, and Vahab Mirrokni. 2018. Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models. ACM Transactions on Economics and Computation (TEAC), Vol. 6, 3--4 (2018), 14.

[24]

Michal Feldman, Nick Gravin, and Brendan Lucier. 2015. Combinatorial auctions via posted prices. In Proceedings of SODA. 123--135.

[25]

Moran Feldman, Ola Svensson, and Rico Zenklusen. 2016. Online Contention Resolution Schemes. In Proceedings of SODA. 1014--1033.

[26]

Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, and Tuomas Sandholm. 2007. Automated Online Mechanism Design and Prophet Inequalities. In Proceedings of AAAI.

[27]

Theodore P Hill and Robert P Kertz. 1992. A survey of prophet inequalities in optimal stopping theory. Contemp. Math, Vol. 125 (1992), 191--207.

[28]

Kumar Joag-Dev and Frank Proschan. 1983. Negative association of random variables with applications. The Annals of Statistics (1983), 286--295.

[29]

Robert Kleinberg and S. Matthew Weinberg. 2012. Matroid prophet inequalities. In Proceedings of STOC. 123--136.

[30]

Ulrich Krengel and Louis Sucheston. 1978. On semiamarts, amarts, and processes with finite value. Advances in Prob, Vol. 4 (1978), 197--266.

[31]

Kevin A. Lai, Anup B. Rao, and Santosh Vempala. 2016. Agnostic Estimation of Mean and Covariance. In IEEE 57th Annual Symposium on Foundations of Computer Science.

[32]

Euiwoong Lee and Sahil Singla. 2018. Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities. In 26th Annual European Symposium on Algorithms, ESA.

[33]

Thodoris Lykouris, Vahab S. Mirrokni, and Renato Paes Leme. 2018. Stochastic bandits robust to adversarial corruptions. In Proceedings of STOC. 114--122.

Digital Library

[34]

Ankur Moitra. 2018. Robustness Meets Algorithms (Invited Talk). In 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018. 3:1--3:1.

[35]

Yosef Rinott and Ester Samuel-Cahn. 1991. Orderings of optimal stopping values and prophet inequalities for certain multivariate distributions. Journal of multivariate analysis, Vol. 37, 1 (1991).

Digital Library

[36]

Yosef Rinott and Ester Samuel-Cahn. 1992. Optimal stopping values and prophet inequalities for some dependent random variables. Lecture Notes-Monograph Series (1992), 343--358.

[37]

Yosef Rinott, Ester Samuel-Cahn, et al. 1987. Comparisons of optimal stopping values and prophet inequalities for negatively dependent random variables. The Annals of Statistics, Vol. 15, 4 (1987).

[38]

Aviad Rubinstein. 2016. Beyond matroids: secretary problem and prophet inequality with general constraints. In Proceedings of STOC. 324--332.

Digital Library

[39]

Aviad Rubinstein and Sahil Singla. 2017. Combinatorial prophet inequalities. In Proceedings of SODA. SIAM, 1671--1687.

[40]

Aviad Rubinstein, Jack Z. Wang, and S. Matthew Weinberg. 2020. Optimal Single-Choice Prophet Inequalities from Samples. In Proceedings of ITCS.

[41]

Ester Samuel-Cahn. 1984. Comparison of threshold stop rules and maximum for independent nonnegative random variables. the Annals of Probability (1984), 1213--1216.

[42]

Jan Vondrák. 2010. A note on concentration of submodular functions. arXiv:1005.2791 (2010).

[43]

Qiqi Yan. 2011. Mechanism design via correlation gap. In Proceedings of SODA.

Cited By

Ekbatani FNiazadeh RNuti PVondrák JMohar BShinkar IO'Donnell R(2024)Prophet Inequalities with Cancellation CostsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649786(1247-1258)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649786
Dughmi SKalayci YPatel NMohar BShinkar IO'Donnell R(2024)Limitations of Stochastic Selection Problems with Pairwise Independent PriorsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649718(479-490)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649718
Gupta AHu JKehne GLevin R(2024)Pairwise-Independent Contention ResolutionInteger Programming and Combinatorial Optimization10.1007/978-3-031-59835-7_15(196-209)Online publication date: 22-May-2024
https://doi.org/10.1007/978-3-031-59835-7_15
Show More Cited By

Index Terms

Prophet Inequalities with Linear Correlations and Augmentations
1. Theory of computation
  1. Design and analysis of algorithms
    1. Online algorithms
  2. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design
      1. Algorithmic mechanism design

Recommendations

Prophet Inequalities with Linear Correlations and Augmentations
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 ...
Prophet Inequalities over Time
EC '23: Proceedings of the 24th ACM Conference on Economics and Computation

In this paper, we introduce an over-time variant of the well-known prophet inequality with i.i.d. random variables. Instead of stopping with one realized value at some point in the process, we decide for each step how long we select the value. Then we ...
Online prophet-inequality matching with applications to ad allocation
EC '12: Proceedings of the 13th ACM Conference on Electronic Commerce

We study the problem of online prophet-inequality matching in bipartite graphs. There is a static set of bidders and an online stream of items. We represent the interest of bidders in items by a weighted bipartite graph. Each bidder has a capacity, i.e.,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '20: Proceedings of the 21st ACM Conference on Economics and Computation

July 2020

937 pages

ISBN:9781450379755

DOI:10.1145/3391403

General Chairs:
Péter Biró
Hungarian Academy of Sciences
,
Jason Hartline
Northwestern University
,
Program Chairs:
Michael Ostrovsky
Stanford University
,
Ariel Procaccia
Harvard University

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Schmidt Foundation

Conference

EC '20

Sponsor:

SIGecom

EC '20: The 21st ACM Conference on Economics and Computation

July 13 - 17, 2020

Virtual Event, Hungary

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
171
Total Downloads

Downloads (Last 12 months)44
Downloads (Last 6 weeks)2

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ekbatani FNiazadeh RNuti PVondrák JMohar BShinkar IO'Donnell R(2024)Prophet Inequalities with Cancellation CostsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649786(1247-1258)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649786
Dughmi SKalayci YPatel NMohar BShinkar IO'Donnell R(2024)Limitations of Stochastic Selection Problems with Pairwise Independent PriorsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649718(479-490)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649718
Gupta AHu JKehne GLevin R(2024)Pairwise-Independent Contention ResolutionInteger Programming and Combinatorial Optimization10.1007/978-3-031-59835-7_15(196-209)Online publication date: 22-May-2024
https://doi.org/10.1007/978-3-031-59835-7_15
Amouzandeh ASchmitt Svan Stee R(2023)SIGACT News Online Algorithms Column 40ACM SIGACT News10.1145/3586165.358617754:1(90-104)Online publication date: 28-Feb-2023
https://dl.acm.org/doi/10.1145/3586165.3586177
Caragiannis IGravin NLu PWang Z(2022)Relaxing the Independence Assumption in Sequential Posted Pricing, Prophet Inequality, and Random Bipartite MatchingWeb and Internet Economics10.1007/978-3-030-94676-0_8(131-148)Online publication date: 1-Jan-2022
https://doi.org/10.1007/978-3-030-94676-0_8
Manshadi VNiazadeh RRodilitz S(undefined)Fair Dynamic RationingSSRN Electronic Journal10.2139/ssrn.3775895
https://doi.org/10.2139/ssrn.3775895

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents