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 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, crediting its tight form to D. J. H. Garling. It concerns a process in which a sequence of random variables arrive from known distributions. When each 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 offer to accept. A prophet, knowing the whole sequence of variables, can obviously select the largest of them, achieving value for any specific instance of this process, and expected value The prophet inequality states the existence of an online algorithm for this process whose expected value is at least half that of the prophet: No algorithm can achieve a greater expected value for all distributions of
One method for proving the single-item prophet inequality is to use a "threshold algorithm" that sets a parameter and then accepts the first random variable that is at least as large If the probability that this process accepts an item is, then its expected value is plus the expected excess over that the selected variable has. Each variable will be considered by the threshold algorithm with probability at least and if it is considered will contribute to the excess, so by linearity of expectation the expected excess is at least Setting to the median of the distribution of so that and adding to this bound on expected excess, causes the and terms to cancel each other, showing that for this setting of the threshold algorithm achieves an expected value of at least A different threshold, 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. These include settings where more than one value can be accepted and the objective is to maximize the sum of accepted values subject to some constraint on the set of accepted elements. For example, a cardinality constraint of where we want to accept at most elements, or a matroid constraint where the elements have a known matroid structure and we want to only accept an independent set of the matroid.

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.