Seminars

View all Seminars  |  Download ICal for this event

Prophet Inequalities: Old and New

Series: Bangalore Theory Seminars

Speaker: Jose Correa, Universidad de Chile

Date/Time: Apr 17 17:30:00

Location: Online Talk (See Teams link below)

Abstract:
In this talk, I will survey some of the most widely used techniques for designing and analyzing online algorithms under stochastic input. The playground is that of the classic prophet inequality. This states that, when faced with a finite sequence of non-negative independent random variables, a gambler who knows their distribution and is allowed to stop the sequence at any time, can obtain, in expectation, at least half as much reward as a prophet who knows the values of each random variable and can choose the largest one.

We begin by reviewing the classic -balanced prices- proof of this result, due to Samuel Cahn. We then introduce online contention resolution schemes of Feldman, Svensson, and Zenklusen, and discuss how to adapt them to the prophet inequality setting. To wrap up, we dive into the data-driven approach recently introduced by Rubinstein, Wang, and Weinberg. In all cases, we provide additional references to the literature and discuss some of the more recent research and open problems. In the final part of the talk, we introduce a new technique to tackle prophetinequalities based on Ordinary Differential Equations and show how this approach provides a unified view of the problem and all known algorithms for it.


Microsoft Teams link:

Link


We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series


Hosts: Rameesh Paul, Debajyoti Kar, KVN Sreenivas, Nirjhar Das, Rahul Madhavan