Prophet inequality (original) (raw)

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.