Document Open Access Logo

Optimal Single-Choice Prophet Inequalities from Samples

Authors Aviad Rubinstein, Jack Z. Wang, S. Matthew Weinberg

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.60.pdf
  • Filesize: 458 kB
  • 10 pages

Document Identifiers

Author Details

Aviad Rubinstein
  • Stanford University, Stanford, CA, USA
Jack Z. Wang
  • Cornell University, Ithaca, NY, USA
S. Matthew Weinberg
  • Princeton University, Princeton, NJ, USA

Funding

  • Weinberg, S. Matthew: Supported by NSF CCF-1717899.

Cite AsGet BibTex

Aviad Rubinstein, Jack Z. Wang, and S. Matthew Weinberg. Optimal Single-Choice Prophet Inequalities from Samples. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 60:1-60:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.60

Abstract

We study the single-choice Prophet Inequality problem when the gambler is given access to samples. We show that the optimal competitive ratio of 1/2 can be achieved with a single sample from each distribution. When the distributions are identical, we show that for any constant ε > 0, O(n) samples from the distribution suffice to achieve the optimal competitive ratio (≈ 0.745) within (1+ε), resolving an open problem of [José R. Correa et al., 2019].

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Online algorithms
  • Probability
  • Optimization
  • Prophet inequalities
  • Samples
  • Auctions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Robert D. Kleinberg, and Brendan Lucier. Beating 1-1/e for ordered prophets. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 61-71, 2017. URL: https://doi.org/10.1145/3055399.3055479.
  2. Marek Adamczyk and Michal Wlodarczyk. Random Order Contention Resolution Schemes. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 790-801, 2018. URL: https://doi.org/10.1109/FOCS.2018.00080.
  3. Saeed Alaei. Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers. In the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 512-521, 2011. URL: https://doi.org/10.1109/FOCS.2011.90.
  4. Nima Anari, Rad Niazadeh, Amin Saberi, and Ali Shameli. Nearly Optimal Pricing Algorithms for Production Constrained and Laminar Bayesian Selection. In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019., pages 91-92, 2019. URL: https://doi.org/10.1145/3328526.3329652.
  5. Pablo Daniel Azar, Robert Kleinberg, and S. Matthew Weinberg. Prophet Inequalities with Limited Information. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1358-1377, 2014. URL: https://doi.org/10.1137/1.9781611973402.100.
  6. Yossi Azar, Ashish Chiplunkar, and Haim Kaplan. Prophet Secretary: Surpassing the 1-1/e Barrier. In Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, pages 303-318, 2018. URL: https://doi.org/10.1145/3219166.3219182.
  7. Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multi-Parameter Mechanism Design and Sequential Posted Pricing. In the 42nd ACM Symposium on Theory of Computing (STOC), 2010. Google Scholar
  8. Shuchi Chawla, J. Benjamin Miller, and Yifeng Teng. Pricing for Online Resource Allocation: Intervals and Paths. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1962-1981, 2019. URL: https://doi.org/10.1137/1.9781611975482.119.
  9. José R. Correa, Paul Dütting, Felix A. Fischer, and Kevin Schewior. Prophet Inequalities for I.I.D. Random Variables from an Unknown Distribution. In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019., pages 3-17, 2019. URL: https://doi.org/10.1145/3328526.3329627.
  10. José R. Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. Posted Price Mechanisms for a Random Stream of Customers. In Constantinos Daskalakis, Moshe Babaioff, and Hervé Moulin, editors, Proceedings of the 2017 ACM Conference on Economics and Computation, EC '17, Cambridge, MA, USA, June 26-30, 2017, pages 169-186. ACM, 2017. URL: https://doi.org/10.1145/3033274.3085137.
  11. José R. Correa, Raimundo Saona, and Bruno Ziliotto. Prophet Secretary Through Blind Strategies. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1946-1961, 2019. URL: https://doi.org/10.1137/1.9781611975482.118.
  12. Paul Duetting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier. Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 540-551, 2017. URL: https://doi.org/10.1109/FOCS.2017.56.
  13. Paul Dütting and Thomas Kesselheim. Posted Pricing and Prophet Inequalities with Inaccurate Priors. In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019., pages 111-129, 2019. URL: https://doi.org/10.1145/3328526.3329576.
  14. Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, and Sahil Singla. Prophet Secretary for Combinatorial Auctions and Matroids. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 700-714, 2018. URL: https://doi.org/10.1137/1.9781611975031.46.
  15. Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Morteza Monemizadeh. Prophet Secretary. In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 496-508, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_42.
  16. Moran Feldman, Ola Svensson, and Rico Zenklusen. Online Contention Resolution Schemes. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1014-1033, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch72.
  17. Oliver Göbel, Martin Hoefer, Thomas Kesselheim, Thomas Schleiden, and Berthold Vöcking. Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, pages 508-519, 2014. URL: https://doi.org/10.1007/978-3-662-43951-7_43.
  18. Nikolai Gravin and Hongao Wang. Prophet Inequality for Bipartite Matching: Merits of Being Simple and Non Adaptive. In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019., pages 93-109, 2019. URL: https://doi.org/10.1145/3328526.3329604.
  19. Theodore P. Hill and Robert P. Kertz. Comparisons of stop rule and supremum expectations of i.i.d. random variables. The Annals of Probability, 10:336-345, 1982. Google Scholar
  20. Robert P. Kertz. Stop rule and supremum expectations of i.i.d. random variables: a complete comparison by conjugate duality. Journal of Multivariate Analysis, 19:88-112, 1986. Google Scholar
  21. Robert Kleinberg and S. Matthew Weinberg. Matroid prophet inequalities. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 123-136, 2012. URL: https://doi.org/10.1145/2213977.2213991.
  22. Ulrich Krengel and Louis Sucheston. On Semiamarts, amarts, and processes with finite value. Advances in Probability and Related Topics, 4:197-266, 1978. Google Scholar
  23. Aviad Rubinstein. Beyond matroids: secretary problem and prophet inequality with general constraints. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 324-332, 2016. URL: https://doi.org/10.1145/2897518.2897540.
  24. Aviad Rubinstein and Sahil Singla. Combinatorial Prophet Inequalities. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1671-1687, 2017. URL: https://doi.org/10.1137/1.9781611974782.110.
  25. Ester Samuel-Cahn. Comparison of threshold stop rules and maximum for independent nonnegative random variables. Annals of Probability, 12(4):1213-1216, 1984. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact