Minimization is Harder in the Prophet World

Vasilis Livanos, Ruta Mehta

Research output: Contribution to conferencePaperpeer-review

Abstract

We study I.I.D. prophet inequalities for cost minimization, where the problem is to pick a cost from a sequence X1, ..., Xn drawn independently from a known distribution in an online manner, and compete against the prophet who can see all the realizations upfront and select the minimum. In contrast to the well-studied rewards maximization setting where a simple threshold strategy achieves a competitive ratio of ≈ 0.745 for all distributions, the cost minimization setting turns out to be much more complex. In our main result, we obtain a complete and nuanced characterization of the I.I.D. cost prophet inequality: if the expected value of the given distribution is infinite, then the competitive ratio is also infinite. On the other hand, when the expected value is finite, we show that the competitive ratio of the optimal stopping strategy is a (distribution-dependent) constant, which we characterize precisely as the solution to a simple inequality. Furthermore, we obtain a closed form for this constant for a broad class of distributions we call entire distributions, we show that the constant is 2 for MHR distributions and obtain matching lower bounds for all our results. To the best of our knowledge, these are the first optimal distribution-sensitive guarantees for the prophet inequality setting. We then focus on single-threshold strategies and design a single threshold that achieves a tight O (polylog n)factor approximation. In terms of techniques, we characterize the expected value of order statistics using the hazard rate of the distribution, which facilitates our analysis. Our results may also be used to design approximately optimal posted price-style mechanisms. We believe both of these may be of independent interest.

Original languageEnglish (US)
Pages424-461
Number of pages38
DOIs
StatePublished - 2024
Externally publishedYes
Event35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States
Duration: Jan 7 2024Jan 10 2024

Conference

Conference35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
Country/TerritoryUnited States
CityAlexandria
Period1/7/241/10/24

Keywords

  • cost minimization
  • hazard rate
  • MHR distributions
  • online algorithms
  • order statistics
  • prophet inequalities

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Minimization is Harder in the Prophet World'. Together they form a unique fingerprint.

Cite this