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.

Prophet Inequalities via the Expected Competitive Ratio / Ezra, Tomer; Leonardi, Stefano; Reiffenhäuser, Rebecca; Russo, Matteo; Tsigonias-Dimitriadis, Alexandros. - (2024). (Intervento presentato al convegno Web and Internet Economics - 19th International Conference, WINE 2023 tenutosi a Shangai).

Prophet Inequalities via the Expected Competitive Ratio

Tomer Ezra;Stefano Leonardi
;
Matteo Russo
;
2024

Abstract

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.
2024
Web and Internet Economics - 19th International Conference, WINE 2023
Prophet Inequalities, Online Decision-Making, Downward-closed Feasibility Constraints
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Prophet Inequalities via the Expected Competitive Ratio / Ezra, Tomer; Leonardi, Stefano; Reiffenhäuser, Rebecca; Russo, Matteo; Tsigonias-Dimitriadis, Alexandros. - (2024). (Intervento presentato al convegno Web and Internet Economics - 19th International Conference, WINE 2023 tenutosi a Shangai).
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1707252
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact