Prophets Inequalities with Uncertain Acceptance

We introduce the $\mathit{\text{prophet}}\mathit{\text{inequality}}\mathit{\text{with}}\mathit{\text{uncertain}}\mathit{\text{acceptance}}$ model, in which a decision maker sequentially observes a sequence of independent options, each characterized by a value $x_i$ and an acceptance probability $p_i$, both sampled from a known joint distribution. At time $i$, the decision maker observes the value $x_i$ and must irrevocably and immediately decide whether to attempt to select it or to continue to the next time step. If the option is selected, the process terminates with probability $p_i$ and the decision maker obtains $x_i$; otherwise, she continues searching. In this setting, two natural benchmarks arise: the $\mathit{\text{value-aware}}\mathit{\text{decision-maker}}$, who knows all value realizations in advance but not the acceptance outcomes, and the $\mathit{\text{full-knowledge}}\mathit{\text{prophet}}$, who knows all realizations beforehand and can choose the best option among those that will be accepted. We characterize the worst-case competitive ratios between our defined agents and show that all these values equal $1\mathrm{/}2$. In addition, we provide sufficient conditions under which the value-aware decision-maker surpasses the $1\mathrm{/}2$-barrier against the more informed prophet. This demonstrates the (crucial) interest for the decision maker to improve her knowledge over the values rather than over the acceptances, and is obtained via a more general result that reduces the value-aware decision-maker’s problem to a classical prophet inequality with scaled Bernoulli distributions, followed by a sequence of transformations that further reduce the problem to a unique optimization problem.