A Bicriterion Concentration Inequality and Prophet Inequalities for $k$-Fold Matroid Unions

Noga Alon, Nick Gravin, Tristan Pollner +4

We investigate prophet inequalities with competitive ratios approaching $1$, seeking to generalize $k$-uniform matroids. We first show that large girth does not suffice: for all $k…