# Beyond matroids: Secretary Problem and Prophet Inequality with general constraints

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

## Key facts

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

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

- [Bandit Algorithms for Prophet Inequality and Pandora's Box](https://mlsanity.com/paper/2211.08586/) (2022)
- [The Competition Complexity of Prophet Inequalities with Correlations](https://mlsanity.com/paper/2409.06868/) (2024)

## Abstract (arXiv)

We study generalizations of the "Prophet Inequality" and "Secretary Problem", where the algorithm is restricted to an arbitrary downward-closed set system. For 0,1-values, we give O(log n)-competitive algorithms for both problems. This is close to the Omega(log n / loglog n) lower bound due to Babaioff, Immorlica, and Kleinberg. For general values, our results translate to O(log n log r)-competitive algorithms, where r is the cardinality of the largest feasible set. This resolves (up to the O(log r loglog n) factors) an open question posed to us by Bobby Kleinberg.