Document Open Access Logo

Threshold Testing and Semi-Online Prophet Inequalities

Authors Martin Hoefer , Kevin Schewior

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.62.pdf
  • Filesize: 0.73 MB
  • 15 pages

Document Identifiers

Author Details

Martin Hoefer
  • Institute of Computer Science, Goethe University Frankfurt, Germany
Kevin Schewior
  • Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark

Funding

  • Hoefer, Martin: Supported by DFG Research Unit ADYN (411362735) and grant 514505843.
  • Schewior, Kevin: Supported by the Independent Research Fund Denmark, Natural Sciences, grant DFF-0135-00018B.

Acknowledgements

The authors gratefully acknowledge discussions with Daniel Schmand and Luca von der Brelie.

Cite As Get BibTex

Martin Hoefer and Kevin Schewior. Threshold Testing and Semi-Online Prophet Inequalities. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ESA.2023.62

Abstract

We study threshold testing, an elementary probing model with the goal to choose a large value out of n i.i.d. random variables. An algorithm can test each variable X_i once for some threshold t_i, and the test returns binary feedback whether X_i ≥ t_i or not. Thresholds can be chosen adaptively or non-adaptively by the algorithm. Given the results for the tests of each variable, we then select the variable with highest conditional expectation. We compare the expected value obtained by the testing algorithm with expected maximum of the variables.
Threshold testing is a semi-online variant of the gambler’s problem and prophet inequalities. Indeed, the optimal performance of non-adaptive algorithms for threshold testing is governed by the standard i.i.d. prophet inequality of approximately 0.745 + o(1) as n → ∞. We show how adaptive algorithms can significantly improve upon this ratio. Our adaptive testing strategy guarantees a competitive ratio of at least 0.869 - o(1). Moreover, we show that there are distributions that admit only a constant ratio c < 1, even when n → ∞. Finally, when each box can be tested multiple times (with n tests in total), we design an algorithm that achieves a ratio of 1 - o(1).

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Online algorithms
  • Theory of computation → Markov decision processes
Keywords
  • Prophet Inequalities
  • Testing
  • Stochastic Probing

Metrics

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

Related Versions

