Minimization Fractional Prophet Inequalities for Sequential Procurement

Junjie Qin (), Shai Vardi () and Adam Wierman ()
Additional contact information
Junjie Qin: Purdue University, West Lafayette, Indiana 47907
Shai Vardi: Purdue University, West Lafayette, Indiana 47907
Adam Wierman: California Institute of Technology, Pasadena, California 91125

Mathematics of Operations Research, 2024, vol. 49, issue 2, 928-947

Abstract: We consider a minimization variant on the classical prophet inequality with monomial cost functions. A firm would like to procure some fixed amount of a divisible commodity from sellers that arrive sequentially. Whenever a seller arrives, the seller’s cost function is revealed, and the firm chooses how much of the commodity to buy. We first show that if one restricts the set of distributions for the coefficients to a family of natural distributions that include, for example, the uniform and truncated normal distributions, then there is a thresholding policy that is asymptotically optimal in the number of sellers. We then compare two scenarios based on whether the firm has in-house production capabilities or not. We precisely compute the optimal algorithm’s competitive ratio when in-house production capabilities exist and for a special case when they do not. We show that the main advantage of the ability to produce the commodity in house is that it shields the firm from price spikes in worst-case scenarios.

Keywords: Primary; 68W27; 60G40; prophet inequalities; online algorithms; competitive ratio; in-house production (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.0173 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:49:y:2024:i:2:p:928-947

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().