Description
EGERVÁRY SZEMINÁRIUM
Abstract:
A classic result from optimal stopping theory asks when one
should stop
and accept a value presented one by one, if one knows the distributions
that these values are coming from and wants to select the maximum.
The catch is that, if one rejects a value, it can never be selected again.
This setting, which combines online decision making with stochastic
uncertainty, is called the prophet inequality. Over the past decade, there
have been two very exciting discoveries, connecting auction theory and
online combinatorial optimization with prophet inequality-type problems.
In this talk, we cover some of the standard ideas and results on prophet
inequalities and online combinatorial optimization. We give some intuition
about the connections mentioned before and show how one can develop tools
for online combinatorial optimization via a duality approach. Finally,
we study a new direction that studies prophet inequalities for minimization
instead, which present rich and qualitatively different results from the
maximization case.