Document Open Access Logo

Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities

Authors Euiwoong Lee, Sahil Singla

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.57.pdf
  • Filesize: 489 kB
  • 14 pages

Document Identifiers

Author Details

Euiwoong Lee
  • Courant Institute of Mathematical Sciences, New York University, New York City, USA
Sahil Singla
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, USA

Cite As Get BibTex

Euiwoong Lee and Sahil Singla. Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.57

Abstract

Online contention resolution schemes (OCRSs) were proposed by Feldman, Svensson, and Zenklusen [Moran Feldman et al., 2016] as a generic technique to round a fractional solution in the matroid polytope in an online fashion. It has found applications in several stochastic combinatorial problems where there is a commitment constraint: on seeing the value of a stochastic element, the algorithm has to immediately and irrevocably decide whether to select it while always maintaining an independent set in the matroid. Although OCRSs immediately lead to prophet inequalities, these prophet inequalities are not optimal. Can we instead use prophet inequalities to design optimal OCRSs?
We design the first optimal 1/2-OCRS for matroids by reducing the problem to designing a matroid prophet inequality where we compare to the stronger benchmark of an ex-ante relaxation. We also introduce and design optimal (1-1/e)-random order CRSs for matroids, which are similar to OCRSs but the arrival order is chosen uniformly at random.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Prophets
  • Contention Resolution
  • Stochastic Optimization
  • Matroids

Metrics

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

Related Versions

References

  1. Marek Adamczyk and Michal Wlodarczyk. Random order contention resolution schemes. CoRR, abs/1804.02584, 2018. Google Scholar
  2. Shipra Agrawal, Yichuan Ding, Amin Saberi, and Yinyu Ye. Price of correlations in stochastic optimization. Operations Research, 60(1):150-162, 2012. Preliminary version in SODA 2010. Google Scholar
  3. Saeed Alaei. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 512-521, 2011. Google Scholar
  4. Saeed Alaei. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM Journal on Computing, 43(2):930-972, 2014. Google Scholar
  5. 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. Google Scholar
  6. Gruia Călinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput., 40(6):1740-1766, 2011. Google Scholar
  7. Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 311-320, 2010. Google Scholar
  8. Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput., 43(6):1831-1879, 2014. Google Scholar
  9. Soheil Ehsani, Mohammad 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. SIAM, 2018. Google Scholar
  10. Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Morteza Monemizadeh. Prophet secretary. SIAM Journal on Discrete Mathematics, 31(3):1685-1701, 2017. Google Scholar
  11. 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. Google Scholar
  12. Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169-197, 1981. Google Scholar
  13. Sudipto Guha and Kamesh Munagala. Approximation algorithms for budgeted learning problems. In STOC, pages 104-113. ACM, 2007. Full version as: Approximation Algorithms for Bayesian Multi-Armed Bandit Problems, URL: http://arxiv.org/abs/1306.3525.
  14. Anupam Gupta, Haotian Jiang, Ziv Scully, and Sahil Singla. The markovian price of information, 2018. Google Scholar
  15. Anupam Gupta and Viswanath Nagarajan. A stochastic probing problem with applications. In Integer Programming and Combinatorial Optimization - 16th International Conference, IPCO 2013, Valparaíso, Chile, March 18-20, 2013. Proceedings, pages 205-216, 2013. Google Scholar
  16. Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Algorithms and adaptivity gaps for stochastic probing. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1731-1747. SIAM, 2016. Google Scholar
  17. Guru Guruganesh and Euiwoong Lee. Understanding the Correlation Gap For Matchings. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017), volume 93 of Leibniz International Proceedings in Informatics (LIPIcs), pages 32:1-32:15, 2018. Google Scholar
  18. Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, and Tuomas Sandholm. Automated online mechanism design and prophet inequalities. In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, July 22-26, 2007, Vancouver, British Columbia, Canada, pages 58-65, 2007. Google Scholar
  19. Theodore P Hill and Robert P Kertz. A survey of prophet inequalities in optimal stopping theory. Contemp. Math, 125:191-207, 1992. Google Scholar
  20. 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. Google Scholar
  21. Ulrich Krengel and Louis Sucheston. Semiamarts and finite values. Bull. Am. Math. Soc, 1977. Google Scholar
  22. Ulrich Krengel and Louis Sucheston. On semiamarts, amarts, and processes with finite value. Advances in Prob, 4:197-266, 1978. Google Scholar
  23. Brendan Lucier and Allan Borodin. Price of anarchy for greedy auctions. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 537-553. Society for Industrial and Applied Mathematics, 2010. Google Scholar
  24. 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. Google Scholar
  25. Aviad Rubinstein and Sahil Singla. Combinatorial prophet inequalities. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1671-1687. SIAM, 2017. Google Scholar
  26. Qiqi Yan. Mechanism design via correlation gap. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 710-719. Society for Industrial and Applied Mathematics, 2011. 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 About DROPS Imprint Privacy Contact