In the theory ofonline algorithms andoptimal stopping, aprophet inequality is a bound on theexpected value of a decision-making process that handles a sequence of random inputs from knownprobability 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.^[1][2] These inequalities have applications in the theory ofalgorithmic mechanism design andmathematical finance.^[3]

The classical single-item prophet inequality was published byKrengel & Sucheston (1978), crediting its tight form to D. J. H. (Ben) Garling. It concerns a process in which a sequence of random variables${\displaystyle X_i}$ arrive from known distributions${\displaystyle {\mathcal{D}}_i}$. When each${\displaystyle 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$\underset{i}{max}{X}_i$ for any specific instance of this process, and expected value$\mathbb{E}[\underset{i}{max}{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:$\frac{1}{2}\mathbb{E}[\underset{i}{max}{X}_i]$. No algorithm can achieve a greater expected value for all distributions ofinputs.^[3][4]

One method for proving the single-item prophet inequality is to use a "threshold algorithm" that sets a parameter${\displaystyle \tau }$ and then accepts the first random variable that is at least as largeas${\displaystyle \tau }$. If the probability that this process accepts an item is${\displaystyle p}$, then its expected value is${\displaystyle p\tau }$ plus the expected excess over${\displaystyle \tau }$ that the selected variable (if there is one) has. Each variable${\displaystyle X_i}$ will be considered by the threshold algorithm with probability at least${\displaystyle 1-p}$, and if it is considered will contribute$max(X_i-\tau ,0)$ to the excess, so bylinearity of expectation the expected excess is at least$${\displaystyle \mathbb{E}[\sum _i(1-p)max(X_i-\tau ,0)]\ge (1-p)(\mathbb{E}[\underset{i}{max}{X}_i]-\tau ).}$$ Setting${\displaystyle \tau }$ to the median of the distribution of$\underset{i}{max}{X}_i$, so that${\displaystyle p=\frac{1}{2}}$, and adding${\displaystyle p\tau }$ to this bound on expected excess, causes the${\displaystyle p\tau }$ and${\displaystyle (1-p)(-\tau )}$ terms to cancel each other, showing that for this setting of${\displaystyle \tau }$ the threshold algorithm achieves an expected value of at least$\frac{1}{2}\mathbb{E}[\underset{i}{max}{X}_i]$.^[3][5] A different threshold,$\tau =\frac{1}{2}\mathbb{E}[\underset{i}{max}{X}_i]$, also achieves at least this same expected value.^[3][6]

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

Prophet inequalities are related to thecompetitive analysis of online algorithms, but differ in two ways. First, much of competitive analysis assumesworst 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 certaincompetitive 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.^[3]

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

• Online algorithms
• Sequential experiments
• Mechanism design

• Articles with short description
• Short description matches Wikidata