1 citations · 1 across the 12 of their papers we have counts for
7 papers · 1 filter
Kernel Methods for Refined Prophet Inequalities
Patrick Loiseau, Mathieu Molina, Vianney Perchet +2
The single-selection prophet inequality is a canonical Bayesian online selection problem in which independent nonnegative values arrive sequentially and the decision-maker must irr…
Threshold Dynamics and Correlated Prophet Inequalities
José Correa, Maximilian Fichtl, Reda Jlibene +4
Prophet inequalities have become a central tool for analyzing the performance of online algorithms. However, most existing results assume that input random variables are independen…
Competition Versus Complexity in Multiple-Selection Prophet Inequalities
Eugenio Cruz-Ossa, Sebastian Perez-Salazar, Victor Verdugo
Competition complexity formalizes a compelling intuition: rather than refining the mechanism, how much additional competition is sufficient for a simple mechanism to compete with a…
Prophet Upper Bounds for Online Matching and Auctions
José Soto, Victor Verdugo
In the online 2-bounded auction problem, we have a collection of items represented as nodes in a graph and bundles of size two represented by edges. Agents are presented sequential…
Optimal Guarantees for Online Selection Over Time
Sebastian Perez-Salazar, Victor Verdugo
Prophet inequalities are a cornerstone in optimal stopping and online decision-making. Traditionally, they involve the sequential observation of non-negative independent random…
Splitting Guarantees for Prophet Inequalities via Nonlinear Systems
Johannes Brustle, Sebastian Perez-Salazar, Victor Verdugo
The prophet inequality is one of the cornerstone problems in optimal stopping theory and has become a crucial tool for designing sequential algorithms in Bayesian settings. In the…
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…