New paper solves 40-year-old 'min prophet' inequality with logarithmic selections

In a new arXiv preprint, computer scientists Yossi Azar, Itamar Biran, and Amos Fiat tackle the minimization counterpart of the classic prophet inequality—known as the 'min prophet' or 'cost prophet' problem. Unlike the maximization version where simple threshold algorithms achieve a 1/2-competitive ratio, the minimization setting has an exponential lower bound even for i.i.d. variables. The authors introduce a multi-choice relaxation: the algorithm may select multiple variables and then choose the best (minimum) among them, aiming to minimize the expected number of selections while maintaining a constant competitive ratio.

Their results are sharp: for adversarial order, constant competitiveness requires a nearly linear expected number of choices—specifically Ω(n/ln n). In contrast, for the prophet secretary model where variables arrive in random order, they achieve constant competitiveness with only O(ln n) expected selections. They refine this to O(min{ln ln M, ln n}) where M is the ratio of the minimum expected value of any single variable to the expected minimum of all variables, and prove this is tight up to low-order log factors. Additionally, any deterministic bound on the number of choices forces n selections even in i.i.d. settings. The work also extends to a multi-unit variant where both algorithm and adversary pick r values and pay their sum, achieving constant competitiveness with small expected selections.