Prophet inequality

==Generalizations==

==Generalizations==

Various generalizations of the single-item prophet inequality to other online scenarios are known, and are also called prophet inequalities.{{r|fks}} 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 constraints on the set of accepted elements. For example, a [[cardinality]] constraint of <math>m</math> where we want to accept at most <math>m</math> 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.<ref>{{Cite journal |last=Kleinberg |first=Robert |last2=Weinberg |first2=S. Matthew |date=2019-01-01 |title=Matroid prophet inequalities and applications to multi-dimensional mechanism design |url=https://www.sciencedirect.com/science/article/pii/S0899825614001651 |journal=Games and Economic Behavior |volume=113 |pages=97–115 |doi=10.1016/j.geb.2014.11.002 |issn=0899-8256}}</ref>

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

==Comparison to competitive analysis==

==Comparison to competitive analysis==