8 papers
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…
Online Contract Selection for Continual Coverage
Qinge Chi, Sebastian Perez-Salazar
Motivated by applications where a system must remain operational via continual procurement of contracts, we study two online contract selection problems under uncertain prices. At…
Prophet Inequalities with Delayed and Uncertain Acceptance
Emile Martinez, Felipe Garrido-Lucero, Umberto Grandi +1
We introduce the prophet inequality with delayed and uncertain acceptance, a variant of the classical prophet inequality in which a decision-maker sequentially evaluates options wh…
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…
Residual Prophet Inequalities
Jose Correa, Sebastian Perez-Salazar, Dana Pizarro +1
We introduce a variant of the classic prophet inequality, called \emph{residual prophet inequality} (RPI). In the RPI problem, we consider a finite sequence of nonnegative inde…
Online Selection with Uncertain Disruption
Yihua Xu, Süleyman Kerimov, Sebastian Perez-Salazar
In numerous online selection problems, decision-makers (DMs) must allocate on the fly limited resources to customers with uncertain values. The DM faces the tension between allocat…