# Combinatorial Prophet Inequalities

arXiv: https://arxiv.org/abs/1611.00665 · HTML: https://mlsanity.com/paper/1611.00665/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2016.

## Built on by (most cited first, 4 of 4)

- [Bandit Algorithms for Prophet Inequality and Pandora's Box](https://mlsanity.com/paper/2211.08586/) (2022)
- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [Streaming Adaptive Submodular Maximization](https://mlsanity.com/paper/2208.08021/) (2022)
- [Pairwise independent correlation gap](https://mlsanity.com/paper/2209.08563/) (2022)

## Abstract (arXiv)

We introduce a novel framework of Prophet Inequalities for combinatorial valuation functions. For a (non-monotone) submodular objective function over an arbitrary matroid feasibility constraint, we give an O(1)-competitive algorithm. For a monotone subadditive objective function over an arbitrary downward-closed feasibility constraint, we give an O(log n log2 r)-competitive algorithm (where r is the cardinality of the largest feasible subset). Inspired by the proof of our subadditive prophet inequality, we also obtain an O(log n · log2 r)-competitive algorithm for the Secretary Problem with a monotone subadditive objective function subject to an arbitrary downward-closed feasibility constraint. Even for the special case of a cardinality feasibility constraint, our algorithm circumvents an Omega(√n) lower bound by Bateni, Hajiaghayi, and Zadimoghaddam citeBHZ13-submodular-secretaryoriginal in a restricted query model. En route to our submodular prophet inequality, we prove a technical result of independent interest: we show a variant of the Correlation Gap Lemma for non-monotone submodular functions.