4 papers
The Competition Complexity of Prophet Inequalities with Correlations
Tomer Ezra, Tamar Garbuz
We initiate the study of the prophet inequality problem through the resource augmentation framework in scenarios when the values of the rewards are correlated. Our goal is to deter…
Prophet Inequality from Samples: Is the More the Merrier?
Tomer Ezra
We study a variant of the single-choice prophet inequality problem where the decision-maker does not know the underlying distribution and has only access to a set of samples from t…
Choosing Behind the Veil: Tight Bounds for Identity-Blind Online Algorithms
Tomer Ezra, Michal Feldman, Zhihao Gavin Tang
In Bayesian online settings, every element has a value that is drawn from a known underlying distribution, which we refer to as the element's identity. The elements arrive sequenti…
The Competition Complexity of Prophet Inequalities
Johannes Brustle, José Correa, Paul Dütting +3
We study the classic single-choice prophet inequality problem through a resource augmentation lens. Our goal is to bound the -competition complexity of different t…