Prophet Inequality

A prophet inequality compares the expected reward of an online selection rule with the expected best reward obtainable after all random values are known. In the classical one-choice problem, independent nonnegative integrable random variables , ..., arrive sequentially. The online rule may stop once and receives the current value, whereas the prophet receives . A factor- guarantee means

The permitted selections, available distributional information, and arrival order are part of the model. The matroid prophet inequality allows selections forming an independent set of a matroid.