AI summaryⓘ
The authors study a problem where you want to pick numbers to minimize the smallest chosen value, which is harder than trying to pick the biggest. They allow picking multiple numbers and then choosing the smallest among them, aiming to do well while picking as few as possible. They show that if the order is adversarial, you must pick almost a linear number of values to be good, but if the order is random, you can pick many fewer (logarithmic in number). They also discuss the limits on how few choices you can make for good results, including scenarios where the number of picks is fixed or multiple picks are considered. Their work quantifies these trade-offs in different settings like i.i.d. variables and random order arrivals.
Prophet inequalityMinimization problemCompetitive ratioAdversarial orderProphet secretary problemRandom orderi.i.d. variablesMulti-choice algorithmThreshold algorithmMulti-unit selection
Authors
Yossi Azar, Itamar Biran, Amos Fiat
Abstract
We study the minimization counterpart of the classic prophet inequality, often termed the min prophet or cost prophet inequality. Unlike the maximization setting, where simple threshold algorithms achieve half of the prophet's value, the minimization setting is significantly harder, with an exponential lower bound even for i.i.d.\ variables. We study a multi-choice relaxation in which the algorithm may select multiple variables and gets to choose the best amongst them (the minimum amongst those selected). Our goal is to minimize the expected number of selections while achieving a constant competitive ratio. For adversarial order, we show that a constant competitive ratio requires a nearly linear number of choices in expectation, ergo, $Ω(n/\ln n)$. In contrast, we show that for the prophet secretary model (random order) one can attain constant competitiveness while requiring only an exponentially smaller expected number of choices i.e. $O(\ln n)$. We give a refined analysis and define $M$ to be the ratio of the minimum expected value of any single variable to the expected minimum value of all variables (the prophet's value) and present an algorithm that achieves a constant competitive ratio with $O(\min\{\ln \ln M, \ln n\})$ choices in expectation for the prophet secretary. We show that this is tight up to low order log factors even for the special case of the i.i.d. model. We also show that if we insist on a deterministic bound on the number of choices then every constant competitive algorithm requires $n$ choices. This holds even in the i.i.d.\ setting Finally, we consider a variant where both the algorithm and the adversary choose $r$ values and pay their sum, this is the minimization multi unit version. We extend our techniques to the multi-unit variant for i.i.d.\ variables, achieving a constant competitive ratio with a small expected number of choices.