References

  1. Marek Adamczyk, Maxim Sviridenko, and Justin Ward. Submodular stochastic probing on matroids. In Symposium on Theoretical Aspects of Computer Science (STACS), pages 29-40, 2014. Google Scholar
  2. S. Agrawal, J. Sethuraman, and X. Zhang. On optimal ordering in the optimal stopping problem. In ACM Conference on Economics and Computation (EC), pages 187-188, 2020. Google Scholar
  3. Saeed Alaei. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM J. Comput., 43(2):930-972, 2014. Google Scholar
  4. Arash Asadpour, Hamid Nazerzadeh, and Amin Saberi. Stochastic submodular maximization. In Workshop on Internet and Network Economics (WINE), pages 477-489, 2008. Google Scholar
  5. Archit Bubna and Ashish Chiplunkar. Prophet inequality: Order selection beats random order. CoRR, abs/2211.04145, 2022. URL: https://arxiv.org/abs/2211.04145.
  6. José R. Correa, Andrés Cristi, Boris Epstein, and José A. Soto. Sample-driven optimal stopping: From the secretary problem to the i.i.d. prophet inequality. CoRR, abs/2011.06516, 2020. URL: https://arxiv.org/abs/2011.06516.
  7. José R. Correa, Paul Dütting, Felix A. Fischer, and Kevin Schewior. Prophet inequalities for independent and identically distributed random variables from an unknown distribution. Math. Oper. Res., 47(2):1287-1309, 2022. Google Scholar
  8. José R. Correa, Paul Dütting, Felix A. Fischer, Kevin Schewior, and Bruno Ziliotto. Unknown I.I.D. prophets: Better bounds, streaming algorithms, and a new impossibility (extended abstract). In Innovations in Theoretical Computer Science Conference (ITCS), pages 86:1-86:1, 2021. Google Scholar
  9. José R. Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. Recent developments in prophet inequalities. SIGecom Exch., 17(1):61-70, 2018. Google Scholar
  10. José R. Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. Posted price mechanisms and optimal threshold strategies for random arrivals. Math. Oper. Res., 46(4):1452-1478, 2021. Google Scholar
  11. José R. Correa, Raimundo Saona, and Bruno Ziliotto. Prophet secretary through blind strategies. Math. Program., 190(1):483-521, 2021. Google Scholar
  12. Paul Dütting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier. Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs. SIAM J. Comput., 49(3):540-582, 2020. Google Scholar
  13. 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 International Colloqium on Automata, Languages, and Programming (ICALP), pages 508-519, 2014. Google Scholar
  14. Anupam Gupta, Haotian Jiang, Ziv Scully, and Sahil Singla. The markovian price of information. In Integer Programming and Combinatorial Optimization (IPCO), pages 233-246, 2019. Google Scholar
  15. Anupam Gupta and Viswanath Nagarajan. A stochastic probing problem with applications. In Integer Programming and Combinatorial Optimization (IPCO), pages 205-216, 2013. Google Scholar
  16. Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Algorithms and adaptivity gaps for stochastic probing. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1731-1747, 2016. Google Scholar
  17. Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Adaptivity gaps for stochastic probing: Submodular and XOS functions. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1688-1702. SIAM, 2017. Google Scholar
  18. Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, and Tuomas Sandholm. Automated online mechanism design and prophet inequalities. In AAAI Conference on Artificial Intelligence (AAAI), pages 58-65, 2007. Google Scholar
  19. T. P. Hill and R. P. Kertz. Comparisons of stop rule and supremum expectations of i.i.d. random variables. Annals of Probability, 10(2):336-345, 1982. Google Scholar
  20. Martin Hoefer, Kevin Schewior, and Daniel Schmand. Stochastic probing with increasing precision. In International Joint Conference on Artificial Intelligence (IJCAI), pages 4069-4075, 2021. Google Scholar
  21. Robert Kleinberg and S. Matthew Weinberg. Matroid prophet inequalities and applications to multi-dimensional mechanism design. Games Econ. Behav., 113:97-115, 2019. Google Scholar
  22. U. Krengel and L. Sucheston. Semiamarts and finite values. Bull. Amer. Math. Soc., 83:745-747, 1977. Google Scholar
  23. Renato Paes Leme, Balasubramanian Sivan, Yifeng Teng, and Pratik Worah. Pricing query complexity of revenue maximization. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 399-415. SIAM, 2023. Google Scholar
  24. Bo Li, Xiaowei Wu, and Yutong Wu. Query efficient prophet inequality with unknown I.I.D. distributions. CoRR, abs/2205.05519, 2022. URL: https://arxiv.org/abs/2205.05519.
  25. Allen Liu, Renato Paes Leme, Martin Pál, Jon Schneider, and Balasubramanian Sivan. Variable decomposition for prophet inequalities and optimal ordering. In ACM Conference on Economics and Computation (EC), page 692, 2021. Google Scholar
  26. Brendan Lucier. An economic view of prophet inequalities. SIGecom Exch., 16(1):24-47, 2017. Google Scholar
  27. Michela Meister and Sloan Nietert. Learning with comparison feedback: Online estimation of sample statistics. In Algorithmic Learning Theory (ALT), volume 132, pages 983-1001, 2021. Google Scholar
  28. Princewill Okoroafor, Vaishnavi Gupta, and Robert Kleinberg. Non-stochastic CDF estimation using threshold queries. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3551-3572. SIAM, 2023. Google Scholar
  29. Bo Peng and Zhihao Gavin Tang. Order selection prophet inequality: From threshold optimization to arrival time design. In IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 171-178, 2022. Google Scholar
  30. Sebastian Perez-Salazar, Mohit Singh, and Alejandro Toriello. The IID prophet inequality with limited flexibility. CoRR, abs/2210.05634, 2022. URL: https://arxiv.org/abs/2210.05634.
  31. Aviad Rubinstein, Jack Z. Wang, and S. Matthew Weinberg. Optimal single-choice prophet inequalities from samples. In Innovations in Theoretical Computer Science Conference (ITCS), pages 60:1-60:10, 2020. Google Scholar
  32. Martin L. Weitzman. Optimal search for the best alternative. Econometrica, 47:641-654, 1979. 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