  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.
