Dipartimento di Ingegneria informatica, automatica e gestionale

We consider prophet inequalities under downward-closed constraints. In this problem, a decision-maker makes immediate and irrevocable choices on arriving elements, subject to constraints. Traditionally, performance is compared to the expected offline optimum, called the Ratio of Expectations ( ). However, has limitations as it only guarantees the average performance compared to the optimum, and might perform poorly against the realized ex-post optimal value. We study an alternative performance measure, the Expected Ratio ( ), namely the expectation of the ratio between algorithm’s and prophet’s value. offers robust guarantees, e.g., a constant implies achieving a constant fraction of the offline optimum with constant probability. For the special case of single-choice problems the coincides with the well-studied notion of probability of selecting the maximum. However, the naturally generalizes the probability of selecting the maximum for combinatorial constraints, which are the main focus of this paper. Specifically, we establish two reductions: for every constraint, and the are at most a constant factor apart. Additionally, we show that the is a stronger benchmark than the in that, for every instance (constraint and distribution), the is at least a constant fraction of the , but not vice versa. Both these reductions imply a wealth of results in multiple settings where results are known.