Prophet inequality

In the theory of online algorithms and optimal stopping, a prophet inequality is a bound on the expected value of a decision-making process that handles a sequence of random inputs from known probability distributions, relative to the expected value that could be achieved by a "prophet" who knows all the inputs (and not just their distributions) ahead of time. These inequalities have applications in the theory of algorithmic mechanism design and mathematical finance.

Single item

The classical single-item prophet inequality was published by Krengel & Sucheston (1978), crediting its tight form to D. J. H. (Ben) Garling. It concerns a process in which a sequence of random variables $X_{i}$ arrive from known distributions ${\mathcal {D}}_{i}$. When each $X_{i}$ arrives, the decision-making process must decide whether to accept it and stop the process, or whether to reject it and go on to the next variable in the sequence. The value of the process is the single accepted variable, if there is one, or zero otherwise. It may be assumed that all variables are non-negative; otherwise, replacing negative values by zero does not change the outcome. This can model, for instance, financial situations in which the variables are offers to buy some indivisible good at a certain price, and the seller must decide which (if any) offer to accept. A prophet, knowing the whole sequence of variables, can obviously select the largest of them, achieving value ${\textstyle \max _{i}X_{i}}$ for any specific instance of this process, and expected value ${\textstyle \mathbb {E} [\max _{i}X_{i}]}$. The prophet inequality states the existence of an online algorithm for this process whose expected value is at least half that of the prophet: ${\textstyle {\tfrac {1}{2}}\mathbb {E} [\max _{i}X_{i}]}$. No algorithm can achieve a greater expected value for all distributions of inputs.

One method for proving the single-item prophet inequality is to use a "threshold algorithm" that sets a parameter $\tau$ and then accepts the first random variable that is at least as large as $\tau$. If the probability that this process accepts an item is $p$, then its expected value is $p\tau$ plus the expected excess over $\tau$ that the selected variable (if there is one) has. Each variable $X_{i}$ will be considered by the threshold algorithm with probability at least $1-p$, and if it is considered will contribute ${\textstyle \max(X_{i}-\tau ,0)}$ to the excess, so by linearity of expectation the expected excess is at least

$$\mathbb {E} {\Bigl [}\sum _{i}(1-p)\max(X_{i}-\tau ,0){\Bigr ]}\geq (1-p){\bigl (}\mathbb {E} [\max _{i}X_{i}]-\tau ).$$

Setting $\tau$ to the median of the distribution of ${\textstyle \max _{i}X_{i}}$, so that $p={\tfrac {1}{2}}$, and adding $p\tau$ to this bound on expected excess, causes the $p\tau$ and $(1-p)(-\tau )$ terms to cancel each other, showing that for this setting of $\tau$ the threshold algorithm achieves an expected value of at least ${\textstyle {\tfrac {1}{2}}\mathbb {E} [\max _{i}X_{i}]}$. A different threshold, ${\textstyle \tau ={\tfrac {1}{2}}\mathbb {E} [\max _{i}X_{i}]}$, also achieves at least this same expected value.

Generalizations

Various generalizations of the single-item prophet inequality to other online scenarios are known, and are also called prophet inequalities.

Comparison to competitive analysis

Prophet inequalities are related to the competitive analysis of online algorithms, but differ in two ways. First, much of competitive analysis assumes worst case inputs, chosen to maximize the ratio between the computed value and the optimal value that could have been achieved with knowledge of the future, whereas for prophet inequalities some knowledge of the input, its distribution, is assumed to be known. And second, in order to achieve a certain competitive ratio, an online algorithm must perform within that ratio of the optimal performance on all inputs. Instead, a prophet inequality only bounds the performance in expectation, allowing some input sequences to produce worse performance as long as the average is good.

External links

• Matroid Prophet Inequalities and Mechanism Design, The Matroid Union
• An Economic View of Prophet Inequalities