Oracle-Augmented Prophet Inequalities.


In the top-1-of-k prophet inequality setting, a gambler is given a sequence of n random variables X_1, …, X_n, taken from known distributions, observes their values in an adversarial order, and selects up to k of them, immediately after they are observed, so that the top value selected is as high as possible, comparing against a prophet who always selects the maximum realization. For k = 1, one recovers the classical prophet inequality, and thus this model serves as a generalization.

In this talk, we look at a new approach to solve the top-1-of-k model. We generalize the standard prophet inequality for k = 1, allowing the gambler some additional information about the future that is otherwise privy only to the prophet. Specifically, at any point in the process, the gambler is allowed to query an oracle O. The oracle responds with a single bit answer: YES, if the current realization is the largest of the remaining realizations, and NO otherwise. We show that the oracle model with k oracle calls is equivalent to the top-1-of-(k+1) model when the objective is maximizing the probability of selecting the maximum. This equivalence fails to hold when the objective is maximizing the competitive ratio, but we still show that any algorithm for the oracle model implies an equivalent competitive ratio for the top-1-of-(k+1) model.

We resolve the oracle model for any k, giving almost tight lower and upper bound on the best possible competitive ratio compared to an almighty adversary. As a consequence, we provide new results as well as improvements on known results for the top-1-of-(k+1) model.

at 15:00:00 h
Date of closure: Apr 17, 2024
Venue: Sala de Seminario John Von Neumann, CMM, Beauchef 851, Torre Norte, Piso 7.
Speaker: Vasilis Livanos
Affiliation: Universidad de Chile.
Coordinator: José Verschae
More info at:
Event website

Posted on Apr 15, 2024 in ACGO, Seminars