Prophet inequalities and secretary problem: a new approach.
Time: 14:30 -- Location: LIX
In the setting of prophet inequalities and secretary problem, one observes a sequence of random objects and is allowed to stop the sequence at any time, claiming a reward equal to the most recent observation. The objective is to maximize the reward while observing the objects in an online manner and making irrevocable decision. These problems have been widely studying in optimal stopping theory and recently in the algorithmic community due to many applications in machine learning, algorithmic game theory, etc. The latter refreshes and raises interesting questions related to the prophet inequalities and the secretary problem. We present a new approach based on linear programming to study such questions.