[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3465456.3467598acmconferencesArticle/Chapter ViewAbstractPublication PagesecConference Proceedingsconference-collections
extended-abstract

Variable Decomposition for Prophet Inequalities and Optimal Ordering

Published: 18 July 2021 Publication History

Abstract

We introduce a new decomposition technique for random variables that maps a generic instance of the prophet inequalities problem to a new instance where all but a constant number of variables have a tractable structure that we refer to as (ε, δ)-smallness. Using this technique, we make progress on several outstanding problems in the area: We show that, even in the case of non-identical distributions, it is possible to achieve (arbitrarily close to) the optimal approximation ratio of β ~0.745 when the items arrive in a random order (this version is commonly known as prophet secretary) as long as we are allowed to remove a small constant number of distributions. We show that forfrequent instances (where each distribution reoccurs some number of times) and random arrival order, it is possible to achieve the optimal approximation ratio of β (improving over the previous best-known bound of 0.738). We give a new, simpler proof of Kertz's optimal approximation guarantee of β ~0.745 for prophet inequalities with i.i.d. distributions. The proof is primal-dual and simultaneously produces upper and lower bounds. Using this decomposition in combination with a novel convex programming formulation, we construct the first (in parallel work with[1]) an Efficient PTAS (EPTAS) for the Optimal Ordering problem.

References

[1]
Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Robert D. Kleinberg, and Brendan Lucier. 2017. 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. 61--71.
[2]
Shipra Agrawal, Jay Sethuraman, and Xingyu Zhang. 2020. On optimal ordering in the optimal stopping problem. In Proceedings of the 21st ACM Conference on Economics and Computation. 187--188.
[3]
Yossi Azar, Ashish Chiplunkar, and Haim Kaplan. 2018. 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. 303--318.
[4]
Hedyeh Beyhaghi, Negin Golrezaei, Renato Paes Leme, Martin Pal, and Balasubramanian Sivan. 2018. Improved Approximations for Free-Order Prophets and Second-Price Auctions. CoRR, Vol. abs/1807.03435 (2018). arxiv: 1807.03435 http://arxiv.org/abs/1807.03435
[5]
Marco Cesati and Luca Trevisan. 1997. On the efficiency of polynomial time approximation schemes. Inform. Process. Lett., Vol. 64, 4 (1997), 165--171.
[6]
Tanmoy Chakraborty, Eyal Even-Dar, Sudipto Guha, Yishay Mansour, and Shanmugavelayutham Muthukrishnan. 2010. Approximation schemes for sequential posted pricing in multi-unit auctions. In International Workshop on Internet and Network Economics. Springer, 158--169.
[7]
José Correa, Patricio Foncea, Dana Pizarro, and Victor Verdugo. 2019 a. From pricing to prophets, and back! Operations Research Letters, Vol. 47, 1 (2019), 25--29.
[8]
José R. Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. 2017. Posted Price Mechanisms for a Random Stream of Customers. In Proceedings of the 2017 ACM Conference on Economics and Computation, EC '17, Cambridge, MA, USA, June 26--30, 2017. 169--186.
[9]
José R. Correa, Raimundo Saona, and Bruno Ziliotto. 2019 b. 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. 1946--1961.
[10]
Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, and Sahil Singla. 2018. 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. 700--714.
[11]
Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Morteza Monemizadeh. 2017. Prophet secretary. SIAM Journal on Discrete Mathematics, Vol. 31, 3 (2017), 1685--1701.
[12]
Hao Fu, Jian Li, and Pan Xu. 2018. A PTAS for a Class of Stochastic Dynamic Programs. arXiv preprint arXiv:1805.07742 (2018).
[13]
T. P. Hill and R. P. Kertz. 1982. Comparisons of stop rules and supremum expectations of i.i.d. random variables. Ann. Probab., Vol. 10 (1982), 336--345.
[14]
Kumar Joag-Dev and Frank Proschan. 1983. Negative association of random variables with applications. The Annals of Statistics (1983), 286--295.
[15]
Robert P Kertz. 1986. Stop rule and supremum expectations of iid random variables: a complete comparison by conjugate duality. Journal of Multivariate Analysis, Vol. 19, 1 (1986), 88--112.
[16]
Ulrich Krengel and Louis Sucheston. 1977. Semiamarts and finite values. Bull. Amer. Math. Soc., Vol. 83, 4 (07 1977), 745--747.
[17]
Ulrich Krengel and Louis Sucheston. 1978. On semiamarts, amarts and processes with finite values. Adv. in Probab., Vol. 4 (1978), 197--266.
[18]
Ester Samuel-Cahn. 1984. Comparison of Threshold Stop Rules and Maximum for Independent Nonnegative Random Variables. The Annals of Probability, Vol. 12, 4 (11 1984), 1213--1216.
[19]
Danny Segev and Sahil Singla. 2020. Efficient Approximation Schemes for Stochastic Probing and Prophet Problems. CoRR, Vol. abs/2007.13121 (2020). arxiv: 2007.13121 https://arxiv.org/abs/2007.13121
[20]
Sahil Singla. 2018. Combinatorial Optimization Under Uncertainty: Probing and Stopping-Time Algorithms. Ph.D. Dissertation. PhD thesis, Carnegie Mellon University.

Cited By

View all
  • (2022)Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00023(171-178)Online publication date: Oct-2022

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
EC '21: Proceedings of the 22nd ACM Conference on Economics and Computation
July 2021
950 pages
ISBN:9781450385541
DOI:10.1145/3465456
Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 July 2021

Check for updates

Author Tags

  1. online decision making
  2. prophet inequalities
  3. secretary problem

Qualifiers

  • Extended-abstract

Conference

EC '21
Sponsor:

Acceptance Rates

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

Upcoming Conference

EC '25
The 25th ACM Conference on Economics and Computation
July 7 - 11, 2025
Stanford , CA , USA

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)8
  • Downloads (Last 6 weeks)0
Reflects downloads up to 31 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2022)Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00023(171-178)Online publication date: Oct-2022

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media