A matroid prophet inequality is a prophet inequality in which the accepted elements must form an independent set of a known finitematroid. For a vector of nonnegative
values ,
the offline benchmark is
The online rule decides irrevocably whether to accept each arriving element.
Kleinberg, R. and Weinberg, S. M. "Matroid Prophet Inequalities." In Proc. Forty-Fourth Annual ACM Symposium on Theory of Computing
(Ed. H. J. Karloff and T. Pitassi). New York: ACM, pp. 123-136,
2012. https://doi.org/10.1145/2213977.2213991.
. For a vector of nonnegative
values 
,
the offline benchmark is
