Single Sample Prophet Inequalities via Greedy-Ordered Selection

Mar, 05/04/2022 - 12:00 / 13:00

Research Seminars Virtual Room, Luiss

Speaker: Rebecca Reiffenhäuser , Università La Sapienza

Abstract

With many modern-world challenges, like auctions,  being of an 'online' nature,  solutions often rely on Bayesian approaches like the famous Prophet Inequalities. However, these come with massive information requirements, i.e. the need to know all underlying distributions beforehand. More realistic, limited-information variants are often much weaker, and known only for simple problem variants. In this talk, we will see a general and intuitive technique for designing prophet inequalities that work with a minimal amount of prior information: just a single sample from each distribution. This not only improves on previous results for many settings, like maximum weight matchings, but also achieves constant-factor approximations for a wider range of problems, among them budget-additive combinatorial auctions.

The talk will introduce key ideas and principles, as well as draw connections to other research, providing both a larger context and additional results illustrating the power and generality of this minimal-prior paradigm.