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.

## Dettaglio pubblicazione

2024, Lecture Notes in Computer Science 14413, Springer 2024, Pages -

### Prophet Inequalities via the Expected Competitive Ratio (*04b Atto di convegno in volume*)

#### Ezra Tomer, Leonardi Stefano, Reiffenhäuser Rebecca, Russo Matteo, Tsigonias-Dimitriadis Alexandros

**ISBN:**978-3-031-48973-0

**Gruppo di ricerca:**Algorithms and Data Science